§ 3. Выборки и упорядочения

Отметим, что в множестве порядок элементов не играет никакой роли, т.е. если $A=\{a,b\}$, $B=\{b,a\}$, то А=В.

Пусть имеется множество А с n элементами, которое часто называется n-множеством А. Некоторая совокупность r элементов этого множества: (а1, а2,…, аr), где аi∈А, i=1,2,…,r, r ≤ n, называется r-выборкой, а число r - ее объемом.

Неупорядоченные r-выборки из n-множества А называются r сочетаниями, если все r элементов различны, и r-сочетаниями с повторениями - при наличии одинаковых элементов.

Упорядоченные r-выборки из n-множества А называются r перестановками, если все r элементов различны, и r-перестановками с повторениями, если среди r элементов имеются одинаковые (равные).

Задачи выделения r-перестановок и r-сочетаний не дают, как правило, единственного решения. Эта неоднозначность с решением порождает естественный вопрос: сколькими способами можно осуществить требуемое комбинаторное расположение.

Найдем число всех возможных r-перестановок (без повторений) из n множества. Обозначим искомое число через P(n,r), иногда это число обозначают $P_n^r$ или $P_{n,r}$.

Задача определения P(n,r) сводится к последовательному применению правила произведения. Действительно, в n-множестве имеется n возможностей для выбора первого элемента r-перестановки. Как только такой выбор сделан, остается n-1 возможностей для выбора второго элемента, затем n-2 возможностей для выбора третьего элемента и т.д., для выбора r-ого элемента будет n-r+1 возможностей. По правилу произведения получим:

$P_{n,r} = n(n-1)...(n-r+1)$

Очевидно, что имеем:

$P_{n,n} = n!$

Для полноты будем считать, что

$P_{n,0} = 0!=1$

Подсчитаем теперь число P возможных r-перестановок с повторениями. В этом случае после выбора любого элемента r-перестановки остаются все те же n-возможностей для выбора следующего элемента. Следовательно, по правилу произведения, число r-перестановок с повторениями из n-множества равно

$P=n^r$

Подсчитаем теперь число r-сочетаний (без повторений). Обозначим число r-сочетаний (без повторений) через С(n,r), или $C_n^r$

r-сочетание (а1, а2,…, аr), аi∈А не зависит от порядка написания элементов, в то время как в r-перестановках в зависимости от порядка элементов получаем различные r-перестановки. Так как P(r,r)=r!, то

$C_n^r=\frac{P(n,r)}{r!}=\frac{n(n-1)...(n-r+1)}{r!}=\frac{n!}{r!(n-r)!}$

Итак, имеем:

$C_n^r=\frac{n!}{r!(n-r)!}$

Определим число r-сочетаний с повторениями. Пусть элементы множества А занумерованы числами 1,2,…,n. Тогда вместо r-сочетаний с повторениями из множества А будем рассматривать соответствующие им (взаимно однозначно) r-сочетания с повторениями из множества$A^*=\{1,2...n\}$. Так как в сочетаниях порядок элементов несущественен, всякое r-сочетание из А* можно записать в виде

$(k_1, k_2,…, k_r), 1≤ k_i ≤ n$

где $k_1, k_2,…, k_r$ (равенство имеет место, когда есть повторяющиеся элементы). r-сочетанию (4.4) с повторениями поставим в соответствие r выборку:

$(k_1+0, k_1+1, k_2+2,…, k_r+r-1), $

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

Это соответствие, как легко видеть, взаимно однозначное и при этом r выборка (4.5) является r-сочетанием без повторений из множества 1, 2,…, n, n+1, n+2,…, n+r-1. Таким образом, число r-сочетаний с повторениями из n множества равно числу $C_{n+r-1}^r$

Свойства чисел $C_n^r$. По определению чисел $C_n^r$ получим, что (по определению 0!=1):

$C_n^n=1$

$C_n^0=1$

$C_n^r=\frac{n!}{r!(n-r)!}=C_n^{n-r}$

Последнее свойство называется правилом симметрии. Следующее соотношение называется правилом Паскаля:

$C_n^r=C_{n-1}^r+C_{n-1}^{r-1}$

Докажем это правило. Из определения чисел $C_n^r$ имеем:

$C_{n-1}^r+C_{n-1}^{r-1}=\frac{(n-1)}{r!(n-1-r)!}+\frac{(n-1)}{(r-1)!(n-1-r+1)}=$

$\frac{(n-r)(n-1)!+r(n-1)!}{r!(n-1)!}=\frac{n!}{r!(n-r)!}=C_n^r$

что и требовалось.

Используя формулу Стирлинга:

$n!=\sqrt{2πn}\dbinom{n}{e}^n (1+0(1/n))$

можно получить следующую оценку чисел $C_n^r$

$\dbinom{n}{r}^r ≤ C_n^r ≤ \dbinom{en}{r}^r$