Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

Размещение

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

Пример 1: ⟨ 1 , 3 , 2 , 5 ⟩ {displaystyle langle 1,3,2,5 angle } — это 4-элементное размещение из 6-элементного множества { 1 , 2 , 3 , 4 , 5 , 6 } {displaystyle {1,2,3,4,5,6}} .

Пример 2: некоторые размещения элементов множества { 1 , 2 , 3 , 4 , 5 , 6 } {displaystyle {1,2,3,4,5,6}} по 2: ⟨ 1 , 2 ⟩ {displaystyle langle 1,2 angle } ⟨ 1 , 3 ⟩ {displaystyle langle 1,3 angle } ⟨ 1 , 4 ⟩ {displaystyle langle 1,4 angle } ⟨ 1 , 5 ⟩ {displaystyle langle 1,5 angle } … ⟨ 2 , 1 ⟩ {displaystyle langle 2,1 angle } ⟨ 2 , 3 ⟩ {displaystyle langle 2,3 angle } ⟨ 2 , 4 ⟩ {displaystyle langle 2,4 angle } … ⟨ 2 , 6 ⟩ {displaystyle langle 2,6 angle } …

В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы ⟨ 2 , 1 , 3 ⟩ {displaystyle langle 2,1,3 angle } и ⟨ 3 , 2 , 1 ⟩ {displaystyle langle 3,2,1 angle } являются различными размещениями, хотя состоят из одних и тех же элементов { 1 , 2 , 3 } {displaystyle {1,2,3}} (то есть совпадают как сочетания).

Заполнить ряд - значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причем каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т.е мы разместили объекты на данных местах.

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

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

A n k = n k _ = ( n ) k = n ( n − 1 ) ⋅ … ⋅ ( n − k + 1 ) = n ! ( n − k ) ! {displaystyle A_{n}^{k}=n^{underline {k}}=(n)_{k}=n(n-1)cdot ldots cdot (n-k+1)={frac {n!}{(n-k)!}}} .

Элементарным образом выражается через символ Похгаммера:

A n k = ( n − k + 1 ) k {displaystyle A_{n}^{k}=(n-k+1)_{k}} .

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

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

A n n = P n = n ! {displaystyle A_{n}^{n}=P_{n}=n!} .

Справедливо следующее утверждение: A n n − 1 = A n n {displaystyle A_{n}^{n-1}=A_{n}^{n}} . Доказывается тривиально:

A n n − 1 = n ! ( n − ( n − 1 ) ) ! = n ! ( n − n + 1 ) ! = n ! = A n n {displaystyle A_{n}^{n-1}={frac {n!}{(n-(n-1))!}}={frac {n!}{(n-n+1)!}}=n!=A_{n}^{n}} .

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

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

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

По правилу умножения количество размещений с повторениями из n по k, обозначаемое A ¯ n k {displaystyle {ar {A}}_{n}^{k}} , равно:

A ¯ n k = n k {displaystyle {ar {A}}_{n}^{k}=n^{k}} .

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

A ¯ 10 3 = 10 3 = 1000 {displaystyle {ar {A}}_{10}^{3}=10^{3}=1000} .

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

aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd.