5. Между двумя множествами можно установить взаимно однозначное соответствие

синонимичны. Они несут в себе одинаковый смысл.

Очевиден следующий принцип транзитивности:

если два множества равномощны третьему, то они равномощны друг другу.

(Предлагаем читателю в качестве упражнения самостоятельно сформулировать принцип транзитивности в терминах взаимно однозначных соответствий.)

Но вернёмся к примеру 33.

В силу только что сказанного частей нашего подмножества столько же, сколько цепочек плюсов и минусов длины n, а число таких цепочек, как показано в примере 32, есть 2n. Пример 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. Расположим слова списка одно под другим, так чтобы получилась квадратная таблица:

В силу только что сказанного частей нашего подмножества столько же, сколько цепочек плюсов и минусов длины n, а число таких цепочек, как показано в примере 32, есть 2ⁿ.

Пример 34. Пусть в алфавите s букв. Сколько в этом алфавите слов длины n?

Рассуждаем как в примере 32. Удлинение на одну букву приводит к увеличению количества слов в s раз. Начиная со слов длины 0, количество коих есть 1, приходим к выводу, что количество слов длины n равно sⁿ.