Бином Ньютона. Вычисление вероятности с помощью формул комбинаторики

Перестановки без повторений

Перестановкой из n элементов называется n-элементное упорядоченное множество, составленное из элементов n-элементного множества.

Иначе: Перестановкой из n элементов называется размещение из n элементов по n без повторений.

Число перестановок из n элементов без повторений обозначается P_n от французского слова perturbation.

Теорема: число способов расположить в ряд n различных объектов есть \(P_n=n(n-1)(n-2)\cdot ...\cdot2\cdot 1=n!\).

Рекуррентная формула: \(P_n=n\cdot P_{n-1}\).

Перестановки симметричных объектов

n различных предметов можно расположить по кругу \((n-1)!\) способами, а если их можно еще и переворачивать, то \(\frac{(n-1)!}2\) различными способами.

Размещения без повторений

Подсчитаем количество способов расположить n различных элементов по k различным позициям (k < n). Такие расположения называются размещениями, а их количество от французского слова arrangement обозначается как \(A^k_n\), в случае, если k = n количество предметов совпадает с количеством имеющихся мест, и это уже изученная задача о числе перестановок.

Если из n объектов выбирают k штук, то число выборов последнего объекта есть n – k невыбранных объектов, что означает наличие n – k + 1 возможности выбора последнего выбранного объекта. То же, другими словами: после выбора первых k – 1 элементов остается выбрать n – (k – 1) = n – k + 1 элемент.

Теорема: число размещений n различных элементов по k различным позициям есть \(A^k_n=n(n-1)(n-2)...(n-k+1)\), или в терминах факториалов – \(A^k_n=\frac{n!}{(n-k)!}\).

Сочетания

Подсчитаем количество способов, которыми можно выбрать k из n различных предметов. Такие выборки называются сочетаниями, а их количество обозначается как \(C^k_n\).

При k < n выбрать k предметов из n можно \(A^k_n\) способами, переставляя их \(P_k\) способами: \(C^k_n=\frac{A^k_n}{P_k}=\frac{n!}{(n-k)!\cdot k!}\).

Рекуррентная формула: \(C^n_m=C^{n-1}_m\cdot \frac{m-n+1}{n}\).

Свойства сочетаний: \(C^n_m=C^{m-n}_m; C^n_m+C^{n+1}_m=C^{n+1}_{m+1}\).

Перестановки с повторениями

Пусть даны n₁ элементов первого типа, n₂ – второго типа,..., n_k – k-го типа, всего n элементов. Способы разместить их по n различным местам называются перестановками с повторениями. Их количество обозначается как \(P_n(n_1,n_2,...,n_k)\).

Теорема: число перестановок с повторениями есть \(P_n(n_1,n_2,...,n_k)=\frac{n!}{n_1!n_2!...n_k!}\).

Размещения с повторениями

Пусть даны n различных видов предметов, которые можно разместить по k различным местам, причем выбирать предметы можно с повторениями (т. е. можно выбрать несколько предметов одного вида). Такие выборки называются размещениями с повторениями, а их количество вычисляется по формуле: \(A^k_n=n^k\).

Сочетания с повторениями

Пусть имеются предметы n различных видов предметов, и из них составляются наборы, содержащие k элементов. Такие выборки называются сочетаниями с повторением. Их число обозначается как \(C^k_n\).

Теорема: число сочетаний с повторениями может быть вычислено по формулам: \(C^k_n=C^k_{n+k-1}=C^{n-1}_{n+k-1}\).

Бином Ньютона. Это формула, представляющая выражение \(( a + b ) ^n\) при положительном целом n в виде многочлена: \((a+b)^n=C^0_na^n+C^1_na^{n-1}b+C^2_na^{n-2}b^2+...+C^{n-1}_nab^{n-1}+C^n_nb^n\).

Коэффициенты в формуле бинома Ньютона равны числу неупорядоченных сочетаний из n по m элементов: \(\left( {\begin{array}{*{20}{c}} n\\ m \end{array}} \right) = C_n^m = \large\frac{{n!}}{{m!\left( {n - m} \right)!}}\normalsize = \large\frac{{n\left( {n - 1} \right)\left( {n - 1} \right) \ldots \left( {n - m + 1} \right)}}{{m!}}\normalsize\).

Для биномиальных коэффициентов справедливы равенства:

1. \(C^k_n=C^{k-1}_{n-1}+C^k_{n-1}\).
2. \(C^0_n+C^1_n+C^2_n+...+C^n_n=2^n\).
3. \(C^0_n-C^1_n-C^2_n-...+(-1)^nC^n_n=0\).

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

Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая – для n = 2; третья – для n = 3 и т. д. Поэтому, если необходимо, например, разложить выражение \(( a + b )^7\), мы можем получить результат моментально, используя таблицу: \((a+b)^7=a^7+7a^6b+21a^5b^2+35a^4b^3+35a^3b^4+21a^2b^5+7ab^6+b^7\).

Пример. В ящике 15 шаров, из которых 5 голубых и 10 красных. Наугад выбирают 6 шаров. Найти вероятность того, что среди вынутых шаров будет 2 голубых.

Решение: Общее число элементарных исходов данного опыта равно числу сочетаний из 15 по 6, то есть \(C_{15}^6=\frac{15!}{6!\cdot 9!}=5005\). Число благоприятных исходов равно произведению \(C_5^2\cdot C_{10}^4=2100\). Искомая вероятность определяется формулой: \(P=\displaystyle\frac{C_5^2\cdot C_{10}^4}{C_{15}^6}=\frac{2100}{5005}\approx0,42\).