Элементы комбинаторики

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

Основная формула комбинаторики

Пусть имеется \(k\) групп элементов, причем \(i\)-я группа состоит из \(n_i\) элементов. Выберем по одному элементу из каждой группы. Тогда общее число \(N\) способов, которыми можно произвести такой выбор, определяется соотношением \(N=n_{1}\cdot{n_{2}}\cdot{n_{3}}\cdot...\cdot{n_{k}}\).

Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из \(n_1\) элементов, а вторая - из \(n_2\) элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить \(n_2\). Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет \(n_2\). Так как в первой группе всего \(n_1\) элемент, всего возможных вариантов будет \(n_{1}\cdot{n_{2}}\).

В том случае, когда все группы состоят из одинакового числа элементов, т.е. \(n_1=n_2=...n_k=n\) можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно \(n^k\). Такой способ выбора в комбинаторики носит название выборки с возвращением.

Рассмотрим множество, состоящие из \(n\) элементов. Это множество в комбинаторике называется генеральной совокупностью.

Число размещений из \(n\) элементов по \(m\)

Определение 1. Размещением из \(n\) элементов по \(m\) в комбинаторике называется любой упорядоченный набор из \(m\) различных элементов, выбранных из генеральной совокупности в \(n\) элементов.

Число размещений в комбинаторике обозначается \(A_n^m\) и вычисляется по формуле:

\(A_n^m=\frac{n!}{(n-m)!}\)

Замечание: \(n!=1\cdot2\cdot3\cdot...\cdot{n}\), кроме того полагают, что \(0!=1\).

Число сочетаний из \(n\) элементов по \(m\)

Определение 2. Сочетанием из \(n\) элементов по \(m\) в комбинаторике называется любой неупорядоченный набор из \(m\) различных элементов, выбранных из генеральной совокупности в \(n\) элементов.

Число сочетаний обозначается \(C_n^m\) и вычисляется по формуле:

\(C_n^m=\frac{n!}{m!(n-m)!}\)

Перестановки из \(n\) элементов

Определение 3. Перестановкой из \(n\) элементов называется любой упорядоченный набор этих элементов.

Число различных перестановок из \(n\) элементов обозначается \(P_n\) и вычисляется по формуле \(P_n=n!\).

Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример: На родительском собрании присутствует \(20\) человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти \(5\) человек?

Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из \(20\) элементов по \(5\).

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно \(5!\) вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из \(20\) элементов по \(5\).

Теория вероятностей

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

Вероятность события равна отношению числа благоприятных исходов к общему числу исходов. Иными словами вероятностью события \(A\) называется дробь \(P(a)={m\over n}\), в числителе которой стоит число \(m\) исходов, благоприятствующих событию \(A\), а в знаменателе \(n\) — число всех возможных исходов события. Очевидно, что вероятность не может быть больше единицы и не может быть меньше \(0\), т.е. вероятность события — это число из отрезка \([0;1]\)

Два события называются противоположными, если в данном испытании они несовместимы и одно из них обязательно происходит. Вероятности противоположных событий в сумме дают \(1\).

Два события \(A\) и \(B\) называются независимыми, если вероятность появления каждого из них не зависит от того, появилось другое событие или нет. В противном случае события называются зависимыми.

Правило умножения вероятностей: если \(A\) и \(B\) независимые события, то вероятность одновременного наступления обоих событий \(A\) и \(B\), равна произведению их вероятностей \(P(A\times B)=P(A)\times P(B)\).

Два события \(A\) и \(B\) называют несовместными, если отсутствуют исходы, благоприятствующие одновременно как событию \(A\), так и событию \(B\) (cобытия, которые не могут произойти одновременно).

Правило сложения вероятностей: если \(A\) и \(B\) несовместные события, то вероятность того, что наступит хотя бы одно из двух событий \(A\) или \(B\), равна сумме их вероятностей \(P(A+ B)=P(A) + P(B)\).

Правило сложения вероятностей для совместимых событий: вероятность суммы двух совместимых событий равна сумме их вероятностей за вычетом вероятности их произведения \(P(A+ B)=P(A) + P(B)-P(A\times B)\).

Элементы статистики

Вероятно, Вы отлично знаете, что такое среднее арифметическое. Если мы имеем набор каких-то величин, и все они одной природы (усреднять килограммы с километрами мы, конечно, не можем), надо посчитать сумму, а затем, поделив ее на количество слагаемых, найти среднее арифметическое. Казалось бы, простое и хорошо знакомое действие, но и тут имеется несколько проблем для обсуждения. При знакомстве с некоторыми "показателями" поневоле вспоминается известная шутка о "средней температуре по больнице".

Поэтому иногда, вместо среднего арифметического употребляют другие характерные величины, если это по каким-то причинам лучше описывает выборку.

Так если расставить выборку по возрастанию (или убыванию) той величины, которой мы интересуемся, то медиана - это то, что будет ровно посередине "строя". Например, если мы расположим по порядку длительности интервалы времени: секунда, минута, час, сутки и неделя - то медианой будет час.

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