Problem set 3: Möbius function
Suppose a function \(f:\mathbb{N}\to\mathbb{R}\) satisfies
\[ \sum_{d\mid n}f(d)= \begin{cases} 1, & n=1,\\ 0, & n\neq 1. \end{cases} \]
Is it necessarily true that
\[ f(n)=\mu(n) \]
for every \(n\in\mathbb{N}\)?
Let
- \(\tau(n)\) denote the number of positive divisors of \(n\);
- \(\sigma(n)\) denote the sum of all positive divisors of \(n\).
Evaluate the following sums.
(a)
\[ \sum_{d\mid n}\sigma(d)\mu\left(\frac{n}{d}\right). \]
(b)
\[ \sum_{d\mid n}\tau(d)\mu\left(\frac{n}{d}\right). \]
For every positive integer \(n\geq 1\), evaluate the sum
\[ \sum_{d\mid n}\mu(d)\ln(d). \]
Let \(\varphi(n)\) denote Euler’s totient function.
(a) Prove Gauss’s identity:
\[ \sum_{d\mid n}\varphi(d)=n. \]
(b) Prove that
\[ \sum_{d\mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}. \]
(c) Using the previous result, derive Euler’s formula
\[ \varphi(n) = n\left(1-\frac{1}{p_1}\right) \cdots \left(1-\frac{1}{p_s}\right), \]
where \(p_1,\ldots,p_s\) are the distinct prime divisors of \(n\).
1 Cyclic Sequences
Let
\[ X=\{b_1,\ldots,b_k\} \]
be an alphabet consisting of \(k\) symbols, and let \(n\in\mathbb{N}\).
Denote by \(T_k(n)\) the number of distinct cyclic sequences of length \(n\) over the alphabet \(X\).
Two sequences are considered equivalent if one can be obtained from the other by a cyclic rotation.
Find \(T_k(n)\) for
\[ n=3,4,5,6,9. \]
Express your answers in terms of \(k\).
Prove the following formulas for the number of cyclic sequences.
(a)
\[ T_k(n) = \sum_{m\mid n} \frac{1}{m} \sum_{d\mid m} \mu(d)k^{m/d}. \]
(b)
\[ T_k(n) = \frac{1}{n} \sum_{d\mid n} \varphi(d)k^{n/d}. \]
Find the number of distinct cyclic binary sequences of length
\[ 2^n. \]
That is, count the cyclic sequences of length \(2^n\) over the alphabet
\[ X=\{0,1\}. \]
How many distinct cyclic sequences of length 10 can be formed using the alphabet
\[ X=\{A,B,C,D,E\} \]
such that exactly four distinct letters appear in each sequence?
Find the number of distinct cyclic sequences of length 9 over the alphabet
\[ X=\{A,B,C,D,E,F\} \]
in which at most two distinct symbols appear.
Consider cyclic sequences of length 6 over the alphabet
\[ X=\{A,B,C,D,E,F,G\}. \]
How many distinct cyclic sequences satisfy both of the following conditions?
- Their period is not equal to 6.
- They contain exactly two distinct symbols.