Основное правило комбинаторики. Перестановки, размещения, сочетания. Бином Ньютона

Комбинаторика – это теория конечных множеств. Основное правило – правило умножения. Пример: нужно совершить путешествие из пункта А в Б, а потом в С. Из а в Б можно попасть 4 способами, а из Б в С только 2. Следовательно, кол-во маршрутов из А в С равно 8. Основное правило умножения: пусть требуется выполнить одно за другим ‘k’ действий. Пусть первое действие можно выполнить n1 способами, второе – n2 способами и … nk способами. Тогда все k действий можно выполнить n1*n2*…*nk способами. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (например, номер элемента с 1, 2, …, до n). Различные упорядоченные множества, которые отличаются лишь порядком элементов, т.е. получены из того же самого множества, называются перестановками этого множества и обозначаются pn=n!. Упорядоченные k элементные подмножества, состоящие из n элементов, называются размещениями. Факториал n! – это произведение n натуральных чисел по основной формуле: n!=(n-1)!*n. Например, 0!=1, 1!=1. Произвольное m-элементное подмножество элементного множества n называется сочетанием из n элементов по m и обозначается С. При подсчете числа сочетаний важно: 1) число элементов m подмножества; 2) различие как минимум у двух подмножеств в элементах (следование элементов не имеет значения). Основная формула: С(m | n)=n!/(m!*(n-m)!). Бином Ньютона – это целая положительная степень суммы двух слагаемых (бинома), представленная в виде суммы степеней этих слагаемых: (a+b)^n=S(n | k=0) C(k | n)*a^(n-k)*b^k.