Сочетания без повторений
Если требуется выбрать k предметов из n, и при этом порядок выбираемых предметов безразличен, то имеем
(7)
Формула (7) может быть получена следующим образом. Выберем
по очереди k предметов из n. Число вариантов будет равно n!(n - k)! В этих расстановках k выбранных предмета имеют свои определенные позиции. Однако нас не интересуют в данном случае позиции выбранных предметов. От перестановки этих предметов интересующий нас выбор не меняется. Поэтому полученное выражение нужно разделить на k!
IIример. Из группы в 25 человек нужно выбрать троих для работы в колхозе. Если выбирать их последовательно, сначала первого, потом второго, потом третьего, то получим 25 · 24 · 23 варианта. Но так как нас не интересует порядок выбора, а только состав выбранной бригады, поэтому полученный результат нужно разделить еще на 3!
IIример 2 . В середине 60-х годов в России появились две лотереи, которые по недоразумению были названы "Спортлото": лотерея 5/36 и 6/49. Рассмотрим одну из них, например, 6/49. Играющий покупает билет, на котором имеется 49 клеточек. Каждая клеточка соответствует какому-либо виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и отправить организаторам лотереи. После розыгрыша лотереи объявляются шесть выигравших номеров. Награждается угадавший все шесть номеров, пять номеров, четыре номера и даже угадавший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше выигрыш.
Подсчитаем, сколько существует разных способов заполнения карточек "Спортлото" при условии, что используется лотерея 6/49. Казалось бы, заполняя последовательно номер за номером, получим: 49 · 48 · 47 · 46 · 45 · 44. Но ведь порядок заполнения не имеет значения, тогда получаем:
Эту же задачу можно решить и другим способом. Выпишем все номера подряд и под выбираемыми номерами поставим 1, а под остальными -0. Тогда различные варианты заполнения карточек будут отличаться перестановками. При этом переставляются 6 предметов одного вида (единицы) и 49 - 6 = 43 предмета другого вида (нули), т. е. опять
Если все участники заполняют карточки по-разному, то в среднем один из примерно 14 миллионов угадает все 6 номеров. А сколько человек в среднем угадают 5 номеров?
Выберем один из угаданных номеров ( =6) и заменим его на один из не угаданных ( = 43). Итого: 6 · 43 = 258 человек из 14 миллионов угадают 5 номеров. А сколько угадают 4 номера? Выберем из 6 угаданных два и затем из 43 не угаданных тоже два и перемножим число вариантов выбора. Тогда получим:
Аналогично найдем, что 3 номера угадают 246820 человек, т. е. примерно 1,77% от всех играющих. Казалось бы. если взять 60 билетов и их "хорошо" заполнить, то можно надеяться на надежный выигрыш хотя бы одной тройки, при этом есть шанс угадать и 4, и 5, и 6 номеров. Однако это не так и число билетов, которые нужно заполнить, чтобы гарантировать угадывание трех номеров, существенно больше.
О целесообразности игры в "Спортлото" можно рассуждать с различных точек зрения. Прагматики понимают, что купив все билеты и как-то их заполнив, вы всегда проиграете, так как из выручки за проданные билеты сразу же производятся отчисления организаторам, изготовителям и распространителям билетов любой лотереи и может быть еще на какие-то благотворительные цели (например, на развитие спорта). Остатки идут на премии угадавшим 6, 5, 4 или 3 номера. Люди, верящие в свою счастливую судьбу, рассуждают примерно так: если не купить ни одного билета, то даже теоретической возможности выиграть не будет. Поэтому надо играть. Мне казалось, что компромисс между этими позициями состоит в том, чтобы, если уж очень хочется испытать судьбу, купить один билет.
Кстати, попробуйте обосновать алгоритм заполнения минимального числа билетов лотереи "Спортлото", при котором гарантируется угадывание хотя бы одной комбинации из 3 номеров. А может быть, попробовать то же с 4 номерами?