4 Билет

Размещение с повторениями

В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.

Пример 1:   — это 4-элементное размещение из 6-элементного множества  .

Пример 2: некоторые размещения элементов множества   по 2:         ...       ...  ...

В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы   и   являются различными, хотя состоят из одних и тех же элементов   (то есть совпадают как сочетания).

Количество размещений из n по k, обозначаемое  , равно убывающему факториалу:

Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту  , в то время как перестановок на k элементах ровно k! штук.

При k=n количество размещений равно количеству перестановок порядка n:

Размещение с повторениями

Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.

Количество размещений с повторениями

По правилу умножения количество размещений с повторениями из n по k, обозначаемое  , равно:

Например, количество вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:

Ещё 1 пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно   эти размещения следующие:

5 Билет

Размещения без повторений

В размещении с повторениями были допустимы повторы элементов в каждой ячейке. Как на примере кодового замка - одну крутящуюся "крутилку :)" с цифрами можно сопоставить с одной ячейкой, а цифры от нуля до девяти на ней - элементами. Очевидно, что может быть несколько ячеек с одинаковой цифрой. "Отоно шо, Мыхалыч, от оно шо", потому и называется размещения с повторениями. А что если ячейками является несколько стульев, а элементами люди? Очевидно, что на трех разных стульев не может сидеть один и тот же человек (Конечно если он не наберется наглости и не ляжет вдоль стульев, чем эффектно испортит весь эксперимент). Вот как раз в такие моменты и используется формуларазмещения без повторения которая выглядит вот так: Где m - количество элементов, а k - количество ячеек. m! - рассчитывает все возможные варианты комбинаций данных элементов. (m-k)! - все возможные варианты элементов оставшихся без ячеек. Разделив одно на другое - каким-то боком узнаем, все варианты размещения без повторений О_о Это была удобная продвинутая формула. Но так же есть и более простая. То есть если так же выбрать кто будет сидеть на трех стульях из 14 человек, можно не вспоминать то нечто ужасное с восклицательными знаками, а просто перемножить таким образом: 14 (садим одного на стул)*13(посадили еще одного)*12(и еще одного, 3 стула заняты)=2184 комбинации. Если подставить в формулу выше - получим тот же ответ. И накой же нам тогда верхняя формула с факториалами? А на тот случай, если стульев окажется эдак 80, а человек эдак 120. Не перемножать же все долгой длинной цепочкой =)