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

Заметим, что в нашем примере, где n = 6 и k = 3, мы могли сначала выбрать, например, первую позицию, затем – четвертую и наконец – пятую, а могли сперва выбрать четвертую позицию, затем – пятую и лишь в конце – первую. И для каждого из подобных вариантов у нас получится одно и то же кодовое слово 100110. Сколько же раз в нашей формуле n (n − 1) (n − 2) × … × (n − k + 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) × … × (n − k + 1), потом сообразили, что в ней каждое множество позиций для единиц учтено k! раз. Это означает, что искомое количество кодовых слов равно

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

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

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

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

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

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

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

Случай 1. Все три канала связи доступны. Соответствующая вероятность равна

Вероятности перемножаются потому, что каналы независимы друг от друга. Допустим, у нас тысяча мини-сетей и p = 0,6. Тогда примерно в 600 из них будет доступен канал 1–2. Поскольку доступность канала 1–2 никак не влияет на канал 1–3, из нашей 1000 сетей оба канала 1–2 и 1–3 будут доступны в среднем 600 × 0,6 = 360 случаев. Чтобы вычислить среднее количество сетей, в которых доступны все три канала, надо взять долю 0,6 от 360, получаем 360 × 0,6 = 216. В результате вероятность доступности всех трех каналов равна

Случай 2. Два канала связи доступны и один недоступен. Недоступным может быть любой из трех каналов связи, поэтому случай 2 можно получить тремя разными способами. В результате соответствующая вероятность равна

Общая вероятность сохранения связи в сети теперь равна

(П.3) + (П.4) =p³ + 3p² (1 −p) = 3p² −2p³.

Потеря связи хотя бы с одним из компьютеров тоже происходит в двух случаях, которые мы назовем случай 3 и случай 4.

Случай 3. Два канала связи недоступны и один доступен. Заметьте, что этот случай совершенно аналогичен случаю 2, только р и (1 − p) поменялись местами. Соответствующая вероятность равна

3 (p − 1)²p. (П.5)

Случай 4. Все три канала связи недоступны. Этот случай опять же аналогичен случаю 1, если поменять местами р и (1 − p). Соответствующая вероятность равна

(1 −p)³. (П.6)

Вероятность, что хотя бы один компьютер окажется отрезанным от сети, равна

(П.5) + (П.6) = 3(1 −p)² − 2(1 −p)³. (П.7)

Естественно, если просуммировать все вероятности, то получится единица. Это очень красиво следует из бинома Ньютона третьей степени:

(П.3) + (П.4) + (П.5) + (П.6) =p³ + 3p² (1 −p) + 3(p − 1)²p + (1 −p)³ = (p + (1 −p))³ = 1³ = 1

Если провести еще немножко алгебраических манипуляций, то можно переписать вероятность (П.7) по-другому:

3(1 −p)² − 2(1 −p)³ = (1 −p)² (3 − 2(1 −p)) = (1 −p)² (1 + 2p) = (1 −p) ((1 −p) (1 + 2p)) = (1 −p) (1 +p − 2p²)

Легко проверить, что если p > ½, то вторая скобка меньше единицы. Получается, что если p > ½, то вероятность потери связи в мини-сети меньше, чем вероятность потери связи в отдельно взятом канале, которая равна (1 − p).