Книга Кому нужна математика? Понятная книга о том, как устроен цифровой мир, страница 34. Автор книги Нелли Литвак, Андрей Райгородский

Разделитель для чтения книг в онлайн библиотеке

Онлайн книга «Кому нужна математика? Понятная книга о том, как устроен цифровой мир»

Cтраница 34

Число сочетаний вычисляется по формуле


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Мы приводим вывод этой известной формулы ниже, в приложении 3. Легко проверить, скажем, что n, и действительно мы можем выбрать одну позицию из n ровно n способами.

Значит, всего внутри шара


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

слов. Здесь слагаемое C0n=1 – это число слов, отстоящих от центра на расстояние 0. Такое слово только одно – сам центр. Поскольку шары с центрами в кодовых словах попарно не пересекаются, то всего в них находится


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

различных слов. Но это количество заведомо не превосходит числа всех возможных кодовых слов, которое, как мы уже знаем, равно 2n. Таким образом,


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Эта формула и есть граница Хэмминга. В нашем примере, когда n = 10, d = 2, получаем


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Всего последовательностей длины 10 ровно 210 = 1024. Получается, что максимальное количество кодовых слов не превышает 1024 ÷ 56 ≈ 18,2857. Поскольку число кодовых слов целое, оно не больше 18.

3. Число сочетаний из n по k

Мы рассмотрим число сочетаний на примере, связанном с кодированием. Давайте попробуем сосчитать, сколько существует слов длины n и веса k, kn. Напомним, что слово – это запись из нулей и единиц, а его вес – это количество единиц. Значит, нам нужно выбрать из n позиций k штук для расстановки на этих k выбранных позициях единиц. При этом ясно, что как только позиции будут выбраны, кодовое слово определяется однозначно. Выбрали, скажем, из шести позиций первую, четвертую и пятую – все, появилось кодовое слово 100110.

Хорошо, допустим, есть n позиций. Выбираем из них любую. Это можно сделать n способами. Для каждого из этих n способов выбора первой позиции из оставшихся n − 1 позиций снова выбираем любую. Для этого уже есть только n − 1 вариант. Итого количество способов зафиксировать первую и вторую позиции для единиц равно n (n − 1). Точно так же три позиции можно последовательно выбрать одним из n (n − 1) (n − 2) способов. И так далее. Для данного k будет всего


n (n − 1) (n − 2) × … × (n k + 1)


вариантов. Это и есть ответ? Не совсем!

Заметим, что в нашем примере, где n = 6 и k = 3, мы могли сначала выбрать, например, первую позицию, затем – четвертую и наконец – пятую, а могли сперва выбрать четвертую позицию, затем – пятую и лишь в конце – первую. И для каждого из подобных вариантов у нас получится одно и то же кодовое слово 100110. Сколько же раз в нашей формуле n (n − 1) (n − 2) × … × (nk + 1) мы тем самым посчитали одно и то же кодовое слово? Смотрите, получая эту формулу, мы выбирали какие-то последовательности номеров позиций: допустим, это были 1-4-5, 1-5-4, 5-1-4, 5-4-1, 4-1-5, 4-5-1. Видно, что все эти последовательности дают одно и то же слово из нулей и единиц. И видно, что их 6. Чтобы снова прийти к этому выводу не путем унылого перебора (которым мы сейчас занимались), а «весело и с умом», надо рассудить так: из трех чисел 1, 4, 5 мы можем сначала выбрать любое (3 варианта); затем вслед за ним расположить второе уже только одним из двух способов, а третье выбирается однозначно. Рассуждение дает нужный результат: число способов упорядочить числа 1, 4, 5 равно 3 × 2 × 1 = 6. Аналогично для любого k возникает формула k (k − 1) × … × 2 × 1 = k!. Напомним: по принятой в математике конвенции 0! = 1.

Что же мы имеем в итоге? Сначала мы вывели формулу n (n − 1) (n − 2) × … × (nk + 1), потом сообразили, что в ней каждое множество позиций для единиц учтено k! раз. Это означает, что искомое количество кодовых слов равно


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Заметим, что найденное выражение можно переписать в виде


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Это так называемое число сочетаний из n по k, или биномиальный коэффициент. В настоящее время для него приняты два обозначения:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Назад к Главе 3

Приложения к главе 4

В качестве дополнительного материала к этой главе рекомендуем книгу Андрея «Модели случайных графов» {33} . Там в подробностях приводится доказательство теоремы Эрдеша – Реньи и много других интересных результатов из теории случайных графов.

1. Вероятность потери связи в мини-сети

Рассмотрим мини-сеть как в примере, приведенном в главе: три компьютера – 1, 2, 3 и три канала связи: 1–2, 1–3, 2–3. Допустим, что канал связи доступен с вероятностью р и недоступен с вероятностью 1 − p, где 0 < p < 1. Предположим, что каналы независимы друг от друга. Связь между всеми тремя компьютерами сохраняется в двух случаях.

Вход
Поиск по сайту
Ищем:
Календарь
Навигация