Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

Задачи и дополнения

1. Часто по разным соображениям для кодирования сообщений используют не все последовательности в данном алфавите, а только некоторые из них, удовлетворяющие тем или иным ограничениям. Будем рассматривать, например, n-буквенные двоичные слова с фиксированным числом t единиц (или, как говорят, слова постоянного веса t). Сколько всего таких слов - нетрудно подсчитать. Каждое из них получится, если мы выберем некоторым образом t позиций из n, и запишем в них единицы, а в остальных n-t позициях - нули. Значит, число всех слов постоянного веса совпадает с числом сочетаний из n элементов по t, т. е. равно


2. Сложнее найти число всех двоичных слов длины n, не содержащих несколько нулей подряд. Обозначим это число через sn. Очевидно, s1 = 2, а слова длины 2, удовлетворяющие нашему ограничению, таковы: 10, 01, 11, т. е. s2 = 3. Пусть α1α2 ... αn-1α1 - такое слово из n символов. Если символ αn = 1, то α1 α2 ... αn-1 может быть произвольным (n-1)-буквенным словом, не содержащим нескольких нулей подряд. Значит, число слов длины n с единицей на конце равно sn-1.

Если же символ αn = 0, то обязательно αn-1 = 1, а первые n-2 символа α1 α2 ... αn-2 могут быть произвольными с учетом рассматриваемого ограничения. Следовательно, имеется sn-2 слов длины n с нулем на конце. Таким образом, общее число интересующих нас слов равно

sn = sn-1 + sn-2.

Из полученного соотношения (подобные соотношения называют рекуррентными) легко можно найти числа sn для любого n. Поскольку s1 и s2 известны, то s3 = s1 + s2 = 5; s4 = s2 + s3 = 8, s5 = s3 + s4 = 13 и т. д. Полученная последовательность чисел

2, 3, 5, 8, 13, 21, 34, ... ,

в которой каждый последующий член равен сумме двух предыдущих, - это хорошо известный в математике ряд Фибоначчи. О многих интересных свойствах чисел Фибоначчи и их разнообразных приложениях можно прочесть в популярной брошюре [21], а также в недавно изданной книге [6]. В частности, можно убедиться (см. [21]), что n-ый член ряда Фибоначчи вычисляется по формуле:


3. Соединим оба предыдущих ограничения и найдем число двоичных слов постоянного веса t, не содержащих нескольких нулей подряд.

Рассуждать можно так. Пусть q = n-t - число нулей в рассматриваемых словах. В любом слове имеется q-1 промежутков между ближайшими нулями, в каждом из которых находится одна или несколько единиц (см. рис. 1). Предполагается, конечно, что q ≤ n/2. В противном случае (при q > n/2) нет ни одного слова без рядом стоящих нулей.

Рис. 1
Рис. 1

Если из каждого промежутка удалить ровно по одной единице, то получим слово длины n-q+1, содержащее q нулей. Легко видеть, что любое такое слов о может быть получено указанным образом из некоторого (и притом только одного) n-буквенного слова, содержащего q нулей, никакие два из которых не стоят рядом. Значит, искомое число совпадает с числом всех слов длины n-q+1, содержащих ровно q нулей, т. е. равно (см. дополнение 1).

4. Используя результаты дополнений 2, 3, убедиться в справедливости тождества:


(символ [n/2] означает наибольшее целое число, не превосходящее n/2).

5. При каком q число двоичных слов из дополнения 3 максимально?

6. Показать, что число всех n-буквенных d-ичных слов, в которых один из символов встречается фиксированное число t раз, равно Ctn(d - 1)n-t (ср. дополнение 1).

7. Обобщить результаты дополнений 2 и 3 применительно к d-ичному алфавиту.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru