Изменения

# Пусть $<math>R$ </math> и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.

# Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.# Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые# Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые# Приведите другое доказательство формулы включения-исключения на базе формулы $\sum_{i=1}^n (-1)^i C_n^i = -1$.# Сколько существует чисел, не превышающих $n$, которые взаимно просты с числом $n$?# Докажите, что $\max(x_1, \ldots , x_n)$ = $\sum_{i} x_i - \sum_{i < j} \min(x_i, x_j) +$ $\sum_{i < j < k} \min(x_i, x_j, x_k) + \ldots + (-1)^{n-1} \min(x_1, \ldots , x_n)$# Формула обращения Мёбиуса. Пусть $S$ — конечное множество, и пусть $f \colon 2^S \to \mathbb{R}$ — произвольная функция, определенная на совокупности подмножеств $S$ и принимающая вещественные значения. Определим функцию $g \colon 2^S \to \mathbb{R}$ следующим соотношением: $g(Y) = \sum_{X \supseteq Y} f(X)$. Докажите, что $f(Y) = \sum_{X \supseteq Y} (-1)^{|X| - |Y|} \, g(X)$.# Чему равно число сюрьекций из $n$-элементного множества в $m$-элементное?# Сколько существует пар взаимно-простых чисел от $1$ до $n$?# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдивига и отражения.# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.# Коды Прюфера. Рассмотрим процедуру для помеченного неподвешенного дерева. Будем по очереди выбирать лист, помеченный минимальным числом и удалять его из дерева, выписывая число в вершине, с которой он был связан. Таким образом будет выписано $n - 1$ число, последнее выписанное число всегда $n$. Докажите, что различным деревьям соответствуют различные коды Прюфера.# Докажите, что любой код Прюфера соответствует некоторому дереву. Предложите алгоритм восстановления дерева по коду Прюфера. Сделайте вывод о числе помеченных неподвешенных деревьев с $n$ вершинами.# Пусть 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 рода.# Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.# Предложите способ посчитать помеченные циклические мультибамбуки.# Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.# Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?# Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов? = ЭТО НЕ КОНЕЦ, ЭТО ЕЩЕ ТОЛЬКО НАЧАЛО =