Список статей

Мы в социальных сетях

       

Формулы комбинаторики

Факториал

Факториал — это произведение всех натуральных чисел от \(1\) до \(n\) включительно.

  • \(0!=1\)
  • \(1!=1\)
  • \(2!=1\cdot 2\)
  • \(3!=1\cdot 2\cdot 3=6\)
  • \(4!=1\cdot 2\cdot 3\cdot 4=24\)
  • \(5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120\)

Перестановки, размещения и сочетания без повторений

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

Количество перестановок \(n\) объектов вычисляется по формуле: \(P_{n}=n!\).

Размещения

Количество способов выбрать \(m\) объектов из  \(n\) объектов и в каждой выборке переставить их местами: \(A_{n}^{m}=(n-m+1)\cdot ... \cdot (n-1)n\). Эта формула эквивалентна формуле: \(A_{n}^{m}=C_{n}^{m}\cdot ... \cdot (n-1)n\).

Сочетания

Количество способов выбрать \(m\) объектов из  \(n\) объектов: \(C_{n}^{m}=\dfrac{n!}{(n-m)!\cdot m!}\), причем \(0\leq m\leq n\).

Треугольник Паскаля. Бином Ньютона

Бином Ньютона — формула возведения двучлена \(a+b\) в степень \(n\), где \(n \in \mathbb{N}\):

  • \((a+b)^{0}=1\)
  • \((a+b)^{1}=C_{1}^{0}a+C_{1}^{1}b=a+b\)
  • \((a+b)^{2}=C_{2}^{0}a^{2}+C_{2}^{1}a^{1}b^{1}+C_{2}^{2}b^{2}=a^{2}+2ab+b^{2}\)

В общем виде формула выглядит следующим образом: \((a+b)^{n}=C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b^{1}+C_{n}^{2}a^{n-2}b^{2}+...+C_{n}^{n-1}a^{1}b^{n-1}+C_{n}^{n}b^{n}\)

треугольник паскаля
Рисунок 1. Треугольник Паскаля

Коэффициенты высчитываются по формуле \(C_{n}^{m}\), приведенной выше или с помощью треугольника Паскаля. Треугольник Паскаля представляет из себя бесконечную таблицу биномиальных коэффициентов и представлен на рисунке 1. Строка номер \(n\) треугольника содержит коэффициенты для формулы возведения двучлена в степень \(n+1\).

Комбинаторные правила суммы и произведения

Если существует объект \(A\), который можно выбрать из набора объектов \(m\) способами и есть объект \(B\), который можно выбрать \(n\) способами, то выбрать объект \(A\) ИЛИ объект \(B\) можно \(m+n\) способами.

В случае, когда объект \(A\) можно выбрать \(m\) способами И для каждой такой выборки объект \(B\) можно выбрать \(n\) способами, то пара объектов \(A; B\) может быть выбрана \(m\cdot n\) способами.

Перестановки, размещения и сочетания с повторениями

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

Количество перестановок с повторениями \(n\) объектов вычисляется по формуле: \(P_{n(повт)}=\dfrac{n!}{n_{1}!\cdot n_{2}!\cdot n_{3}!\cdot...\cdot n_{k}!}\), где \(n_{1}+n_{2}+ n_{3}+...+n_{k}=n\)

Размещения

Количество размещений с повторениями считается по формуле: \(A_{n(повт)}^{m}=n^{m}\)

Сочетания

Сочетания с повторениями: \(C_{n(повт)}^{m}=C_{n+m-1}^{m}=\dfrac{(n+m-1)!}{(n-1)!\cdot m!}\).

Нет комментариев



ru |  en