Апология математики (сборник статей)

Естественно возникает бесконечная диагональная последовательность: в ней на первом месте стоит первый член первой последовательности, на втором – второй член второй последовательности, …, на сотом – сотый член сотой последовательности и т. д. Для показанного варианта диагональная последовательность будет иметь вид 0101110000… Меняем в ней все члены и получаем бесконечную последовательность 1010001111 …, которая отсутствует в нашем перечне в силу причин, изложенных в примере 35. Стало быть, наше предположение, что мы пронумеровали все двоичные бесконечные последовательности, оказалось ложным.

§ 9. Задачи из элементарной комбинаторики

Выражение (читается «цэ из n по k») означает количество k-элементных частей n-элементного множества или, в более современной терминологии, количество частей мощности k множества мощности n.

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

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

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

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

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

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