1.2 Свойства

Числа C_n^k обладают рядом замечательных свойств. Эти свойства в конечном счёте выражают различные соотношения между подмножествами данного множества X. Их можно доказывать непосредственно, исходя из формулы (1), но более содержательными являются доказательства, опирающиеся на теоретико-множественные рассуждения.

1. Справедлива формула

С_n^k = С^n-k_n , (3)

Вытекающая из (1) очевидным образом. Смысл формулы (3) состоит в том, что имеется взаимно-однозначное соответствие между множеством всех k-членных подмножеств из X и множеством всех (n - k)-членных подмножеств из X: чтобы установить это соответствие, достаточно каждому k-членному подмножеству Y сопоставить его дополнение в множестве X.

2. Справедлива формула

С⁰_n + С¹_n + С²_n + … + Сⁿ_n = 2ⁿ . (4)

Поскольку сумма, стоящая в левой части, выражает собой число всех подмножеств множества X (C⁰_n есть число 0-членных подмножеств, C¹_n - число 1-членных подмножеств и т.д.), то для доказательства формулы (4) достаточно сослаться на уже известный читателю факт: число различных подмножеств n-членного множества X равно 2ⁿ.

3. При любом k, 1? k? n , справедливо равенство

C^k_n = C_n-1^k + C_n-1^k-1. (5)

Это равенство нетрудно получить с помощью формулы (1). В самом деле,

Вывод формулы (5), основанный на теоретико-множественных соображениях. Укажем, что для этого следует выделить какой-то определённый элемент а є X и все k-членные подмножества разбить на две группы: подмножества, содержащие а , и подмножества, не содержащие а.

4. Арифметический треугольник Паскаля.

Равенство (5) позволяет вычислять значения C_n^k, если известны С_n-1^k и С^k-1_n-1 . Иными словами, с помощью этого равенства можно последовательно вычислять С_n^k сначала при n = 1, затем при n = 2, n = 3 и т.д. Вычисления удобно записывать в виде треугольной таблицы:

в (n + 1) строке которой по порядку стоят числа С⁰_n, С¹_n, …, Сⁿ_n . При этом крайние числа строки, т.е. С⁰_n и Сⁿ_n , равны 1, а остальные числа находяться по формуле (5). Поскольку С^k-1_n-1 и С^k_n-1 распологаются в этой таблице строкой выше, чем число С^k_n , и находяться в этой строке слева и справа от него, то для получения числа С^k_n надо сложить находящиеся слева и справа от него числа предыдущей строки. Например, число 10 в шестой строке мы получаем, сложив числа 4 и 6 пятой строки. Указанная таблица и есть как раз "арифметический треугольник Паскаля".

5. Задача. Пусть n и k - два целых числа, при чём n > 0, k ?0. сколько существует различных строк длиной n, состоящих из букв а и b , с условием, что в каждой из этих строк буква а встречается k раз .(и, следовательно, b-n-k раз)?

Решение. Пусть (x₁, x₂, ..., x_n) - одна из строк указанного вида. Рассмотрим все номера i , такие, что x_i = а. Совокупность таких номеров является подмножеством множества М = {1, 2, …, n}, состоящим из k элементов. Обратно, если Y - любое подмножество множества М, состоящее из k элементов, то, положив x_i = а для всех i є Y и x_i = b для всех i є Y, получим строку (x₁, x₂, ..., x_n) требуемого вида. Значит, число указанных в задаче строк равно числу k-элементных подмножеств в n-элементном множестве М, т.е. равно числу С_n^k .