Изменения

# Докажите, что $\sum_sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.# Докажите, что $\sum_sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}$.# Докажите, что $\sum_sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.# Докажите, что $\sum_sum\limits_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}$. // Забавно, что нет простого выражения для $\sum_sum\limits_{k=0}^m {r \choose k}$.

# Докажите, что $\sum_ksum\limits_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.# Докажите, что $\sum_ksum\limits_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$# Докажите, что $\sum_ksum\limits_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+n}{s-m \choose n-r}$# Докажите, что $\sum_ksum\limits_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$# Докажите, что $\sum_ksum\limits_k{m-r+s\choose k}{n+r-s \choose n-k}{r+k \choose m+n}={r \choose m}{s \choose n}$# Вычислите сумму $\sum_sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.# Докажите, что $\sum_k sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).# Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.# Будем называть последовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана. # Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.# Укажите способ подсчитать число разбиений заданного $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}} = t (t - 1) \ldots (t-n+1)$.# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые # Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?# Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.# Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые# Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые# Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными# Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.# Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.# Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.# Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?# Пусть $3$ - множество из трёх различных элементов, каждый из которых имеет вес 1. Можно условно называть их красный, синий и зелёный. Что представляет собой $Seq(3)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Set(3)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $MSet(3)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Cycle(3)$? Посчитайте число элементов для него, в зависимости от веса.# Пусть $F$ - множество из трёх различных элементов, два из которых имеют вес 1, а один - 2. Можно условно называть их маленький чёрный, маленький белый и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.# Пусть $U$ - множество, состоящее из одного атома веса 1. Обозначим как $Seq^+(U)$ множество непустых последовательностей из элементов $U$. Выведите формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(U))$.# Пусть $A$ - комбинаторные объекты, $a_i$ - число объектов веса $i$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.# Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.# Укажите, как построить разбиения на слагаемые как конструируемый комбинаторный объект.# Укажите, как построить разбиения на множества как конструируемый комбинаторный объект.# Укажите, как построить разбиения на циклы как конструируемый комбинаторный объект.