Изменения
Нет описания правки
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
# Докажите корректность следующего алгоритма построения цепного кода. Начинаем со строки из $n$ нулей. Каждый раз пытаемся жадно приписать 1, если слово из последних $n$ символов уже встречалось раньше, то приписываем 0. Заканчиваем, когда все $2^n$ слов получены.
# Докажите, что $\sum_{k=0}^n C_n^k = 2^n$
# Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$
# Используйте предыдущее задание для альтернативного доказательства формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы.
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
# Коды Грея для размещений. Предложите способ перечисления сочетаний, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
# Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
# Размещение с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок выбора важен. Чему равно число размещений с повторениями из $n$ по $k$?
