Пример 34. Пусть в алфавите s букв. Сколько в этом алфавите слов длины n?
Рассуждаем как в примере 32. Удлинение на одну букву приводит к увеличению количества слов в s раз. Начиная со слов длины 0, количество коих есть 1, приходим к выводу, что количество слов длины n равно sn.
Пример 35. Дан список из n слов длины n в каком-то алфавите. Как указать слово в том же алфавите, не входящее в заданный список?
Решение проиллюстрируем на частном случае. В качестве алфавита возьмём двухбуквенный алфавит {0; 1}, а список такой: 00100100100; 01011011010; 10011011001; 01111011101; 11001010110; 11111111111; 11010001000; 11001000100; 00000000000; 10101010101; 01010101010. Расположим слова списка одно под другим, так чтобы получилась квадратная таблица:
По идущей от верхнего левого угла диагонали этой квадратной таблицы стоит слово 01011100000. Поменяв в нём все цифры, получим 10100011111, что отличается от всех строк (а заодно и всех столбцов). В самом деле, это слово не может совпасть ни с пятой, скажем, строкой, потому что на пятом месте в этом слове стоит ноль, тогда как в пятой строке на пятом месте стоит единица, ни с десятой строкой, где на десятом месте в этом слове стоит единица, а в десятой строке на этом месте стоит ноль, и вообще ни с одной из строк таблицы.
Изложенный метод иногда называют диагональным, или методом канторовской диагонали. В 1891 г. он впервые был применён в статье Кантора. Это было сделано для доказательства того, что натуральный ряд N и множество Ω всех бесконечных двоичных (т. е. составленных из ноля и единицы) последовательностей обладают различными количествами элементов. Диагональный метод успешно используется при доказательстве некоторых важнейших теорем математики.
Пример 36 (Кантор). Доказать, что множества Ω и N имеют различное количество элементов.
Для этого мы должны установить невозможность взаимно однозначного соответствия между указанными множествами. Рассуждаем от противного. Пусть такое соответствие возможно. Тогда бесконечные двоичные последовательности, из которых состоит множество Ω, можно занумеровать натуральными числами: первая, вторая, третья и т. д. Расположим эти последовательности друг под другом. Возможный вариант такого расположения показан ниже.
Естественно возникает бесконечная диагональная последовательность: в ней на первом месте стоит первый член первой последовательности, на втором – второй член второй последовательности, …, на сотом – сотый член сотой последовательности и т. д. Для показанного варианта диагональная последовательность будет иметь вид 0101110000… Меняем в ней все члены и получаем бесконечную последовательность 1010001111 …, которая отсутствует в нашем перечне в силу причин, изложенных в примере 35. Стало быть, наше предположение, что мы пронумеровали все двоичные бесконечные последовательности, оказалось ложным.
§ 9. Задачи из элементарной комбинаторики
Выражение (читается «цэ из n по k») означает количество k-элементных частей n-элементного множества или, в более современной терминологии, количество частей мощности k множества мощности n.
Пример 37. Доказать равенство
Пусть множество M имеет n элементов. Каждому его подмножеству A мощности k взаимно однозначно соответствует его дополнение M \ A, состоящее в точности из тех (n – k) элементов, которые не входят в A. Наличие этого взаимно однозначного соответствия и доказывает равенство.
Пример 38. Доказать равенство
Равенство очевидно, если вспомнить, что количество частей n элементного множества равно 2n (см. пример 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. Доказать равенство
Для доказательства полезно привлечь так называемые биномиальные коэффициенты.
Биномиальные коэффициенты – это коэффициенты разложения бинома (1 + x)n по возрастающим степеням x:
Из выписанной формулы видно, как они обозначаются. Если в этой формуле положить x = –1, то получим:
Только что полученная формула очень похожа на равенство, которое требовалось доказать. И это не случайно. Дело в том, что биномиальный коэффициент и количество подмножеств – это одно и то же число.
Пример 42. Доказать равенство
Мы наметим лишь план доказательства. Сначала равенство проверяется для случаев k = 0 и k = n. Затем доказывается равенство, аналогичное равенству из примера 40:
Доказать это равенство чрезвычайно просто. Надо рассмотреть два способа записи разложения степени бинома (1 + x)n+1 по возрастающим степеням x. Первый способ – стандартный, с использованием коэффициентов
Второй способ таков: возводим (1 + x) в степень n, располагаем по степеням x с использованием коэффициентов а затем это разложение умножаем на (1 + x) и развёртываем в многочлен. Если теперь приравнять коэффициенты при одинаковых степенях переменной, то получим равенство (****). Далее, для получения равенства (***) рассуждаем по индукции.
Этому рассуждению можно придать легко запоминающуюся форму. Рассмотрим так называемый треугольник Паскаля:
По краям стоят единицы, а каждое другое число равно сумме двух его «соседей» из предыдущей строки. Таблица неограниченно продолжается вниз. Занумеруем строки, считая верхнюю строку (из одной единицы) нулевой. Таким образом, первая строка – это 11, вторая – 121 и т. д. Аналогично нумеруем числа в каждой строке: самая левая единица получает номер ноль, за ней следует число номер один и т. д. Например, третье число в шестой строке – это 20.
Наше доказательство равенства можно теперь сформулировать так: числа равны потому, что каждое из них есть k-е число в n-й строке треугольника Паскаля.
§ 10. Счётные и несчётные множества
Прежде всего не станем уподобляться свифтовским остроконечникам и тупоконечникам, готовым воевать с теми, кто при поедании яиц разбивает их не с того конца. Признаем, что ноль можно считать, а можно и не считать натуральным числом. Потому что на самом деле есть два понятия натурального числа: количественное, возникающее при исследовании количества элементов в множестве, и считательное, возникающее при пересчёте элементов этого множества, при условии, что таковые существуют[141]. Из сказанного ясно, что наименьшее количественное натуральное число есть ноль; это количество элементов в пустом множестве. Наименьшее считательное натуральное число есть единица, потому что с неё начинается любой пересчёт. Сообразно этому есть два натуральных ряда – количественный, начинающийся с ноля, и считательный, начинающийся с единицы. Между ними нетрудно установить взаимно однозначное соответствие:
К сожалению, оба натуральных ряда претендуют на обозначение N. Это не слишком страшно, потому что из контекста ясно, какой из двух натуральных рядов имеется в виду. В этом параграфе натуральный ряд начинается с единицы.
Множество называется счётным, если между ним и натуральным рядом можно установить взаимно однозначное соответствие. Например, множество всех целых чисел счётно, как показывает бесконечная таблица из двух строк:
В первой строке в некотором порядке выписаны все целые числа, во второй – соответствующие им члены натурального ряда. Ясно, что между любыми двумя счётными множествами можно установить взаимно однозначное соответствие (хотя бы через промежуточное соответствие каждого из них с натуральным рядом). Поэтому все счётные множества имеют одинаковую мощность или одинаковое количество элементов – столько же, сколько их содержится в натуральном ряду, т. е. столько же, сколько существует натуральных чисел.
