Ч исла называются полиномиальными коэффициентами. Cформулируем следующее правило.

Число различных перестановок, которые можно составить из n элементов, среди которых имеется n₁ элементов типа a_1, n₂ элементов типа a_2, …, n_k элементов типа a_k равно:

Сочетания с повторениями

Сочетаниями из n элементов по k элементов с повторениями называются кортежи,

содержащие k элементов, причём каждый элемент принадлежит к одному из n типов. Число таких сочетаний обозначается Например, из трёх элементов a,b,c можно составить такие сочетания по два с повтореними (n =3, k =2):

aa,ac,bc,ab,bb,cc.

Поставим в соответствие каждому приведённому кортежу (сочетанию) последовательность

из нулей и единиц, придерживаясь такого правила: пишется подряд столько единиц,сколько элементов первого типа входит в данный кортеж, далее ставим нуль и после него записываем столько единиц, сколько элементов второго типа содержит этот кортеж и т.д. Таким образом нулями отделяем единицы, соответствующие элементам одного типа, а также нули означают отсутствие в кортеже элементов других типов. Сумма единиц равна k. Записанным выше кортежам соответствуют такие последовательности:

1100,1001,0101,1010,0110,0011.

Т аким образом, каждому сочетанию из n по k соответствует последовательность из k единиц и n-1 нулей. По полученным последовательностям также можно однозначно восстановить сочетания. Число перестановок из k единиц и n-1 нулей, а это и есть число сочетаний с повторениями, равно:

Э ту же формулу, пользуясь свойствами сочетаний, можно записать в виде:

Сочетания без повторений

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

Для вывода формулы, определяющей число сочетаний, воспользуемся примером. Из множества (a,b,c,d) образуем трёхэлементные подмножества, отличающиеся друг от друга составом элементов и запишем их в левой части таблицы, а в правой части все перестановки каждого сочетания:

Сочетания	Перестановки
abc	abc, acb, bac, bca, cab, cba
abd	abd, adb, bad, bda, dab, dba
acd	acd, adc, cad, cda, dac, dca
bcd	bcd, bdc, cbd, cdb, dbc, dcb

Видно, что каждому сочетанию соответствует шесть перестановок. Действительно, Р₃=3!=6, т.е. любое трёхэлементное подмножество можно переставить 3! способами. В результате получаем 24 размещения. Отсюда можно для данного примера записать соотношение: или

О бобщая данное рассуждение, можно найти общую формулу числа сочетаний из n различных элементов по k:

Р азделив обе части равенства на P_k,получим: