Биноминальные коэффициенты

С_n^k (число сочетаний) - это число способов выбрать k различных (т.е. без повторений) предметов из n различных (0<= k <= n), без учета порядка выбора. Они могут быть вычислены по следующим формулам:

Треугольник Паскаля и Бином Ньютона:

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

C_n+1^k+1=C_n^k+C_n^k+1.

Давайте построим из чисел два бесконечных треугольника. В первом из них (см. рис. внизу слева) будем ставить единицы в самом верху и по краям каждом следующей строки, а каждое из остальных чисел будет равно сумме двух стоящих над ним слева и справа (этот треугольник называется треугольником Паскаля). Во втором (см. рис. внизу справа) будем последовательно выписывать значения C_n^k, отводя по одной строке для каждого значения n и располагая в ней C_n^k по возрастанию k. На самом деле эти треугольники одинаковы. Равенство первых нескольких строчек, можно заметить, а дальше надо уже доказывать.

				C00
			C10		C11
		C20		C21		C22
	C30		C31		C32		C33
C40		C41		C42		C43		C44

Утверждение. Если строчки треугольника Паскаля и позиции в них нумеровать, начиная с нуля, то на k-м месте в n-й строке будет стоять значение C_n^k (основное свойство треугольника Паскаля).

Доказательство: Индукция по n (см. лекцию "Индукция", если вы еще не знакомы с этим методом).

База: n =0 - действительно, C₀⁰ =1 - как раз то, что стоит на верхушке треугольника Паскаля.

Переход: от n к n+1. Пусть в n-й строчке все числа уже равны значениям C_n^k из n по соответствующим k. Рассмотрим n+1 -ю строчку. На ее краях (нулевое и n+1 -е места) стоят две единицы - и значения C_n+1⁰ и C_n+1ⁿ⁺¹ как раз равны 1. Далее, при всех k от 1 до n число, стоящее на k -м месте в n+1-й строке, равно сумме чисел, стоящих в n-й строке на k-1 -м и k -м местах соответственно (т.е. как раз двух стоящих над ним - по принципу построения треугольника Паскаля). По предположению индукции, они равны C_n^k-1 и C_n^k, а их сумма тогда будет C_n^k-1+C_n^k, что как раз равно C_n+1^k, ч.т.д.

Для справки мы приводим здесь первые 11 строчек (с нулевой по 10-ю) треугольника Паскаля - их можно посчитать и вручную. На компьютере, с помощью простой программы, можно вычислить значительно больше, и более быстрого алгоритма, чем треугольник Паскаля, пока не существует.

Такие, казалось бы, чисто комбинаторные вещи, как числа C_n^k и треугольник Паскаля, неожиданно встречаются и в алгебре. Выпишем известные формулы сокращенного умножения:

(a+b)0= (a+b)1= (a+b)2= (a+b)3=

1 a+b a2+2ab+b2 a3+3a2b+3ab2+b3

Коэффициенты в этих формулах (и это лучше видно, когда выписаны еще нулевая и первая степень) - это числа из треугольника Паскаля, то есть C_n^k. На самом деле, такая закономерность будет продолжаться и дальше, и называется она бином Ньютона. Точнее:

(a+b)ⁿ=aⁿ+C_n¹a^n-1b+C_n²a^n-2b²+...+C_n^n-1a¹b^n-1+bⁿ.

Можно доказать эту формулу по индукции, как и основное свойство треугольника Паскаля. Приведем более простое объяснение:

(a+b)ⁿ=(a+b)(a+b)...(a+b) (n скобок). Раскрывая скобки, получаем в отдельных слагаемых произведения n букв, каждая из которых - a или b, т.е. a^n-kb^k при каком-то k от 0 до n. Докажем, что для каждого такого k число таких слагаемых - ровно C_n^k, откуда, приведя подобные, и получаем формулу бинома. Но это правда: a^n-kb^k получается путем взятия a из k скобок и b из n-k оставшихся; разные такие слагаемые получаются путем разного выбора этих самых k скобок, а k скобок из n можно выбрать как раз C_n^k способами, ч.т.д.

Именно из-за бинома Ньютона числа C_n^k часто называют биномиальными коэффициентами.