Элементы комбинаторики. Основные правила и формулы комбинаторики

Поговаривают, что ключевой предпосылкой для создания элементов комбинаторики и теории вероятностей стало пристрастие людей к лотереям, игральным костям, картам и прочим азартным играм. Азарт имел большое значение в древности. Одни выигрывали целые состояния, земли, жен. Другие теряли все, что имели, вплоть до последней рубашки. Действительно, влияние игр с риском или случайных игр имело место. Однако были и более основательные причины, в числе которых - бурное развитие науки: проведение опытов, необходимость в предсказании хода серии экспериментов и оценке погрешности результатов. Все это и многое другое привело к появлению элементов комбинаторики и теории вероятностей.

Теорема Бернулли

Считается, что комбинаторика появилась в XVII веке благодаря работам таких ученых, как Кардано, Паскаль, Галилей, Ферма, Лейбниц, Бернулли. Именно они ввели в употребление специфические термины для данной науки и доказали ряд основополагающих законов и первые для комбинаторики формулы. Например, теорема Бернулли, которая гласит, что рассмотрению стоит предавать только те опыты и эксперименты со случайностями, которые не зависят друг от друга и могут быть повторены сколько угодно раз в одинаковых условиях. Принято считать, что данная теорема определила дальнейшее развитие комбинаторики и теории вероятностей как науки.

Устойчивость частоты

Прежде чем перейдем к изучению элементов комбинаторики, приведем наглядный пример, наталкивающий на определенные мысли - подбрасывание костей. Рассмотрим для простоты одну кость. Это шестигранный куб, каждая сторона которого пронумерована. Если провести серию опытов из n бросков и положить, что Г₁ - количество выпадений грани с номером 1, Г₂ - с номером 2 и т. д., то выясняется, что с увеличением числа бросков n, частоты Г₁/n, Г₂/n, ..., Г₆/n, которые в начале эксперимента кажутся случайными, приобретают вполне определенные значения. И для хорошо сбалансированной игральной кости частота выпадения каждой грани будет равной с большой точностью.

Еще одним примером может послужить эксперимент с монетой. Так, ученый Пирсон, проведя 24 000 подбрасываний монеты, пришел к выводу, что частота выпадения одной из сторон монеты приближается к 0,5 тем точнее, чем больше бросков совершено. Таким образом он получил вероятность 0,5005 для выпадения герба. Данный принцип устойчивости частот также является одной из основ теории.

Историческая заметка

Наиболее активное развитие теория вероятностей и комбинаторика получили в XX веке. И огромный вклад в это дело был внесен русскими и советскими математиками. В их числе, например, Колмогоров, Чебышев, Ляпунов, Марков. Они значительно расширили области применимости, исследовали и описали закон больших чисел, центральную предельную теорему, аксиоматику теории вероятностей. Все это стало основой для целой науки. На сегодняшний день сложно переоценить значение элементов комбинаторики и теории вероятностей в физике, химии, биологии и многих других областях, особенно в практической их области.

Примеры задач комбинаторики

Комбинаторика - это оценка количества возможных комбинаций, составляемых из какого-либо набора элементов, при соблюдении определенных условий. Для этого были выведены в комбинаторике формулы, позволяющие удобно и быстро решать требуемую задачу. Но прежде чем показать эти формулы, рассмотрим примеры вопросов, которые привели к их появлению.

Задача 1. В плей-офф стадии чемпионата мира принимают участие 16 команд. Сколькими способами у них выйдет распределить между собой места? Так, например:

• (3, 1, 2, 4..16) - на первом месте команда под номером 3, на втором - под номером 1, т. д.
• (16, 1, 2, 3, 4..15) - на первом месте команда под номером 16, ...
• (1..7, 9, 8, 10..16) - на первых местах команды 1, 2, 3, ...

Все это примеры вариантов. Очевидным решением данной задачи будет выписать все возможные комбинации. Однако займет это много времени, ведь их количество будет таким же, сколько существует способов переставить 16 цифр местами. Элементами комбинаторики примеры, подобные данному, решаются в два счета.

Задача 2. Среди этих 16 команд лишь три могут получить призовое место. Сколькими способами будут определены призеры? В данном случае задача от предыдущей отличается тем, что совершенно не важно, как выглядит турнирная таблица и какой порядок финалистов. Ведь среди всех команд важно найти только три, которые будут разыгрывать между собой призовые места. То есть наборы могут выглядеть как {3, 2, 1}, {5, 12, 7}, {8, 1, 2} и т. д.

Задача 3. А что, если мы поставим вопрос немного иначе: сколько найдется вариантов раздачи медалей по 16 командам, участвующим в плей-оффе? Разница со второй задачей может быть не совсем очевидна. Однако теперь нам предстоит выбрать не только три команды, которые будут бороться за призовые места, но определить кто из них какое место займет. Другими словами, если для второй задачи, например, наборы (5, 12, 1) и (1, 12, 5) были равнозначными, то теперь порядок команд имеет вес. Ведь в первом случае золото получит команда под номером 5, а во втором - под номером 1.

Ниже мы рассмотрим, к какому из разделов комбинаторики относится каждая из задач и подробно расскажем о способе их решения. А пока можете попробовать самостоятельно поразмышлять над поставленными вопросами.

Сочетания или комбинация без учета порядка

Сочетанием из всего n-штук элементов наборами по k-штук элементов, где k может принимать значения от 1 до n, называется любая комбинация из k элементов, выбранных из n штук элементов. В данном случае два набора будут считаться различными, если в один из них входит какой-либо элемент из n, но не входит во второй. Иными словами, различаются они только составом. В элементах комбинаторики сочетания являются вводной основой.

Количество сочетаний из n по k обозначается C_n^k , от английского слова Combination. Вполне очевидными являются утверждения C_n¹ = n и C_nⁿ = 1. То есть вариантов выбрать из n элементов по одному всего n штук (столько же, сколько самих элементов) и, соответственно, можно составить набор из n элементов в количестве n штук только один.

Так, например, рассмотрим набор из трех элементов {е, 2, a}. Для него C₃¹ = 3: {a}, {2}, {е}; C₃² = 3: {е, 2}, {2, a}, {a, е}; и, наконец, C₃³ = 1: {е, 2, a}. Напомним, что в данном случае порядок следования элементов в наборах не имеет никакого значения.

А что будет, если попытаться сообразить, что есть C_n⁰?

Размещения или комбинация с учетом порядка

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

• они отличаются составом;
• они отличаются порядком элементов в составе наборов;
• они отличаются и составом и порядком.

Количество размещение из n по k обозначается A_n^k , от слова Arrangements. Рассмотрим все варианты размещения для трехэлементного набора {x, е, z}:

• A₃¹ = 3: (x), (е), (z);
• A₃² = 6: (x, е), (е, x), (x, z), (z, x), (е, z), (z, е);
• A₃³ = 6: (x, е, z), (е, x, z), (z, x, е), (x, z, е), (е, z, x), (z, е, x).

Последняя строка A₃³ заслуживает отдельного внимания. Это не что иное, как перестановки.

Перестановки

Как уже выше было сказано, перестановки - это совсем просто по смыслу. Это просто размещения из n элементов по n штук. То есть нас интересуют все комбинации, различающиеся порядком следования элементов, и только им. Или, что то же самое, A_nⁿ. Обозначается количество перестановок буквой P, от слова Permutation. В элементах комбинаторики перестановки снабжаются лишь одним индексом. Так, например, P₃ = 6, как мы выяснили в предыдущей главе.

Комбинации через теорию множеств

Как известно, в математике сложно общаться неопределенными сущностями: набор, комбинация и т. д. Неплохо было бы математически точно определить то, с чем же мы имеем дело. И тут отлично подходит язык теории множеств. Определим, что представляют собой элементы комбинаторики на языке теории множеств.

Пусть дано некоторое n-множество A = {a₁, a₂, ..., a_n}, в нем содержится n штук элементов. Легко определить из n-множества его k-подмножество, где k меньше или равно n. Тогда сочетаниями из n по k будут называться все подмножества k множества n. Благодаря такому определению можно легко ответить на вопрос, что из себя будет представлять запись C_n⁰. Так как в теории множеств пустое множество содержится в любом подмножестве, то C_n⁰ = 1. Иными словами, это будет комбинация, которая содержит один элемент - пустое множество.

Таким образом, изучая множество из трех элементов {c, b, a}, мы получим, что C_n⁰ = 1: {}; C₃¹ = 3: {a}, {b}, {c}; C₃² = 3: {a, b}, {b, c}, {c, a}; и, наконец, C₃³ = 1: {a, b, c}.

Соответственно, аналогичным образом будут определяться в комбинаторике размещения. С той лишь разницей, что выделять нужно упорядоченные k-подмножества из n-множества. И все подмножества также будут содержать пустое множество. Оно условно считается упорядоченной комбинацией из n элементов по 0 штук, т.е. A_n⁰ = 1.

Благодаря переходу от неясных конструкций к четко определенным в теории множеств объектам получилось достаточно тривиально ответить на один из возникших вопросов. В этом вся математика.

Принцип сложения

Это одно из двух основных правил комбинаторики. Пусть в городе Москва из точки А в точку Б можно доехать 5 автобусами, 3 трамваями и 1 поездом метро. Получится, всего способов добраться до нужного места 5 + 3 + 1 = 9. Это и есть комбинаторный принцип сложения.

Если при рассмотрении задачи ее можно решить n способами, при этом первый из этих способов можно применить m₁ раз, второй - m₂ раза и т. д., тогда данная задача будет решаться m₁ + m₂ + ... + m_n способами.

Принцип умножения

Теперь представим, что из Москвы в Казань нужно добраться через Нижний Новгород. При этом Москва и Нижний Новгород связаны 2 поездами, 3 авиарейсами и 10 машинами, а Нижний Новгород и Казань - 1 поездом, 1 авиарейсом и 2 автобусами. По принципу сложения мы приходим к тому, что из Москвы до Нижнего Новгорода можно добраться 13 способами, а оттуда в Казань - 4. Итоговое количество путей, которое связывает Москву и Казань, будет: 13 * 4 = 52.

Таким образом, комбинаторный принцип умножения гласит следующее. Если задача решается за n штук последовательных этапов, при этом m₁ способами на первом этапе, m₂ - на втором и т. д., при этом данные последовательные этапы независимы, то есть число способов не изменяется в зависимости от того, каким образом производилось решение на предыдущих этапах, тогда задача решается m₁*m₂*...*m_n способами. Два способа решения считаются разными, если есть хотя бы одно отличие на этапах.

Основные формулы

Покажем формулы сразу, затем расскажем вкратце, откуда они берутся, и решим с применением данных элементов комбинаторики примеры, описанные ранее.

• Размещения. Мы начинаем с этой формулы, поскольку из нее выводятся другие.

• Перестановки.

• Сочетания.

Доказательство данных формул основывается на принципах элементов комбинаторики - правилах сложения и умножения. Рассмотрим первую формулу для поиска количества размещений. На первом этапе мы берем один из n-штук элементов и для этого у нас n способов. На втором этапе у нас остается n-1 элементов и, соответственно, n-1 способов выбора. На третьем - n-3 способа. Продолжаем делать это до тех пор, пока в нашем наборе не окажется k штук элементов. По правилу умножения мы придем к тому, что всего способов выбрать k элементов у нас n(n-1)(n-2)(n-3)(n-4)(n-5)...(n-k+1). Вторая формула для поиска перестановок является простым следствием первой за счет подстановки m=k. Последняя формула, дающая количество сочетаний, получается из соображений, что при поиске сочетаний из n элементов по k штук мы каждый раз приходим к просмотру k! размещений из n по k (они получаются как перестановки из k элементов). Поэтому имеем A_n^k = C_n^k*k!.

Теперь мы можем вернуться к задачам, которые были озвучены ранее, и оценить количество вариантов. Для первой задачи нам нужно использовать формулу перестановок, т. е. P₁₆ = 16! = 20 922 789 888 000 ≈ 21 * 10¹² возможных вариантов, как 16 команд могут расположиться в турнирной таблице. Вторая задача касается сочетаний, а значит, C₁₆³ = 16! / [3!(16-3)!] = 560 вариантов призеров. Наконец, последняя задача касается размещений, т. е. A₁₆³ = 16! / (16-3)! = 3360 вариантов, как 3 команды из 16 могут разделить призовые места.

Учитывая описанное, излишне говорить о том, с насколько большими числами работает комбинаторика.