Изменения
sta
# Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
# Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).
# Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
# Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
# Будем называть последовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
# Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
# Докажите, что число мультимножеств из $n$ чисел от $0$ до $n$, сумма которых делится на $n+1$ равно числу Каталана
# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
# Докажите формулу $t^{\overline{n}}=\sum\limits_{k=0}^n\left[n\atop k\right]t^k$
# Докажите формулу $t^n=\sum\limits_{k=0}^n(-1)^{n-k}\left\{n\atop k\right\}t^{\overline k}$
# Придумайте аналогичные двум предыдущим заданиям формулы для $t^{\underline{n}}$.
# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
