Комбинаторика и бином Ньютона

Формулы комбинаторики: перестановки, размещения, сочетания. Понятные схемы и бином Ньютона.

Размещения

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

Существуют два вида размещений:

без повторений – каждый элемент, входящий в комбинацию, представлен единственным экземпляром (например, размещения без повторений из \(n=3\) элементов \(a, b, c\) по \(m=2\) элемента таковы: \(ab, ba, ac, ca, bc, cb\));
с повторениями – каждый элемент, входящий в комбинацию, может быть представлен более, чем одним экземпляром (например, размещения с повторениями из \(n=3\) элементов \(a, b, c\) по \(m=2\) элемента таковы: \(aa, ab, ac, ba, bb, bc, ca, cb, cc\); размещения с повторениями из \(n=2\) элементов \( a, b\) по \(m=3\) элемента таковы: \(aaa, aab, aba, abb, baa, bab, bba, bbb\)).

Число возможных размещений из \(n\) различимых элементов по \(m\) находят по формулам:

без повторений
\[A_{n}^{m}=\frac{n!}{\left(n-m\right)!}=n\left(n-1\right)... \left(n-m+1\right),\;m\leq n;\]
с повторениями
\[\tilde{A_{n}^{m}}=n^{m}.\]

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

Последовательности, каждая из которых состоит из \(n\) различимых элементов и отличается от другой только порядком расположения элементов, т. е. это размещения без повторений из \(n\) элементов по \(n\) (например, перестановки из трех элементов \(a, b, c\) таковы: \(abc, acb, bac, bca, cab, cba\)).

Число возможных перестановок из \(n\) различимых элементов находят по формуле

\[P_{n}=n!\]

Сочетания

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

Существуют два вида сочетаний:

без повторений – каждый элемент, входящий в комбинацию, представлен единственным экземпляром (например, сочетания без повторений из \(n=4\) элементов \(a, b, c, d\) по \(m=2\) элемента таковы: \(ab, ac, ad, bc, bd, cd\)),
с повторениями – каждый элемент, входящий в комбинацию, может быть представлен более, чем одним экземпляром (например, сочетания с повторениями из \(n=4\) элементов \(a, b, c, d\) по \(m=2\) элемента таковы: \(aa, ab, ac, ad, bb, bc, bd, cc, cd, dd\); сочетания с повторениями из \(n=2\) элементов \(a, b\) по \(m=4\) элемента таковы: \(aaaa, aaab, abab, abbb, bbbb\)).

Число возможных сочетаний из \(n\) различимых элементов по \(m\) находят по формулам:

без повторений
\[C_{n}^{m}=\frac{A_{n}^{m}}{P_{m}}=\frac{n!}{\left(n-m\right)!m!},\;m\leq n,\; C_{n}^{0}=1;\]
с повторениями

\[\tilde{C_{n}^{m}}=C_{n+m-1}^{m}=C_{n+m-1}^{n-1}=\frac{\left(n+m-1\right)!} {m!\left(n-1\right)!}.\]

Справедливы следующие свойства числа сочетаний без повторений:

\[C_{n}^{m}=C_{n}^{n-m},\] \[C_{n}^{m}+C_{n}^{m+1}=C_{n+1}^{m+1}.\]

Бином Ньютона

Формула бинома Ньютона имеет вид

\[\left(a+b\right)^{n}=C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b+...+C_{n}^{k}a^{n-k}b^{k}+... +C_{n}^{n}b^{n},\]

или

\[\left(a+b\right)^{n}=a^{n}+na^{n-1}b+...+\frac{n\left(n-1\right)... \left(n-k+1\right)}{k!}a^{n-k}b^{k}+...+b^{n},\]

где: \(n\) – натуральное число и

\[ T_{k-1}=C_{n}^{k}a^{n-k}b^{k}\]

есть \((k-1)\)-й член в разложении бинома \((k=0, 1, 2, …, n)\).

Сумма биномиальных коэффициентов равна

\[C_{n}^{0}+C_{n}^{1}+...+C_{n}^{n}=2^{n}.\]

Если у вас возникли вопросы, пишите - поможем, чем сможем 🙂.