11. Свойства чисел C(m,n)

Числа выражающие количество -подмножеств в -множестве X, обладают целым рядом замечательных свойств. Эти свойства выражают различные соотношения между подмножествами множества Их можно доказывать, непосредственно исходя из формулы для Но более содержательными являются доказательства, опирающиеся на теоретико-множественные рассуждения.

1) Если и числа целые, то верно равенство

С помощью формулы это утверждение доказывается сразу. Действительно,

Смысл этого утверждения состоит в следующем. Каждому -подмножеству А -множества X соответствует однозначно определенное -подмножество в X, получаемое из X удалением всех элементов подмножества А. Это -подмножество называют дополнением к При этом любое -подмножество в X является дополнением одного и только одного -подмножества. Значит, существует взаимно однозначное соответствие между -подмножествами и -подмножествами, а потому число -подмножеств равно числу -подмножеств. Это утверждение и выражается равенством (1).

2) Для любого целого числа верно равенство

В самом деле, мы доказали в что общее число подмножеств -множества X равно Но любое подмножество -множества содержит элементов, где целое число, такое, что

Так как число -подмножеств в X равно то по правилу суммы общее число подмножеств -множества равно Сравнивая два получившихся значения для числа всех подмножеств в X, получаем равенство (2).

3) Для любых , таких, что верно равенство:

И это равенство нетрудно получить с помощью формулы . В самом деле, так как

и

то, подставляя эти значения в правую часть формулы (3), получаем:

Равенство (3) доказано. Отметим, что при получаем равенство Так как то следует положить Аналогично следует положить при Тогда равенство (3) оказывается верным и при

Приведем второй вывод равенства (3), вскрывающий его теоретико-множественный смысл. Выделим один из элементов -множества X, например элемент а. Тогда все -подмножества X разбиваются на два класса: первый состоит из подмножеств, не содержащих элемента а, а второй — из подмножеств, содержащих этот элемент. Но если -подмножество не содержит элемента а, то оно является подмножеством -множества X, получаемого из X удалением элемента а. Поэтому число -подмножеств первого класса равно числу -подмножеств множества X, т. е. Найдем теперь число -подмножеств второго класса. Все эти подмножества содержат элемент а. Если исключить из них этот элемент, то получатся -подмножества, не содержащие а (например, из -подмножества получится -подмножество Эти -подмножества не содержат элемента а, и потому они состоят из элементов -множества Следовательно, число подмножеств второго класса равно числу -подмножеств -множества X, т. е.

Поскольку каждое -подмножество либо содержит элемент а, либо не содержит его, оно принадлежит либо первому, либо второму классу. Значит, по правилу суммы получаем, что число всех -подмножеств в X равно Поэтому