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

Задача 1.5.1

(1)(2)(3)

Под значком $\displaystyle \sum_{d \mid n}$ подразумевается сумма по всем натуральным делителям числа $n$ .

Определим функцию Мёбиуса $\mu (n)$ следующим образом:

\mu (n) = \begin{cases} 1, & \text{если } n=1; \\ (-1)^k, & \text{если }n\text{ является произведением }k\text{ различных простых делителей;} \\ 0, & \text{если }n\text{ делится на }p^2\text{ для некоторого простого числа }p\text{.} \end{cases}

?

(1)

$\displaystyle \sum_{d \mid n}\mu (d) = \begin{cases} 1, & n=1; \\ 0, & n \neq 1. \end{cases}$

(2)

Найдите сумму значений функции Мёбиуса по тем и только тем делителям числа $n$ , в каноническое разложение которых входит чётное количество простых множителей.

(3)

Формула обращения Мёбиуса. Пусть $f: \mathbb {N} \to \mathbb {R}$ — произвольная функция, $g(n) = \displaystyle \sum_{d \mid n}f(d)$ . Тогда справедлива формула

f(n) = \sum _{d \mid n}\mu (d)g\left(\frac{n}{d}\right) = \sum _{d \mid n}\mu \left(\frac{n}{d}\right)g(d).

Функция Эйлера $\varphi (n)$ определена в п.1.2 (задача 1.2.1).

Задача 1.5.2

(1)(2)

?

(1)

Найдите сумму $\displaystyle \sum_{d \mid n}\varphi (d)$ .

(2)

$\displaystyle \sum_{d \mid n}\frac{\mu (d)}{d} = \left(1-\frac{1}{p_1}\right)\ldots \left(1-\frac{1}{p_s}\right)$ .

Примечание.

?

Заметим, что, применяя формулу обращения Мёбиуса (задача 1.5.1(3)) к функции $\varphi (n)$ , можно немного другим способом доказать формулу для нахождения $\varphi (n)$ (см. утверждение 1.2.1(3)).

Действительно, используя утверждения 1.5.2(1, 2), получаем:

\varphi (n) = \sum _{d \mid n}\mu (d)\frac{n}{d} = n\cdot \sum _{d \mid n}\frac{\mu (d)}{d} = n\left(1-\frac{1}{p_1}\right)\ldots \left(1-\frac{1}{p_s}\right).

Задача 1.5.3

(1)(2)

Обозначим через $T_r(n)$ количество способов раскрасить карусель из $n$ вагончиков в $r$ цветов, т.е. число раскрасок вершин правильного $n$ -угольника в $r$ цветов, если раскраски, совмещающиеся поворотом, неотличимы. При этом

в раскраске могут быть использованы не все цвета;
цвета различны: например, раскраски КККЖ и ЖЖЖК различны.

Приведём более формальное определение. Для любой раскраски карусели можно «разорвать» карусель между любыми двумя вагончиками и записать получившуюся последовательность цветов (раскраску поезда), начиная с места разрыва по часовой стрелке. Например, следующие последовательности соответствуют одной и той же раскраске карусели:

\text{КЖЗС;}\quad \text{ЖЗСК;}\quad \text{ЗСКЖ;}\quad \text{СКЖЗ.}

С другой стороны, из каждой последовательности цветов можно получить раскраску карусели, «склеив» её начало и конец правильным образом.

Циклическим сдвигом последовательности $(a_1, a_2, \ldots , a_n)$ называется последовательность $(a_2, a_3, \ldots , a_1)$ . Раскраской карусели (или, более учёно, циклической последовательностью) называется класс эквивалентности последовательностей с точностью до циклического сдвига.

Итак, $T_r(n)$ — количество циклических последовательностей длины $n$ , элементы которых — числа $1, \ldots , r$ .

?

(1)

Найдите $T_r(n)$ при $n = 3,4,5,6,9$ .

(2)

$2^{2^n-n-1} < T_2(2^n) < 2^{2^n-n}$ .

Задача 1.5.4

(1)(2)

Назовём периодом последовательности минимальное положительное число $d$ , такое что в результате $d$ циклических сдвигов она перейдёт в себя. Аналогично определяется период карусели.

?

(1)

Период последовательности делит её длину.

(2)

Если $d$ делит $n$ , то количество последовательностей длины $n$ и периода $d$ равно количеству последовательностей длины $d$ и периода $d$ .

Задача 1.5.5

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

Обозначим через $M_r(n)$ количество последовательностей длины $n$ и периода $n$ , элементы которых — числа $1, \ldots , r$ .

?

(1)

Найдите $\displaystyle \sum_{d \mid n}M_r(d)$ .

(2)

Выразите $T_r(n)$ через все $M_r(d)$ , где $d \mid n$ .

(3)

$T_r(n) = \displaystyle \sum_{l \mid n}\frac{1}{l}\sum_{d \mid l}\mu (d)r^{l/d}$ .

(4)

$T_r(n) = \dfrac {1}{n}\displaystyle \sum_{d \mid n}\varphi (d)r^{n/d}$ . (Более простой способ доказательства этой формулы приведён в п.1.9, задача 1.9.4(1).)

Задача 1.5.6

(1)(2)

Найдите количество различных раскрасок карусели из $n$ вагончиков в $r$ цветов, в которых

?

(1)

цвет $s$ встречается $n_s$ раз для каждого $s = 1, \ldots , r$ (здесь в качестве ответа принимается формула с суммированием по делителям, аналогичная 1.5.5(3));

(2)

присутствует ровно 4 цвета из $r=5$ данных.

Обращение Мёбиуса