Сочетания

Курс „Элементы теории вероятностей и математической статистики”

Дадим общее определение.

Число всевозможных сочетаний из n элементов по k обозначается символом C_n^k или символом \left(_k^n\right).

Таким образом, в примере 1 C_6^4=15, а в примере 2 C_4^3=4.

Попробуем выяснить, каким образом проще всего вычислить эти значения. В примере 1 выяснилось, что C_6^4=\frac{6\cdot5\cdot4\cdot3}{4!}. Расширим эту дробь на множитель 2!, тогда в числителе получится 6!. В результате получим, что C_6^4=\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{4!\cdot2!}=\frac{6!}{4!\cdot2!}. Поскольку и число 2! можно представить с помощью чисел 6 и 4 в виде (6 – 4)!, то C_6^4=\frac{6!}{4!\cdot\left(6-4\right)!}=15.

Аналогично в примере 2 получим, что C_4^3=\frac{4!}{3!\cdot\left(4-3\right)!}=\frac{4!}{3!\cdot1!}=4.

Значит, число сочетаний из n элементов по k вычисляется по формуле

Имеет место равенство

в справедливости которого можно убедиться, если записать выражения для C_n^k и C_n^{n-k}. Например, C_7^5=C_7^2=21.

Для одноэлементного множества (n = 1) можно составить лишь одно, причем одноэлементное подмножество (k = 1), т. е. единственное сочетание. Поэтому C_1^1=1. Так как такой же результат получается из формулы C_n^k=\frac{n!}{k!\cdot\left(n-k\right)!}, то 1=\frac{1!}{1!\cdot\left(1-1\right)!}, т. е. 1=\frac{1}{0!}. Но такое равенство будет возможным только в том случае, если определить

Благодаря определениям 1! = 1 и 0! = 1 приобретает значение также величина C_n^0, а именно, C_n^0=\frac{n!}{0!\cdot\left(n-0\right)!}=\frac{n!}{1\cdot n!}=1. По определению сочетаний символ C_n^0 обозначает число нульэлементных подмножеств (по существу пустое множество, всегда являющееся также подмножеством). Таких подмножеств \left\{\ \right\}=\varnothing у любого множества только одно, что согласуется и с результатом вычисления C_n^0=1.

Значения выражения C_n^k в неявном виде встречались уже в изученных в основной школе формулах:

\left(a+b\right)^1=a+b     или     \left(a+b\right)^1=C_1^0a+C_1^1b

\left(a+b\right)^2=a^2+2ab+b^2     или     \left(a+b\right)^2=C_2^0a^2+C_2^1ab+C_2^2b^2

\left(a+b\right)^3=a^3+3a^2b+3ab^2+b^3     или     \left(a+b\right)^3=C_3^0a^3+C_3^1a^2b+C_3^2ab^2+C_3^3b^3

Обобщением этих формул является формула бинома Ньютона:

Коэффициенты C_n^0, C_n^1, C_n^2, … C_n^{n-1}, C_n^n называются биномиальными коэффициентами[cноска: Бином от латинского bi – два + греческое nomos – часть, член) – двучлен.][cноска: binoom (ld bi- kaksis-, kahe + kr nomos osa, liige) − kaks­liige].

Если в формуле бинома Ньютона взять а = b = 1, то сумма всех биномиальных коэффициентов будет равна 2ⁿ, т. е.

Так как C_n^k – это число k-элементных подмножеств n-элементного множества, то отсюда следует, что число всех подмножеств n-элементного множества (включая и пустое множество) равно 2^n.

Последний треугольник Паскаля легко выписать и продолжить. На сторонах треугольника расположены единицы. Остальные числа являются суммами двух расположенных над ними чисел. Так шестой ряд образуют числа 1; 1 + 5 = 6; 5 + 10 = 15; 10 + 10 = 20; 10 + 5 = 15; 5 + 1 = 6 и 1.