1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
# Пусть 2 - множество из двух различных элементов, каждый из которых имеет вес 1. Можно условно называть их черный и белый. Что представляет собой $Seq(2)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Set(2)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $MSet(2)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Cycle(2)$? Посчитайте число элементов для него, в зависимости от веса.
# Пусть $F$ - множество из двух различных элементов, один из которых имеет вес 1, а другой - 2. Можно условно называть их маленький и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.
# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^+(A)$ множество непустых последовательностей из элементов $A$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.
# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^1(A) = Seq^+(A)$, $Seq^k(A) = Seq^+(Seq^{k-1}(A))$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^k(A)$.
# Разбиения на множества. Проинтерпретируйте разбиения $n$-элементного множества на $k$ множеств как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.
# Разбиения на циклы. Проинтерпретируйте разбиения $n$-элементного множества на $k$ циклов как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.
# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.
# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.
# Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.
# Предложите способ посчитать помеченные циклические мультибамбуки.
# Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.
# Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?
# Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов?
# Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
# Докажите, что среди любых 5 точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать 4, которые являются вершинами выпуклого многоугольника.
# Какое число точек необходимо для того, чтобы среди них можно было выбрать 5, являющихся вершинами выпуклого пятиугольник?
# Докажите, что для любого $r$ существует $K(r)$, такое что среди любых $K(r)$ точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать $r$, которые являются вершинами выпуклого многоугольника.
# 🔎 Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.
