244
правки
Изменения
Нет описания правки
# Докажите, что число разбиений числа $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$. Докажите, что сопряжение является отношением эквивалентности.
# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.
