Math Problems Vault

Problem 1.5.1

(1)(2)(3)

The notation $\displaystyle \sum_{d \mid n}$ denotes the sum over all positive divisors of $n$ .

Define the Möbius function $\mu (n)$ as follows:

\mu (n) = \begin{cases} 1, & \text{if } n=1; \\ (-1)^k, & \text{if }n\text{ is a product of }k\text{ distinct prime divisors;} \\ 0, & \text{if }n\text{ is divisible by }p^2\text{ for some prime number }p\text{.} \end{cases}

?

(1)

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

(2)

Find the sum of the values of the Möbius function over exactly those divisors of $n$ whose canonical factorization contains an even number of prime factors.

(3)

The Möbius inversion formula. Let $f: \mathbb {N} \to \mathbb {R}$ be an arbitrary function, and let $g(n) = \displaystyle \sum_{d \mid n}f(d)$ . Then the following formula holds:

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).

Problem 1.5.2

(1)(2)

Euler's totient function $\varphi (n)$ is defined in Sec.1.2 (Problem 1.2.1).

?

(1)

Find the sum $\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)$ .

Remark.

?

Note that by applying the Möbius inversion formula (Problem 1.5.1(3)) to the function $\varphi (n)$ , one can prove the formula for $\varphi (n)$ in a slightly different way (see Statement 1.2.1(3)).

Indeed, using Statements 1.5.2(1, 2), we obtain:

\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).

Problem 1.5.3

(1)(2)

Denote by $T_r(n)$ the number of ways to color a carousel of $n$ cars in $r$ colors, i.e. the number of colorings of the vertices of a regular $n$ -gon in $r$ colors, where colorings that coincide after a rotation are considered indistinguishable. Here

a coloring need not use all the colors;
the colors are distinguishable: for example, the colorings RRRY and YYYR are different.

Let us give a more formal definition. For any coloring of a carousel, one can ``break'' the carousel between any two cars and write down the resulting sequence of colors (a coloring of a train), starting from the break point and going clockwise. For example, the following sequences correspond to the same coloring of a carousel:

\text{RYGB;}\quad \text{YGBR;}\quad \text{GBRY;}\quad \text{BRYG.}

On the other hand, from every sequence of colors one can obtain a coloring of a carousel by ``gluing'' its beginning and end in the proper way.

The cyclic shift of a sequence $(a_1, a_2, \ldots , a_n)$ is the sequence $(a_2, a_3, \ldots , a_1)$ . A coloring of a carousel (or, in more learned terms, a cyclic sequence) is an equivalence class of sequences up to cyclic shift.

Thus, $T_r(n)$ is the number of cyclic sequences of length $n$ whose elements are the numbers $1, \ldots , r$ .

?

(1)

Find $T_r(n)$ for $n = 3,4,5,6,9$ .

(2)

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

Problem 1.5.4

(1)(2)

The period of a sequence is the smallest positive integer $d$ such that $d$ cyclic shifts map the sequence to itself. The period of a carousel is defined similarly.

?

(1)

The period of a sequence divides its length.

(2)

If $d$ divides $n$ , then the number of sequences of length $n$ and period $d$ equals the number of sequences of length $d$ and period $d$ .

Problem 1.5.5

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

Denote by $M_r(n)$ the number of sequences of length $n$ and period $n$ whose elements are the numbers $1, \ldots , r$ .

?

(1)

Find $\displaystyle \sum_{d \mid n}M_r(d)$ .

(2)

Express $T_r(n)$ in terms of all $M_r(d)$ , where $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}$ . (A simpler proof of this formula is given in Sec.1.9, Problem 1.9.4(1).)

Problem 1.5.6

(1)(2)

Find the number of distinct colorings of a carousel of $n$ cars in $r$ colors in which

?

(1)

color $s$ occurs $n_s$ times for each $s = 1, \ldots , r$ (here a formula with summation over divisors, analogous to 1.5.5(3), is accepted as an answer);

(2)

exactly 4 of the $r=5$ given colors are present.