Теорема 1.

Над алфавитом мощностью m можно создать ровно mⁿ слов длиною n.

Доказательство:

Воспользуемся методом полной математической индукции. Пусть - элементы (буквы) алфавита мощностью . Из этого алфавита можно создать слов длиной 1. Такими словами будут буквы этого алфавита. Для данное утверждение является правильным .

Допустим, что данное утверждение является правильным для , и покажем, что тогда оно выполняется и для . Предположим, число длины равняется . Чтобы создать все возможные слова длины , достаточно к каждому слову длины добавить в его конце последовательно каждую из букв алфавита. Таким образом, из каждого слова длины образуется разных слов длины . Таким образом, получаем все возможные слова длиною . Поскольку слов длиной является , то общее количество слов длиной будет . Таким образом, предположив истинность утверждения для , доказано, что оно является правильным для . Теорема доказана.

 

Пример 1.

Какой является мощность алфавита, с помощью которого записано сообщение, которое содержит 5120 символов, если его информационный объем составляет 2,5Кб?

1. Переведем информационный объем сообщения в биты:

.

2. Определим количество битов, которые приходятся на один символ:

.

3. Определяем мощность алфавита по теореме 1: