Банк задач по математике

Задача 1.9.1

(1)(2)(3)(4)

Раскраски, совмещающиеся вращением пространства (т.е. движением пространства, сохраняющим ориентацию), считаются одинаковыми (кроме п.(3) ниже).

Сколько существует

?

(1)

раскрасок незанумерованных граней куба в красный и серый цвета?

(2)

различных (т.е. неизоморфных) неориентированных графов с 4 незанумерованными вершинами?

(3)

раскрасок в $r$ цветов незанумерованных вершин правильного тетраэдра? Здесь раскраски, совмещающиеся движением пространства (не обязательно сохраняющим ориентацию), считаются одинаковыми.

(4)

раскрасок вершин полного графа на 4 незанумерованных вершинах в $r$ цветов? Здесь раскраски, совмещающиеся перестановкой вершин (т.е. автоморфизмом) этого графа, считаются одинаковыми.

Задача 1.9.2

Для простого $p$ найдите число замкнутых ориентированных связных $p$ -звенных ломаных (возможно, самопересекающихся), проходящих через все вершины данного правильного $p$ -угольника. Ломаные, совмещающиеся поворотом, неотличимы.

?

Задача 1.9.3

(1)(2)(3)

Найдите количество раскрасок карусели из $n$ незанумерованных вагончиков в $r$ цветов (т.е. число раскрасок вершин правильного $n$ -угольника в $r$ цветов, если раскраски, совмещающиеся поворотом, неотличимы) для

?

(1)

$n=5$ ;

(2)

$n=4$ ;

(3)

$n=6$ .

Задача 1.9.4

Найдите количество:

?

(1)

раскрасок карусели из $n$ вагончиков в $r$ цветов (см. формализацию и другое решение в п.1.5, задача 1.5.5);

(2)

$r$ -цветных ожерелий из $n=2k+1$ бусин (ожерелья считаются одинаковыми, если они совмещаются либо поворотом вокруг центра ожерелья, либо осевой симметрией ожерелья);

(3)

раскрасок незанумерованных граней куба в $r$ цветов;

(4)

раскрасок незанумерованных вершин куба в $r$ цветов;

(5)

раскрасок незанумерованных вершин графа $K_{3,3}$ (п.2.1) в $r$ цветов. Раскраски считаются одинаковыми, если они совмещаются автоморфизмом этого графа.

Указание к п.(2)--(5): если не получается, читайте дальше (задачи 1.9.5--1.9.7).

Задача 1.9.5

Перечислите все вращения куба (т.е. вращения пространства, переводящие куб в себя).

?

Задача 1.9.6

Назовём замороженной раскраской раскраску занумерованных граней куба. (Тогда всего имеется $r^6$ замороженных раскрасок.)

?

(1)

Для каждого вращения $s$ куба найдите количество $\mathrm{fix}(s)$ замороженных раскрасок, переходящих в себя при вращении $s$ .

(2)

Найдите количество $P$ пар $(\alpha ,s)$ , в которых $s$ — вращение куба и $\alpha$ — замороженная раскраска, переходящая в себя при вращении $s$ .

(3)

$P = \displaystyle \sum \mathrm{st}\, \alpha$ , где $\mathrm{st}\, \alpha$ — количество вращений куба, переводящих в себя замороженную раскраску $\alpha$ , а суммирование ведётся по всем замороженным раскраскам $\alpha$ .

(4)

Если существует вращение, переводящее замороженную раскраску $\alpha$ в замороженную раскраску $\alpha '$ , то количество таких вращений равно $\mathrm{st}\, \alpha$ .

(5)

Для замороженных раскрасок $\alpha$ и $\alpha '$ , переходящих друг в друга при некотором вращении, $\mathrm{st}\, \alpha = \mathrm{st}\, \alpha '$ .

(Эти равные числа обозначаются $\mathrm{st}\, x$ , где $x$ — соответствующая раскраска незанумерованных граней куба.)

(6)

$P = \displaystyle \sum \mathrm{st}\, x\cdot N_x$ , где $N_x$ — количество замороженных раскрасок, отвечающих раскраске $x$ , а суммирование ведётся по всем раскраскам $x$ незанумерованных граней.

(7)

$\mathrm{st}\, x\cdot N_x$ равно количеству вращений куба для любой раскраски $x$ .

Как сформулировать общий результат, который можно было применять вместо повторения намеченных решений задач 1.9.4(1, 3)?

Задача 1.9.7

Пусть заданы конечное множество $M$ и семейство $\{ g_1, g_2, \ldots , g_n\}$ преобразований этого множества, замкнутое относительно взятия композиции и взятия обратного элемента. Назовём элементы множества $M$ эквивалентными, если один можно перевести в другой одним из данных преобразований. Тогда количество классов эквивалентности равно $\dfrac {1}{n}\displaystyle \sum_{k=1}^{n}\mathrm{fix}(g_k)$ , где $\mathrm{fix}(g_k)$ — количество элементов множества $M$ , которые преобразование $g_k$ переводит в себя.

?

Задача 1.9.8

Найдите количество графов с $n$ вершинами с точностью до изоморфизма. (Ответ можно оставить в виде суммы.)

?

Задача 1.9.9

(1)(2)

?

(1)

Найдите количество $b_n$ отображений $\{ 0,1\}^n \to \{ 0,1\}$ с точностью до перестановки переменных.

(2)

Докажите, что существует $\displaystyle \lim_{n\to \infty }\dfrac {n!\, b_n}{2^{2^n}}$ , и найдите этот предел.

Комбинаторика классов эквивалентности