2.2. Схемы выборок, биномиальные коэффициенты

В комбинаторике важнейшими объектами изучения являются комбинаторные схемы и конфигурации. Рассмотрим схемы выборок.

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

Число элементов выборки называется размером выборки. Размер выборки без возвращения не превышает n. Размер выборки с возвращением не ограничен. Всякую выборку размера k можно рассматривать как элемент множества X^k.

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

Упорядоченная выборка без возвращения из n-множества размера k<n называется размещением k элементов n-множества, кратко размещением из n по k (при k=n перестановкой степени n). По правилу произведения число размещений из n по k (обозначается или (n)_k) равно:

(n)_k= =n(n-1)…(n-k+1)=n!/(n-k)!. (2.1)

Число различных перестановок элементов n-множества равно n!, иначе

= n!. (2.2)

Упорядоченную выборку с возвращением из n-множества размера k называют размещением с повторениями, или словом длины k в алфавите порядка n, или последовательностью длины k над n-множеством. По правилу произведения число размещений размера k с повторениями (обозначается ) равно:

=n^k. (2.3)

Неупорядоченная выборка без возвращения из n-множества размера kn называется сочетанием k элементов n-множества, кратко сочетанием из n по k. Число сочетаний из n по k (обозначается или ) равно:

= / = n!/(n-k)!k!. (2.4)

Неупорядоченная выборка с возвращением из n-множества размера k называется сочетанием с повторениями k элементов n-множества, кратко сочетанием с повторениями из n по k. Число таких сочетаний (обозначается ) совпадает с числом разбиения строки длины n+k на n непустых отрезков. Это число равно:

= = . (2.5)

Заметим, что при расчетах полагается: = = =0!=1, и = =0 при n<m.

Числа использованы в формуле бинома Ньютона, a,bR:

(a+b)ⁿ= , (2.6)

поэтому числа называют биномиальными коэффициентами, для них верны соотношения, полезные при расчетах. Например,

• свойство симметрии: = , 0kn; (2.7)

• рекуррентное соотношение: = + ; (2.8)

• сумма биномиальных коэффициентов: =2ⁿ; (2.9)

• знакопеременная сумма биномиальных коэффициентов:

=0; (2.10)

• сумма четных (нечетных) биномиальных коэффициентов:

= =2^n-1; (2.11)

• при r=1,…,n-1 =0; (2.12)

• свертка Вандермонда, 0kn+m: = ; (2.13)

• = . (2.14)

Свойство симметрии и рекуррентное соотношение доказываются с использованием равенства (2.4). Сумма биномиальных коэффициентов следует из бинома Ньютона (2.6) при a=b=1. Знакопеременная сумма биномиальных коэффициентов следует из (2.6) при -a=b=1. Сумма четных (нечетных) биномиальных коэффициентов получается как полусумма (полуразность) равенств (2.9) и (2.10).

Равенства (2.12) получаются в результате r-кратного дифференцирования бинома Ньютона (1-x)ⁿ и подстановки значения x=1. Для доказательства свертки Вандермонда следует воспользоваться биномом Ньютона и тождеством многочленов: (x+1)ⁿ(x+1)^m=(x+1)^n+m. Равенство (2.14) следует из (2.13) при n=m=k.

Прямоугольная таблица (табл. 2.1), образованная биномиальными коэффициентами, называется треугольником Паскаля.

Таблица 2.1. Треугольник Паскаля

n	k=0	k=1	k=2	k=3	k=4	k=5	k=6	…
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
…

В комбинаторике рассматриваются и более сложные схемы выборок, в которых n-множество X состоит их элементов k>1 типов (иначе, X разбивается на k блоков). Число разбиений n-множества на k блоков мощностей n₁,…,n_k (обозначается C(n,n₁,…,n_k)) равно:

C(n,n₁,…,n_k)= … = , (2.15)

где n=n₁+…+n_k. Числа C(n,n₁,…,n_k) называются полиномиальными коэффициентами, число C(n,n₁,…,n_k) совпадает с коэффициентом при мономе в каноническом виде действительного полинома (x₁+…+x_k)ⁿ. Заметим, что C(n,n₁,n₂)= .