Теория групп и теория вероятностей
Теория групп
Рассмотрим группу вращений правильного n - угольника [4]. Порождающим элементом этой группы является перестановка:
все остальные элементы группы могут быть получены возведением последовательно в степени 2, 3, ... n этой перестановки. При этом Количество таких перестановок (а, следовательно, и число эле¬ментов группы) равно n.
Пусть теперь требуется найти число элементов группы, в которой ровно k конкретных элементов не меняют своих позиций, а остальные переставляются произвольно. Число элементов такой группы равно
Решение в этих двух случаях получено с помощью формул комбинаторики.
Теория вероятностей
Для оценки вероятности появления какого-либо дискретного события широко применяются комбинаторные методы. Приведем некоторые примеры.
а) Игрок в преферанс хочет рискнуть: объявить и сыграть "мизер". Для надежной игры ему требуется, чтобы в прикупе оказалась одна из двух семерок, например бубновая или трефовая. Он хочет оценить вероятность такого события. Вероятность события можно определить, разделив количество благоприятных вариантов на общее число возможных вариантов. Подсчитаем количество вариантов, в которых одна из указанных семерок или сразу обе окажутся в прикупе. Положим бубновую семерку в прикуп, а остальные 21 карты распределим так: по 10 карт двум игрокам и одну в прикуп. Количество комбинаций будет равно: 21!(10! 10!). Такое же количество комбинаций будет и в случае, когда в прикуп попадет трефовая семерка. Если мы сложим число вариантов в этих 2 случаях, то дважды учтем расклады, при которых обе семерки и бубновая, и трефовая попадут в прикуп, поэтому должны еще вычесть число этих вариантов. Окончательно получим число благоприятных комбинаций: 2(21!/(10! 10!) - 20!/(10! 10!) = 41 · 20!/(10! 10!). Подсчитаем теперь общее число вариантов (учитываем, что 10 карт находятся у игрока, который хочет сыграть мизер). Общее число вариантов равно: 22!/(10! 10!2!). Вероятность благоприятного события: Р= 0,177. Рискнуть можно, но шансов на успех мало.
б) Из-за недостатка времени криптоаналитак может сделать только 1000 попыток для расшифровки сообщения, ключ от которого ему неизвестен. Однако известно, что используется рюкзачный вектор, состоящий из 100 чисел, при этом сумма порождается 4 числами. Требуется оценить вероятность того, что за 1000 попыток вскрыть шифр, он это сумеет сделать.
Определим сначала общее число комбинаций, которые следовало бы перебрать криптоаналитику: = 100!/(4! 96!). Однако благоприятной комбинацией является только одна. Следовательно, вероятность вскрытия шифра за одну попытку
Р = 24/94109400 = 0,000000255.
Вероятность того, что криптоаналитик вскроет неизвестный шифр за 1000 попыток:
Р( 1000) = 1 - (1 - 0, 000000255)1000 = 0,0003.
в) Электромонтажник распаивает разъем на 8 контактов, не имея монтажной схемы, т. е. случайным образом. Определить:
1. Вероятность того, что все провода будут припаяны правильно.
2. Вероятность того, что из 8 проводов ровно 3 провода будут припаяны правильно, а остальные неверно.
Для решения задачи сначала определим общее число перестановок 8 проводов. Оно равно 8! = 40320. Для решения 1-й части задачи отметим, что имеется всего одна благоприятная комбинация, поэтому вероятность распаять разъем правильно, не имея монтажной схемы, равна Р = 1/40320 = 0,0000248. Для решения второй части задачи число благоприятных комбинаций значительно больше и определяется как Р = =56·44 = 2464. Поэтому вероятность припаять правильно ровно 3 провода из 8 равна Р = 2464/40320 = 0,061.
