Редактирование: Список заданий по ДМ 2019 осень

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 132: Строка 132:
 
# Выразите $n \choose k$ через $n-1 \choose k$, $n$ и $k$.
 
# Выразите $n \choose k$ через $n-1 \choose k$, $n$ и $k$.
 
# Докажите, что ${n \choose m}{m \choose k}={n \choose k}{n-k \choose m - k}$.
 
# Докажите, что ${n \choose m}{m \choose k}={n \choose k}{n-k \choose m - k}$.
# Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
+
# Докажите, что $\sum_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
# Докажите, что $\sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}$.
+
# Докажите, что $\sum_{k=0}^n {k \choose m}={n+1 \choose m+1}$.
# Докажите, что $\sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.
+
# Докажите, что $\sum_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.
# Докажите, что $\sum\limits_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}$. // Забавно, что нет простого выражения для $\sum\limits_{k=0}^m {r \choose k}$.
+
# Докажите, что $\sum_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}$. // Забавно, что нет простого выражения для $\sum_{k=0}^m {r \choose k}$.
 
# Обобщите формулу бинома Ньютона на степень суммы трёх: $(x+y+z)^n=?$
 
# Обобщите формулу бинома Ньютона на степень суммы трёх: $(x+y+z)^n=?$
# Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.
+
# Докажите, что $\sum_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.
# Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$
+
# Докажите, что $\sum_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$
# Докажите, что $\sum\limits_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+n}{s-m \choose n-r}$
+
# Докажите, что $\sum_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+n}{s-m \choose n-r}$
# Докажите, что $\sum\limits_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$
+
# Докажите, что $\sum_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$
# Докажите, что $\sum\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_k{m-r+s\choose k}{n+r-s \choose n-k}{r+k \choose m+n}={r \choose m}{s \choose n}$
# Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
+
# Вычислите сумму $\sum_{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$ элементов, в которых нет возрастающей последовательности длины 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))$.
 
# Укажите, как построить разбиения на слагаемые как конструируемый комбинаторный объект.
 
# Укажите, как построить разбиения на множества как конструируемый комбинаторный объект.
 
# Укажите, как построить разбиения на циклы как конструируемый комбинаторный объект.
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)