В полной колоде карт каждая карта принадлежит к одной из 4 мастей (пики, червы, бубны, трефы) и 13 достоинств (туз, 2, 3, 4, 5, 6, 7, 8, 9, 10, валет, дама и король). Значит, всего в полной колоде 4 × 13 = 52 карты. При желании все их можно разложить в виде прямоугольника со сторонами 4 на 13 – тем самым мы получим визуальное представление об общем количестве в 52.
Давайте применим правило произведения для подсчета почтовых индексов. Каково возможное количество пятизначных индексов? Каждый индекс – это пятизначное число, состоящее из цифр от 0 до 9. Наименьшее из них будет иметь вид 00000, а наибольшее – 99999[7]. Значит, всего имеется 100 000 вариантов. К тому же результату можно прийти с помощью правила произведения. У нас есть 10 вариантов выбора числа для первой цифры (от 0 до 9), 10 – для второй, и дальше по 10 для третьей, четвертой и пятой. Значит, имеем 105 = 100 000 вариантов.
В почтовых индексах числа могут повторяться. А если взять ситуацию, в которой объекты не могут повторяться – например, когда вы выкладываете предметы в ряд? Несложно заметить, что два объекта в каждой паре могут быть расположены двумя способами. Скажем, буквы А и B могут быть представлены либо как АВ, либо как ВА. Способов разложить 3 объекта у нас ровно 6: ABC, ACB, BAC, BCA, CAB, CBA. А можете представить в уме, без ручки и бумажки, 24 возможные комбинации 4 объектов? Начнем с выбора одного из четырех вариантов для начальной позиции (выбираем из четырех букв: А, B, C или D). Для второй позиции останется 3 варианта, для третьей – 1, для последней, четвертой, – всего лишь 1. Всего получается 4 × 3 × 2 × 1 = 4! = 24 варианта. Другими словами, для n объектов имеется n! вариантов их расположения.
А вот пример одновременного использования правил суммы и произведения. Допустим, некое государство выдает автовладельцам регистрационные номера двух типов. Номера первого типа состоят из 3 букв и 3 цифр, второго – из 2 букв и 4 цифр (в обоих случаях сначала идут буквы, потом – цифры). Сколько всего будет номеров (притом что мы можем использовать все 26 букв латинского алфавита и 10 цифр, не обращая при этом внимания на внешнее сходство, вроде О и ноль)? Сначала посчитаем количество номеров первого типа, применив правило произведения:
То же с номерами второго типа:
Так как один номер относится либо к первому, либо ко второму типу (и не повторяется), согласно правилу суммы общее количество возможных комбинаций – 24 336 000.
Но подобного рода подсчеты (математики даже выделяют такие упражнения в отдельную ветвь своей науки – комбинаторику) не приносили бы столько удовольствия, если бы не многообразие способов, которыми можно достичь желаемого (мы уже успели в этом убедиться, когда говорили об устном счете). Оказывается, то же количество автомобильных номеров можно посчитать за один шаг:
ведь для первых двух символов каждого номера существует 26 вариантов, для последних трех – 10, при этом третий символ может быть или буквой, или цифрой, а значит, возможных вариантов здесь будет 26 + 10 = 36.
Лотерея и покер
В этом разделе мы используем то, что только что узнали, для подсчета своих шансов выиграть в лотерею или собрать нужную комбинацию в покере. Но позвольте сначала предложить вам немного мороженого.
Допустим, вам предлагают наполнить рожок 3 шариками разных сортов мороженого. Всего можно выбирать из 10 сортов. Сколько всего можно получить разных рожков? Не забудьте: порядок шариков разных сортов имеет значение (а как же иначе? Ведь вкус-то разный!). Если повторяться можно, получается, что у нас есть 10 вариантов для каждого из трех шариков: 103 = 1000 вероятных комбинаций. Ну а если нельзя – их количество сокращается до 10 × 9 × 8 = 720, как показано на картинке чуть ниже.
Теперь кое-что поинтереснее. Как будут лежать три шарика трех разных сортов в вазочке, если их порядок не важен? Можно сказать точно: их будет меньше. А конкретно – в 6 раз меньше. Попытаемся понять, почему. Лежащие в вазочке 3 шарика мороженого 3 разных сортов (допустим, шоколадное, ванильное и мятное) можно переложить в рожок 3! = 6 способами. Значит, из 1 варианта вазочки можно собрать 6 вариантов рожков. Количество вазочек, таким образом, будет равняться
Другой способ представить 10 × 9 × 8 – 10!/7! (хотя первый пример, конечно, легче подсчитать). Значит, количество чашек – Такая запись читается как «число сочетаний из 10 по 3», обозначается символом и равняется 120. Другими словами, число вариантов при выборе определенного количества различных объектов, равного n, из общего количества различных объектов, равного k (в произвольном порядке), называется «числом сочетаний из n по k» и подсчитывается по формуле
Математики называют такого рода вычисления сочетаниями или комбинациями, а числа вида – биноминальными коэффициентами. Вычисления же при строго определенном порядке объектов называется перестановкой или пермутацией. Эти два понятия часто путают: например, мы привыкли думать, что на «кодовом» замке нужно подбирать «комбинации» цифр, хотя по сути это не комбинации, а перестановки, ведь порядок чисел, составляющих код, имеет большое, если не решающее, значение.
Если ваш продавец мороженого предлагает 20 разных сортов, то, направляясь туда с намерением купить 5 разных шариков (в случайном порядке), вам придется выбирать из
вариантов. Кстати, если на вашем калькуляторе не предусмотрено специальной кнопки, чтобы подсчитать просто наберите в любом поисковике «число сочетаний из 20 по 5»[8], и вы увидите веб-калькулятор с готовым ответом.
Биноминальные коэффициенты, впрочем, могут появляться и там, где порядок расположения объектов определенную роль все же играет. Если вы 10 раз подбросите монетку, сколько всего у вас будет возможных последовательностей результатов (вроде О-Р-О-Р-Р-О-О-Р-Р-Р или О-О-О-О-О-О-О-О-О-О)? Так как каждый бросок имеет два возможных исхода, правило произведения говорит нам, что их будет 210 = 1024, причем шансы выпадения каждой стороны абсолютно равны. (Некоторые, конечно, удивятся: вероятность того, что выпадет вторая комбинация, вроде бы куда ниже, чем у первой. Тем не менее шансы и у той, и у другой абсолютно равные – 1 к 1024.) С другой стороны, то, что за 10 бросков орел выпадет 4 раза, а не 10, куда вероятнее, ведь комбинаций с 4 орлами много, а с 10 – всего одна. Вот только «много» – это сколько? Подобная последовательность определяется количеством «орлиных» бросков, равным 4 из 10, соответственно, остальные броски должны закончиться выпадением решки. Количество способов определить, какие именно 4 из 10 бросков дадут нам орла, равно (все равно что выбирать 4 разных шарика мороженого из 10 сортов). Значит, наш шанс, что из 10 попыток 4 раза выпадет орел, если бросать симметричную, абсолютно уравновешенную монетку, равен
или примерно 20 % всех возможных комбинаций.
Логично спросить, сколько можно собрать вазочек с 3 шариками из 10 сортов, если можно повторяться (10³/6 – ответ неправильный, это ведь даже не целое число). Наиболее простой способ – рассмотреть 3 отдельных случая, взяв за отправную точку количество разных сортов в вазочке. Очевидно, что в случае с 3 шариками одного сорта получится 10 вазочек. Из сказанного выше понятно, что в случае с 3 шариками 3 сортов получится вазочек. А вазочек будут с 2 сортами мороженого, ведь 2 сорта мы можем выбрать способами. И лишь потом можно решать, какие 2 из 3 шариков будут именно этого сорта. Сложив все вместе, получим 10 + 120 + 90 = 220 вазочек.
Есть и другой способ прийти к этому ответу, не разбивая задачу. Каждую вазочку можно представить как комбинацию трех звездочек и девяти черточек. Если мы выбираем первый, второй и снова второй сорта, «перекодированная» вазочка будет выглядеть вот так:
Второй, снова второй и седьмой сорта – вот так:
А комбинация
будет означать, что наш выбор пал на сорта третий, пятый и десятый. То есть вазочка – это набор из 3 звездочек и 9 черточек. Всего получается 12 символов, 3 из которых обязательно должны быть звездочками. Следовательно, возможных комбинаций у нас будет Обобщая, можно сказать, что количество способов выбрать k объектов из множества n при произвольном порядке и с возможностью повторения равно количеству способов сочетания k звездочек и n – 1 черточек –
Подсчет сочетаний необходим в большинстве задач, в которых большую роль играет случайность. Представим себе лотерею, в которой вам нужно угадать 5 различных чисел от 1 до 47. Дополнительно вы выбираете еще одно, МЕГАчисло от 1 до 27 (можно выбирать любое, в том числе и одно из тех, которые уже встречались в пятерке). У нас есть 27 вариантов выбора дополнительного числа, и вариантов выбора основных 5 чисел. Таким образом, общее количество равно
Другими словами, ваш шанс выиграть главный приз в такой лотерее – примерно 1 из 40 миллионов.
Теперь давайте переключим внимание на покер. Комбинация в покере – это обычно 5 карт из 52, составляющих колоду. Все они разные, выбраны случайно, порядок их значения не имеет. Следовательно, количество комбинаций равняется
Комбинация из 5 карт одной и той же масти
называется флешем. Сколько всего может быть флешей? Чтобы посчитать, сначала выберем масть – 1 из 4 вариантов (давайте договоримся, что это будут пики). Сколько всего можно собрать комбинаций разных 5 карт этой масти? В колоде 13 пиковых карт. Значит, флешей всего