Комбінаторика. Біном Ньютона
комбинаторика
факториал нуля равен единице
факториал натурального числа n равен произведению всех натуральных чисел от 1 до n
комбинаторный принцип сложения: пусть имеется "m" типов предметов, причем предмет i-го типа (i: от 1 до m) можно выбрать ni способами, тогда: один предмет ИЛИ 1-го, ИЛИ 2-го,..., ИЛИ m-го типа (т.е. один из имеющихся) можно выбрать n1+n2+...+nm способами (пример: есть три мишки и два зайца, тогда: одну игрушку можно выбрать пятью способами)
комбинаторный принцип умножения: пусть имеется "m" типов предметов, причем предмет i-го типа (i: от 1 до m) можно выбрать ni способами, тогда: И один предмет 1-го типа, И один предмет 2-го типа,..., И один предмет m-го типа (т.е. по одному предмету каждого типа) можно выбрать n1·n2·...·nm способами (пример: есть три мишки и два зайца, тогда: мишку и зайца вместе можно выбрать шестью способами способами)
количество перестановок без повторений из "n" элементов. Перестановка без повторений из "n" элементов – упорядоченный набор из "n" различных элементов
количество размещений без повторений из "n" элементов по "m". Размещение без повторений из "n" элементов по "m" – упорядоченный набор из "m" элементов, выбранных из "n" различных элементов
количество сочетаний без повторений из "n" элементов по "m". Сочетание без повторений из "n" элементов по "m" – набор из "m" элементов, выбранных из "n" различных элементов, в котором не учитывается порядок элементов
симметрия сочетаний (при разложении бинома Ньютона на сумму одночленов, биномиальные коэффициенты, находящиеся на одинаковом расстоянии от середины, равны)
треугольник Паскаля (треугольник из чисел, в каждой строке которого находятся коэффициенты бинома Ньютона степени, равной номеру строки (начиная с нулевой))
Формула, выражающая произвольное число в треугольнике Паскаля через сумму двух чисел над ним, где каждое их этих чисел является количеством сочетаний (формула, позволяющая из биномиальных коэффициентов выстроить треугольник Паскаля)
сумма биномиальных коэффициентов равна 2n
сумма биномиальных коэффициентов с нечетным верхним индексом равна сумме биномиальных коэффициентов с четным верхним индексом, и равна 2n-1
бином Ньютона (формула для представления бинома (суммы двух одночленов) в произвольной степени в виде суммы одночленов)
количество перестановок с повторениями из n элементов, среди которых n1 одинаковых элементов 1-го типа, n2 одинаковых элементов 2-го типа,...,nm одинаковых элементов m-го типа,. Перестановка с повторениями – упорядоченный набор из "n" элементов, считающийся неизменным, если любые два одинаковых элемента поменять местами
количество размещений с повторениями из "n" элементов по "m". Пусть имеется "n" различных типов элементов, причем элемент каждого типа можно брать сколько угодно раз. Размещение с повторениями из "n" элементов по "m" – упорядоченный набор из "m" элементов, выбранных из имеющихся типов элементов
количество сочетаний с повторениями из "n" элементов по "m". Пусть имеется "n" различных типов элементов, причем элемент каждого типа можно брать сколько угодно раз. Сочетание с повторениями из "n" элементов по "m" – набор из "m" элементов, выбранных из имеющихся типов элементов, в котором не учитывается порядок элементов
формула, связывающая количество сочетаний без повторений с количеством перестановок с повторениями