Элементы комбинаторики: рекуррентные соотношения для соответствующих величин; бином Ньютона, свойства биномиальных коэффициентов, треугольни

Рекуррентное соотношение - это соотношение(равенство, система равентсв) позволяющее свести решение комбинационной задачи для некоторого числа предметов к аналогичной задаче с меньшей размерностью.

рекуррентное соотношение для чисел Фибоначчи:

$\begin{displaymath}\begin{array}{rcl} f_0&{}={}&0,\\ f_1&{}={}&1,\\ f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.\\ \end{array} \end{displaymath}$

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n - k} b^k = {n\choose 0}a^n + {n\choose 1}a^{n - 1}b + \dots + {n\choose k}a^{n - k}b^k + \dots + {n\choose n}b^n$

где ${n\choose k}=\frac{n!}{k!(n - k)!}$ — биномиальные коэффициенты, $n$ — неотрицательное целое число.

Все свойства этих коэффициентов согласуются с треугольником Паскаля.

Главное свойство: элементы, стоящие от концов треугольника, равны.

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