Как решать комбинаторные задачи

Данный вопрос можно рассмотреть как с точки зрения стандартных методов и подходов комбинаторики, так и с применением теории вероятности. Это позволяет несколько расширить кругозор, а также взглянуть на поставленную задачу с нестандартной точки зрения.

Инструкция

1. Как известно, вероятность простых событий определяется по классической формуле Р(А)=m/n, в которой число событий (исходов) конечно и равновозможно. При этом n - общее число исходов, а m – число благоприятных исходов (условию задачи). Теперь, необходимо рассмотреть три наиболее распространенные формулы комбинаторики: перестановки, сочетания и размещения.
2. ПерестановкиПредставьте себе, что на столе лежат пять карточек, на невидимой стороне которых написаны цифры: 1, 2, 3, 4 и 5. Произвольным образом, по одной, они вынимаются, переворачиваются и укладываются по очереди. Какова вероятность того, что извлеченная комбинация будет числом 12345?Количество благоприятных исходов m очевидно – m=1. В то время как всего вариантов n=5!=120, где «!» - знак факториала будет целых 120, а искомая вероятность данного события Р= 1/120, соответственно. В данном примере общее число исходов искали как число всевозможных перестановок пяти элементов по пяти позициям. Поэтому и в произвольном случае n элементов это число называют числом перестановок и обозначают Pn (Pn=n!)
3. СочетанияСледует рассмотреть следующий пример. В корзине находится некоторое количество шаров двух цветов, равное n. В такой постановке задачи, число сочетаний из n элементов по m называют множество способов, отличающихся друг от друга количеством шаров разного цвета в каждой комбинации. При этом n – общее число шаров (элементов), m – число элементов в извлеченной комбинации. Комбинации различны, если они отличаются хотя бы одним элементом. Обозначение числа сочетаний и формула для вычисления приведены на рисунке 1.
4. Предположительно, необходимо вычислить вероятность выигрыша в спортлото 6 из 49, где «угадано» 4 из 6-ти. Очевидно, что при этом используется формула для сочетания.Общее число исходов С (из 49 по 6)=49!/43!6! Благоприятное число исходов можно найти из следующих соображений. Имеется 6 «хороших» из общего количества 49 номеров. По вопросу задачи достаточно 4-х совпадений. Из 6-ти «хороших» 4 можно выбрать С (из 6 по 4) способами. При этом из оставшихся 43 «плохих» выбираются 2 для дополнения выбранной комбинации до шести элементов С (из 43 по2) способами. Звучит это следующим образом.
5. Число благоприятных ситуаций собирается как С (из 6 по 4) и С (из 37 по 2) (ситуация логического умножения). Значит m=С(из 6 по 4)∙С(из 43 по 2). Таким образом, вероятность даже самого «мизерного» выигрыша Р=m/n=С(из 6 по 4)∙С(из 43 по 2)/С(из 49 по 6)=(6!/2!4!)(43!/2!41!)/(49!/6!43!)=15*21*43/66*92*47*49=9*43/92*47*154=0,000347.
6. РазмещенияЕсли в задаче о сочетаниях учесть порядок следования элементов в выбранной комбинации из m элементов, то появится задача о размещениях. Вопрос, на основании которого принимается решением о применении формулы числа сочетаний должен добавочно (по сравнению с сочетаниями) содержать данные о необходимости учета порядка расположения элементов в выбираемых комбинациях. Если выбрано m элементов, то вычисляя число размещений необходимо число сочетаний умножить на число перестановок Pm=m!. Обозначение числа размещений и формулы для его вычисления даны на рис. 2.