Пример 37. Доказать равенство

Пусть множество M имеет n элементов. Каждому его подмножеству A мощности k взаимно однозначно соответствует его дополнение M \ A, состоящее в точности из тех (n – k) элементов, которые не входят в A. Наличие этого взаимно однозначного соответствия и доказывает равенство.

Пример 38. Доказать равенство

Равенство очевидно, если вспомнить, что количество частей n элементного множества равно 2ⁿ (см. пример 33).

Равенство (*) из примера 39 не столь очевидно.

Пример 39. Доказать равенство

Постараемся доказать равенство (*) как можно нагляднее. Возьмём множество M, имеющее 2n элементов, произвольно отберём из него n элементов и назовём их «белыми»; остальные n элементов назовём «чёрными». Каждое подмножество K множества M, содержащее n элементов, есть объединение двух частей – «белой» части A, состоящей только из «белых» элементов, и «чёрной» части B, состоящей только из «чёрных» элементов: K = A ∪ B. Число элементов в каждой из этих частей может варьироваться от 0 до n. Приготовим n + 1 «комнату», на которых выставим номера от 0 до n. Все подмножества мощности n множества M распределим по этим «комнатам», соблюдая следующее правило: в «комнату» с номером k помещаются те подмножества, число «белых» элементов в которых равно k. В каждой «комнате» поставим «столов» и подмножества, попавшие в эту «комнату», распределим по этим «столам». Число «белых» подмножеств мощности k множества M, т. е. подмножеств, содержащих k «белых» элементов и ноль «чёрных», равно т. е. числу «столов». Для каждого такого «белого» подмножества взаимно однозначно выберем свой «стол». На этом «столе» располагаются подмножества мощности n множества M, у которых «белая» часть уже фиксирована, а «чёрная» часть варьируется. «Белая» часть имеет мощность k. «Чёрной» частью может быть любое множество мощности (n – k), элементы которого выбраны из n «чёрных» элементов, присутствующих в M. Так что для заданного стола число возможных «чёрных» частей есть Столько же подмножеств множества M лежит на нашем «столе». Итак, в «комнате» «столов», а на каждом из них подмножеств. Значит, в «комнате» подмножеств. Осталось вспомнить равенство из примера 37 и сложить количества подмножеств по всем «комнатам», чтобы получить общее количество n элементных подмножеств множества M в виде левой части равенства (*). А в правой части стоит символ, по определению выражающий это количество. Пример 40. Доказать равенство В множестве мощности (n + 1) выделим какой-то элемент. Совокупность k элементных подмножеств этого множества распадается на два класса: содержащих элемент и не содержащих выделенного элемента Пример 41. Доказать равенство