Математика 9 класс 9-М-7

§6. Треугольник Паскаля

Вернёмся к арифметическим свойствам количеств сочетаний и докажем свойство 2: Cn+1k+1=Cnk+1+CnkC_{n+1}^{k+1} = C_n^{k+1} + C_n^k, если 0k+1n0 \leq k + 1 \leq n. Действительно,

Cnk+1+Cnk=n!(k+1)!(n-k-1)!+n!k!(n-k)!=n!((n-k)+(k+1))(k+1)!(n-k)!=C_n^{k+1} + C_n^k = \dfrac{n!}{(k+1)!(n-k-1)!}+\dfrac{n!}{k!(n-k)!} = \dfrac{n!( (n-k) + (k+1) )}{(k+1)!(n-k)!}=

=(n+1)!(k+1)!(n-k)!=Cn+1k+1=\dfrac{(n+1)!}{(k+1)!(n-k)!} = C_{n+1}^{k+1}.

Это свойство можно доказать также из комбинаторных соображений. Пусть у нас есть n+1n + 1 белых шариков, из которых надо выбрать k +1k + 1. Это можно сделать Cn+1k+1C_{n+1}^{k+1} способами. Теперь покрасим один из шариков в чёрный цвет. Среди выбранных шариков либо есть шарик чёрного цвета, либо его нет.

Выбрать k+1k + 1 шарик, среди которых есть чёрный – значит выбрать чёрный шарик и оставшиеся kk белых шариков из nn, т. е. CnkC_n^k. Выбрать k +1k + 1 шарик, среди которых нет чёрного шарика – значит выбрать k +1k + 1 шарик только из множества белых шариков, которых nn штук, т. е. Cnk+1C_n^{k+1}. По правилу суммы получаем, Cn+1k+1=Cnk+1+CnkC_{n+1}^{k+1} = C_n^{k+1} + C_n^k.

Свойство 2 позволяет нам расположить все числа CnkC_n^k в виде бесконечной таблицы, которая называется треугольником Паскаля:

или, численно:

Т. к. Cn+1k+1=Cnk+1+CnkC_{n+1}^{k+1} = C_n^{k+1} + C_n^k, то в треугольнике Паскаля каждое число (кроме крайних) равно сумме двух чисел, стоящих непосредственно выше данного числа. Так, например, число 6 из строки 4 равняется сумме двух троек, непосредственно стоящих над ним, т. к. C42=C31+C32C_4^2 = C_3^1 + C_3^2. Можно сказать, что крайние числа, равные единицам, тоже удовлетворяют этому свойству, т. к. непосредственно выше них находится только одна единица.

Теперь перейдём к свойству 3: Cn0+Cn1+Cn2++Cnn =2nC_n^0 + C_n^1 + C_n^2 + \: ⋯ \: + C_n^n = 2^n. Это свойство можно записать короче, используя знак математической суммы:

Данная запись означает, что мы должны выписать все слагаемые вида CniC_n^i, где ii принимает целые значения от нуля (i=0i = 0 под знаком суммы) до nn (над знаком суммы), само же nn во всех выписанных слагаемых остаётся постоянным. Затем все выписанные слагаемые нужно сложить.

Приведём три способа доказательства свойства 3.

Первый способ основан на использовании треугольника Паскаля. Положим,

Sn= Cn0+Cn1+Cn2++CnnS_n = C_n^0 + C_n^1 + C_n^2 + \: ⋯ \: + C_n^n.

Всякое Cn1kC_{n−1}^k из строки (n1n − 1) входит в строку nn в качестве слагаемого два раза – в CnkC_n^k и Cnk+1C_n^{k+1}. Следовательно, Sn=2Sn1=22Sn2= = 2nS0=2nS_n = 2S_{n−1} = 2^2S_{n−2} =  \: ⋯ \: = 2^n S_0 = 2^n, т. к. S0=1S_0 = 1.

Второй способ доказательства – комбинаторный. Вернёмся к примеру 15 в конце §4.

При решении данного примера с помощью применения правила произведения был получен ответ: 2n2^n. Решим теперь данный пример, применив правило суммы.

Пример 15*

Найти число подмножеств множества AA, состоящего из nn элементов.

Решение

Заметим, что все подмножества nn-элементного множества можно разбить на (n+1n + 1) группу по количеству элементов в данном подмножестве (от 0 до nn).

Рассмотрим одну из таких групп, которая содержит все подмножества из kk элементов. Количество подмножеств из kk элементов равно числу неупорядоченных наборов (сочетаний) из nn по kk, т. е. CnkC_n^k. Однако, мы уже знаем, что число подмножеств равно 2n2^n.

Таким образом, по правилу суммы, получаем:

Cn0+Cn1+Cn2++Cnn =2nC_n^0 + C_n^1 + C_n^2 + \: ⋯ \: + C_n^n = 2^n.

Третий способ доказательства основывается на применении бинома Ньютона.