Сочетания

Из m -элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и теми же элементами, расположенными в разном порядке считаются равными. Такие размещения называются сочетаниями и обозначаются (англ. combination)

Сочетание отличается от размещения тем, что в нем не учитывается порядок. Поэтому каждому сочетанию соответствует k! размещений.

Сочетания из m подмножеств n- элементного множества, на элементах которых задан линейный порядок, называются размещениями.

A_n^m = m!C_n^m

Число строго монотонно возрастающих функций, или число размещений n неразличимых предметов по m ящикам не более чем по одному в ящик, т.е. число способов выбрать из m ящиков n ящиков с предметами, называется числом сочетаний и обозначается , или , или . Число сочетаний из m по n в раз, т.е.

Теорема.

Доказательство.

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

2. Число сочетаний является числом строго монотонно возрастающих функций, потому что строго монотонно возрастающая функция определяется набором своих значений, причем .

Другими словами, каждая монотонно возрастающая функция определяется выбором n чисел из диапазона 1… m. Таким образом, число строго монотонно возрастающих функций равно числу n- элементных подмножеств m- элементного множества, которое, в свою очередь, равно числу способов выбрать n ящиков с предметами из m ящиков.

По определению = 0 при n > m.

Из этой формулы непосредственно вытекает, что ; ;

Задание

Доказать, что

1. , где

Доказательство.

2.

Доказательство.