1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Вычислите сумму $\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\choose n}^n$.
# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
# (для 31-35) Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
# Докажите формулу $t^{\overline{n}}=\sum\limits_{k=0}^n\left[n\atop k\right]t^k$, где $t^{\overline{n}} = t(t+1)\ldots(t+n-1)$ называется "$n$-й восходящей факториальной степенью $t$".
# Докажите формулу $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))$ ($t^{\underline{n}}$ называется "$n$-й нисходящей факториальной степенью $t$").
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Беспорядком называется перестановка без неподвижных точек. Найдите число беспорядков длины $n$ с помощью формулы включений-исключений.
# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек.
# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками. Не пользуйтесь формулой для подсчета беспорядков, придумайте именно рекуррентную формулу.
# Префиксным максимумом в перестановке называется элемент, который больше всех предыдущих. Выведите рекуррентную формулу для числа перестановок размера $n$ с $k$ префиксными максимумами.
# Транспозицией называется перестановка, которая имеет один цикл длины $2$ и остальные элементы являются неподвижными точками. Перестановка называется чётной, если ее можно представить в виде произведения чётного числа транспозиций. Докажите, что если перестановку можно представить в виде произведения циклов длины 3, то она является чётной.
# Транспозиция называется элементарной, если она переставляет местами два соседних элемента. Докажите, что перестановка является чётной тогда и только тогда, когда любое ее представление в виде произведения элементарных транспозиций содержит чётное число сомножителей.
# Докажите, что перестановка является чётной тогда и только тогда, когда '''любое''' ее представление в виде произведения транспозиций содержит чётное число сомножителей.
# Докажите, что число четных перестановок равно $\frac {n!}{2}$ при $n \ge 2$.
# Инверсией в перестановке $a$ называется пара индексов $i < j$, для которой $a_i > a_j$. Докажите, что перестановка является чётной тогда и только тогда, когда она содержит чётное число инверсий.
# Докажите, что перестановка является чётной тогда и только тогда, когда $n - c$ четно, где $c$ - число циклов в перестановке.
# Докажите, что множество четных перестановок с операцией композиции образует группу.
# Есть две перестановки: первая меняет местами первые два элемента, а вторая делает циклический сдвиг на один. Покажите, что любую перестановку можно выразить, как композицию этих двух (возможно, используя каждую несколько раз).
# Перестановка $[a_1, a_2, \ldots, a_n]$ называется пилообразной, если $a_1 > a_2 < a_3 > a_4 \ldots a_n$. Найдите количество пилообразных перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
# Перестановка $[a_1, a_2, \ldots, a_n]$ называется неразложимой, если у нее ни для какого $0 < k < n$ нет префикса длины $k$, который является перестановкой чисел от 1 до $k$. Найдите количество неразложимых перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
# Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.
# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция отражения и поворота является отражением.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция двух отражений является поворотом.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Зафиксируем конкретную прямую, относительно которой можно делать отражение. Докажите, что композиция любой последовательности отражений и поворотов является либо поворотом, либо композицией поворота и отражения относительно зафиксированной прямой.
# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.
# Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.
# Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.
# Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.
# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
