14. Числа Каталана.

Числом Каталана наз-ся число различных скобочных структур из n пар скобок.

Если =1, то последовательность чисел К. равна: 1,1,3,5,14,42,132,…

Применение чисел Каталана.

Числа К. перечисляют самые разнообразные комбинаторные объекты. Реализация чисел К. осуществляется диагональной триангуляцией(это разбиение многоугольника на треугольники непересекающимися диагоналями).Еще одна важная реализация чисел К. связана с путями Дика на плоскости (путем Дика называется непрерывная ломанная в верхней полуплоскости, составленная из векторов (1,1) и (1,-1),начинающаяся в начале координат и заканчивающаяся на оси абсцисс). Совершенно ясно, как устанавливается соответствие между путями Дика и правильными скобочными структурами : нужно сопоставить вектору (1,1) левую скобку, а вектору (1,-1) правую. Тогда условие, что путь лежит в верхней полуплоскости и заканчивается на оси абсцисс, и есть в точности условие правильности скобочной структуры. Поэтому число путей Дика из 2n звеньев равно n-му числу Каталана .

15. Полиномиальная формула.

Вывод формулы бинома Ньтона можно получить и др. способом.

Для этого запишем (a+b)ⁿ= . раскроем скобки выписывая многочлены в порядке их появления.

(a+b)²=aa+ba+ab+bb

(a+b)³=aaa+aab+aba+abb+baa+bab+bba+bbb

……………………………………………….

Ясно, что слагаемые в правой части будут произведениями всевозможных перестановок с повторениями длины n из букв a и b, чтобы привести подобные члены нежно найти число перестановок имеющих заданный состав (n₁;n₂) n₁+ n₂=n.

Т.е. это есть ничто иное как P(n₁,n₂) тогда получим суммы слагаемых вида P(n₁,n₂) aⁿ¹ bⁿ². И окончательно (a+b)ⁿ= (1)

Чтобы привести наше равенство (1) к более привычной нам формуле (2)

достаточно положить, что n₂=k, n₁=n-k,

Произведенные доказательства переносятся на случай нескольких слагаемых.

(3)

Формула (3) носит название полиномиальной формулы.

16. Производящие функции и их применения.

В комбинаторном анализе для доказательства различных соотношений широко используется т.к. методы производящих функций.

Производящие функции определяются для последовательностей. Пусть дана конечная или бесконечная последовательность а₀,а₁, а₂,…, а_k. Производящей функцией этой последовательности называется формула A(x)= а₀+а₁x+ а₂x²+…+ а_kx^k+…

Экспотенциальной производящей функцией называется функция

Если последовательность конечна, то производящие функции определяются конечными суммами.

Если последовательность бесконечна, то производящие функции определяются бесконечными рядами, при этом часто пользуются такими функциями и даже в тех случаях когда соответствующие ряды расходятся.

Для последовательности чисел сочетаний из k элементов (без повторений) производящей функцией будет

Экспотенциальной производящей формулой для размещений (без повторений) будет