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

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

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

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

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

Число различных перестановок элементов «-множества равно А» = «!.

Упорядоченную выборку с возвращением размера к называют размещением с повторениями (словом длины к в алфавите порядка «). По правилу произведения число размещений размера k с повторениями (обозначается А^к) равно.

Неупорядоченную выборку без возвращения размера к называют сочетанием из п по к (сочетанием к элементов «-множества). Число сочетаний из п по к (обозначают С^к или) равно.

k)

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

Заметим, что при расчетах полагается: А° =Cfj =Cfj = 0! = 1 и А" ' = С" ¹ = О при п<�т.

Числа С^к называют биномиальными коэффициентами, они используются в формуле бинома Ньютона, где для элементов а и b определено сложение и умножение:

При расчетах нередко используют следующие соотношения:

• 1) свойство симметрии: С^к = С" ^-*, 0 < k < и;
• 2) рекуррентное соотношение: С^к = С*_, + C^k_nz,

П

3) сумма биномиальных коэффициентов:? С'_г = 2″ ;

к=о

П

4) знакопеременная сумма биномиальных коэффициентов:? (~)^кС^к =0;

к=0

L"^/2J.

5) сумма четных (нечетных) биномиальных коэффициентов:? С" =.

.. Ы).

L"/2J.

= X C²ⁱ⁺¹ = 2−1;

к=0

n

6) свертка Вандермонда и ее следствие:? С*_пС^~* = С%_+т> 0.

/=о.

• ?(Ф2=С?|.
• *=0

Свойство симметрии и рекуррентное соотношение следуют из равенства (1.3). Сумма биномиальных коэффициентов следует из бинома Ньютона (1.5) при a-b- 1. Знакопеременная сумма следует из (1.5) при b = -а = 1. Сумма четных (нечетных) биномиальных коэффициентов получается как полусумма (полуразность) 3-го и 4-го соотношений. Свертка Вандермонда следует из тождества многочленов (х -г )^п(х + 1)^{, 7/}= (х + )^п+т и бинома Ньютона. Следствие свертки Вандермонда получается при n = m = k.