Math Exercises(sol)

· · 算法·理论

组合数学

$\textbf{sol:}

有 \sqrt{n} = \prod\limits_{i=1}^k p_i^{\frac{a_i}{2}}，因此 \sqrt{n} 为整数当且仅当 \forall i, 2 \mid a_i，即 \prod\limits_{i=1}^k a_i + 1 为奇数。

$\textbf{sol:}

考虑计算不合法的方案，注意到至多只有一个数 > \frac{n}{2}，因此枚举最大的个数，就有答案为 \binom{n+2}{2} - 3 \sum\limits_{i = \frac{n+1}{2}}^n n-i+1

$\textbf{sol:}

对 n+1 个数任意选或不选，但是不能全都不选，有方案数为 2^{n+1} - 1，枚举选的最大的数，就能得到方案数为 \sum\limits_{i=0}^n 2^i，因此 \sum\limits_{i=0}^n 2^i = 2^{n+1} - 1。

改成枚举次大数，就有 \sum\limits_{i=0}^n (n-i) 2^i = 2^{n+1} - 1 - (n+1)，即 \sum\limits_{i=1}^n (n-i) 2^i = 2^{n+1} - 2n - 2。

$\textbf{sol:}

在 n+1 个数中选 3 个，有 \binom{n+1}{3} 种方案，枚举中间那个数，有方案数为 \sum\limits_{i=1}^n i(n-i)，枚举第三个数，有方案数为 \sum\limits_{i=1}^n \binom{i}{2}，因此有 \sum\limits_{i=1}^n i(n-i) = \sum\limits_{i=1}^n \binom{i}{2} = \binom{n+1}{3}。

$\textbf{sol:}

相当于一开始有一个球，每次可以向左边或右边添加一个球，最后给每个球编号，按照出现顺序写下每个编号，就能与题目要求的排列一一对应，因此答案为 2^{n-1}。

$\textbf{sol:}

先删掉 k-1 个数，然后选 k 个数，并在前 k-1 个数后面添加 1 个数，就能得到答案为 \binom{n-k+1}{k}。

考虑依次枚举每个数选或不选，如果 i 不选，则前 i-1 个数有 f_{i-1} 种选择方式，否则 i-1 不能选，因此有 f_{i-2} 种选择方式，因此有 f_{i} = f_{i-1} + f_{i-2}，与斐波那契数列的递推公式相同。

$\textbf{sol:}

考虑写下 \frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}，显然有 n 个分数。对每个分数约分，那么对每个 d，以 d 为分母的分数为 \{ \frac{i}{d}, \gcd(i,d) = 1 \}，因此有 \sum\limits_{d \mid n} \varphi(d) 个分数，所以有 \sum\limits_{d \mid n} \varphi(d) = n。

$\textbf{sol:}

注意到

n^3 = \sum\limits_{i=1}^n i^3 - (i-1)^3 = \sum\limits_{i=1}^n 3 i^2 - 3i + 1 = 3 \sum\limits_{i=1}^n i^2 - 3 \frac{n(n+1)}{2} + n

因此

\sum\limits_{i=1}^n i^2 = \frac{n^3 + 3 \frac{n(n+1)}{2} - n}{3} = \frac{n(n + \frac{1}{2})(n+1)}{3}

类似的

\sum\limits_{i=1}^n i^3 = \frac{n^4 + 6 \frac{n(n + \frac{1}{2})(n+1)}{3} - 4 \frac{n(n+1)}{2} + n}{4} = \frac{n^2 (n+1)^2}{4} $\textbf{sol:}

先在 n 个数里选 m 个，再在选出的 m 个数里选 k 个，等同于现在 n 个数里选 k 个，再在剩下的 n-k 个数里选 m-k 个，因此有 \binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}。

枚举在 m 个数中选的个数，就有 \sum\limits_{k=0}^n \binom{n}{k} \binom{n-k}{m-k} = \sum\limits_{k=0}^m \binom{n}{m} \binom{m}{k} = 2^m \binom{n}{m}。

10.$ 证明 $\binom{2n}{2k} \binom{2n-2k}{n-k} \binom{2k}{k} = \binom{2n}{n} \binom{n}{k}^2 \textbf{sol:} \binom{2n}{2k} \binom{2n-2k}{n-k} \binom{2k}{k} = \binom{2n}{k} \binom{2n-k}{k} \binom{2n-2k}{n-k} = \binom{2n}{k} \binom{2n-k}{n-k} \binom{n}{n-k} = \binom{2n}{n} \binom{n}{k}^2 $\textbf{sol:}

见 6.。

$\textbf{sol:}

先将 n 个 1 分成 k 份，然后转化成不相邻集合的方案数，有答案为 \binom{n-1}{k-1} \binom{m+1}{k}。

$\textbf{sol:}

左边相当于先从 (0,0) 走到 (m+k,r-m-k) 再走到 (m+n,r-m+s-n)，枚举所有 k，就是从 (0,0) 走到 (m+n,r-m+s-n)。

因此有

\sum\limits_{k} \binom{r}{m+k} \binom{s}{n+k} = \sum\limits_{k} \binom{r}{r-m-k} \binom{s}{n+k} = \binom{r+s}{r-m+n} $\textbf{sol:}

枚举走了多少步向上，则有

F(n,m) = \sum\limits_{k=0}^m \binom{m}{k} \binom{n+k}{n-(m-k)} = \sum\limits_{k=0}^m \binom{m}{k} \binom{n+k}{m} $\textbf{sol:} \sum\limits_{k \ge 0} \binom{m-r+s}{k} \binom{n+r-s}{n-k} \binom{r+k}{m+n} = \sum\limits_{k \ge 0} \binom{m-r+s}{k} \binom{n+r-s}{n-k} \sum\limits_{i \ge 0} \binom{r}{m+n-i} \binom{k}{i} = \sum\limits_{i \ge 0} \binom{r}{m+n-i} \sum\limits_{k \ge i} \binom{m-r+s}{i} \binom{m-r+s-i}{k-i} \binom{n+r-s}{n-k} = \sum\limits_{i \ge 0} \binom{r}{m+n-i} \binom{m-r+s}{i} \binom{m+n-i}{n-i} = \sum\limits_{i \ge 0} \binom{r}{m} \binom{r-m}{n-i} \binom{m-r+s}{i} = \binom{r}{m} \binom{s}{n} $\textbf{sol:} (x+1)^{n+1} = \sum\limits_{k} {n+1 \brace k+1} (x+1)^{\underline{k+1}} (x+1)^n = \sum\limits_{k} {n+1 \brace k+1} x^{\underline{k}}

因此

\sum\limits_{k} {n+1 \brace k+1} x^{\underline{k}} = (x+1)^n = \sum\limits_{i \ge 0} \binom{n}{i} x^i = \sum\limits_{i \ge 0} \sum\limits_{k} \binom{n}{i} {i \brace k} x^{\underline{k}}

即

{n+1 \brace k+1} = \sum\limits_{i \ge 0} \binom{n}{i} {i \brace k} 17.$ 证明 $\sum\limits_{i=k}^n {i \brace k} (k+1)^{n-i} = {n+1 \brace k+1}$，且 $\sum\limits_{i=0}^n i {m+i \brace i} = {m+n+1 \brace n} \textbf{sol:} $(2)$ 左式 $= \sum\limits_{i=0}^n {m+i+1 \brace i} - {m+i \brace i-1} = {m+n+1 \brace n} $\textbf{sol:}

由通项公式得 {n \brace 3} = - \frac{1}{2} + \frac{2^n}{2} - 3^n。

$\textbf{sol:} (-x)^k = \sum\limits_{i=0}^k {k \brace i} (-x)^{\underline{i}} = \sum\limits_{i=0}^k {k \brace i} (-1)^i x^{\overline{i}} x^k = \sum\limits_{i=0}^k {k \brace i} (-1)^{k-i} x^{\overline{i}} $\textbf{sol:}

右式相当于枚举每组数第一次出现的位置的差分。

$\textbf{sol:}

左右两式都是在计算将 n 个数分成 k 个一类组和 r 个而类组的方案数，只不过左边是先分成 k+r 组，再对组进行分割，右边是先分成两份，然后再分别分成 k 组和 r 组。

$\textbf{sol:}

相当于先将 n 个数分成 k 组，再按照第一次出现的顺序给每个组编号，由于组内可空，因此答案为 \sum\limits_{i=1}^k \binom{k}{i} {n \brace i}。

$\textbf{sol:}

考虑递推式，当加入第 n 个数时，可以新起一个组，也可以加入之前的除了 n-1 所在的组以外的所有组，因此有 f_{n,k} = f_{n-1,k-1} + (k-1) f_{n-1,k}，边界为 f_{1,1} = 1，不难发现令 f_{n,k} = {n-1 \brace k-1} 就能满足条件，因此方案数为 \sum\limits_{i=1}^n f_{n,i} = \sum\limits_{i=0}^{n-1} {n-1 \brace i} = Bell(n-1)。

$\textbf{sol:}

考虑右边的组合意义：先将 n 划分成 i 个圆排列，再从中选出 k 个。这等同于先选出 i 个数，并将其划分成 k 个圆排列，再在剩下 n-i 个数中任意划分，显然这个方案数是 (n-i)! 个的，因为每个排列都对应着一个圆排列的组合，而 n-i+1 个数的圆排列也是有 (n-i)! 个，因此左边等于先在 n 个中选出 i 个并划分成 k 个圆排列，再将剩下的 n-i 个数和 n+1 一起组成一个圆排列，也就是将 n+1 划分成 k+1 个圆排列。

$\textbf{sol:}

条件等同于每个环的大小不超过 2，因此当加入 n+1 时，可以单独成一个环，也可以和前面的任意一个数成环，即 f(n+1) = f(n) + n f(n-1)。

$\textbf{sol:}

右式 = \sum\limits_{k=n-r+1}^n \binom{n}{k} f(k,r) (n-k)!，即选择 k 个数，让剩下的数和 n+1 成环。

$\textbf{sol:} $(2)$ 可以在 $n-1$ 的最后加上 $n$，或者将有 $k-1$ 个逆序对的排列的 $n$ 向左移动一位，当 $k=n$ 时就不能移了。 $(3)$ 只需要考虑交换前两个数就能改变逆序对个数的奇偶性，且能一一对应，因此有奇数个逆序对的排列数量 $=$ 有偶数个逆序对的排列数量。 --- $28.$ 令 $f(n)$ 表示 $1 \sim n$ 的所有排列 $P$ 满足 $\forall 1 \le k < n, \{ P_1, P_2, \dots, P_k \} \ne \{ 1, 2, \dots, k \}$，证明 $\sum\limits_{i=1}^n f(i) (n-i)! = n!$。 $\textbf{sol:}

条件等价于不存在 1 \le k < n，使得 1 \sim k 和 k+1 \sim n 间完全没有边，因此左式就是在枚举最小的这样的 k，加起来就是所有的排列。

$$ \sum\limits_{i=k}^n {i \brack k} n^{\underline{n-i}} = n! \sum\limits_{i=k}^n \frac{{i \brack k}}{i!} = {n+1 \brack k+1} $$ $$ \sum\limits_{i=0}^n (m+i) {m+i \brack i} = {m+n+1 \brack n} $$ $$ \sum\limits_{k} {n+1 \brack k+1} \binom{k}{m} (-1)^{k-m} = {n \brack m} $$ $$ \sum\limits_{k} {k \brack l} {n-k \brack m} \binom{n}{k} = {n \brack l+m} \binom{l+m}{m} $$ $\textbf{sol:} $(2)$ $\sum\limits_{i=0}^n (m+i) {m+i \brack i} = \sum\limits_{i=0}^n {m+i+1 \brack i} - {m+i \brack i-1} = {m+n+1 \brack n} $(4)$ 两边都是将 $n$ 数分成 $l$ 个一类环和 $m$ 个二类环，只不过左边是先将 $n$ 分成两部分再分别划分成环，右边是先划分成环再分成两部分。 --- $30.$ 令 $f(n,k)$ 表示有多少个 $1 \sim n$ 的排列 $P$ 满足恰好存在 $k-1$ 个 $i$ 使得 $P_i > P_{i+1}$，证明 $f(n,k) = (n-k+1) f(n-1,k-1) + k f(n-1,k)$，并用这个结论证明 $x^n = \sum\limits_{k=0}^n f(n,k) \binom{x+n-k}{n}$，并证明 $f(n,k) = \sum\limits_{i=0}^k (-1)^i \binom{n+1}{i} (k-i)^n$。 $\textbf{sol:} (1)$ 考虑从小到大插入每个数，如果将 $n$ 插在 $k$ 段中的一段的开头，那么 $k$ 不变，否则 $k \gets k+1$，因此有 $f(n,k) = (n-k+1) f(n-1,k-1) + k f(n-1,k) $$\sum\limits_{k \ge 0} f(n,k) \binom{x+n-k}{n} = \sum\limits_{k \ge 0} ((n-k+1) f(n-1,k-1) + k f(n-1,k)) \binom{x+n-k}{n} $$ $$ = \sum\limits_{k \ge 0} f(n-1,k) \left( k \binom{x+n-k}{n} + (n-k) \binom{x+n-k-1}{n} \right) = \sum\limits_{k \ge 0} f(n-1,k) \binom{x+n-k-1}{n-1} x $$ 对于 $n=0$ 结论显然成立，设对于 $n' < n$ 结论成立，就有 $$ \sum\limits_{k \ge 0} f(n,k) \binom{x+n-k}{n} = \sum\limits_{k \ge 0} f(n-1,k) \binom{x+n-k-1}{n-1} x = x \times x^{n-1} = x^n $$ 因此对于 $\forall n \in N$，有结论成立。 $(3)$ 注意到 $$ \sum\limits_{i=0}^k (-1)^i \binom{n+1}{i} (k-i)^n $$ $$ = \sum\limits_{i=0}^k (-1)^i \binom{n+1}{i} \sum\limits_{j \ge 0} f(n,j) \binom{n+k-i-j}{n} $$ $$ = \sum\limits_{i=0}^k \binom{n+1}{i} \sum\limits_{j \ge 0} (-1)^{k-j} f(n,j) \binom{-n-1}{k-i-j} $$ $$ = \sum\limits_{j \ge 0} (-1)^{k-j} f(n,j) \sum\limits_{i=0}^k \binom{n+1}{i} \binom{-n-1}{k-i-j} $$ $$ = \sum\limits_{j \ge 0} (-1)^{k-j} f(n,j) \binom{0}{k-j} $$ $$ = f(n,k) $$ --- $31.$ 令 $f(n,k)$ 为上一题的定义，证明 $\sum\limits_{k=1}^n f(n,k) = n!$，$f(n,k) = f(n,n+1-k)$，$\sum\limits_{k=1}^n k f(n,k) = \frac{(n+1)!}{2} \textbf{sol:} $(2)$ 将序列翻转即可。 $(3)$ 左边可以理解为任意选择一段，并将 $n+1$ 插入他的开头，那么形成的新的排列需要满足 $n+1$ 不在第 $n+1$ 位，且要么 $n+1$ 在第一位，要么 $n+1$ 左边的数比右边的数小，因此当 $n+1$ 在开头或末尾时，满足条件的占一半，当 $n+1$ 在中间时，满足条件的也占一半，因此能够形成的排列占 $1 \sim n+1$ 的所有排列的一半。 --- $32.$ 求有多少个 $1 \sim n$ 的排列 $P$ 使得 $1 \sim k$ 在同一个环里。 $\textbf{sol:}

枚举 1 所在的环的大小，就有答案为

\sum\limits_{i=k}^n \binom{n-k}{i-k} (i-1)! (n-i)! = (n-k)! \sum\limits_{i=k}^m \frac{(i-1)!}{(i-k)!} $\textbf{sol:}

对于每个 i，存在 \binom{n}{i} (i-1)! 个大小为 i 的环，且每个环出现的概率都为 \frac{(n-i)!}{n!}，因此答案为

\sum\limits_{i=1}^n \binom{n}{i} \frac{(i-1)! (n-i)!}{n!} = \sum\limits_{i=1}^n \frac{1}{i} $\textbf{sol:}

加入 n 时，要么和 n-1 的错排中的一个数交换位置，要么存在一个 i 满足 p_i = i 且其他 n-2 个数都是错排，然后交换 n,i，因此有 D_n = (n-1) (D_{n-1} + D_{n-2})。

当 n=1 时结论成立，假设对于 n' < n 时结论成立，那么有 D_{n-2} = \frac{D_{n-1} + (-1)^n}{n-1}，因此

D_n = (n-1) (D_{n-1} + D_{n-2}) = n D_n + (-1)^n

所以对 \forall n \in N_+，结论成立。

定义：令 p(n) 表示将 n 无序拆分成若干个正整数的方案数，注意 1,2 和 2,1 算一种拆分。p(n,k) 表示将 n 拆分成 k 个正整数的方案数，p(n,k,m) 表示将 n 拆分成 k 个不超过 m 的正整数的方案数，p_d(n) 则要求拆分成若干个不同的正整数。

$\textbf{sol:}

左边相当于先拆分出 n-k 个 1，再将剩下的 k 个数分配给 n-k 组。如果 k \le n-k，则就相当于将 k 个数任意拆分，否则会出现拆分出超过 n-k 组的情况。

$\textbf{sol:}

按照从小到大的顺序将第 i 个数增加 i-1，就能将左右两式一一对应。

$\textbf{sol:}

将每个数减小 1，如果最小值是 1，则就是 p_d(n-k,k-1)，否则就是 p_d(n-k,k)，因此有 p_d(n,k) = p_d(n-k,k) + p_d(n-k,k-1)。

$\textbf{sol:}

考虑减去不符合条件的方案数，只需要钦定存在一个数为 1，那么剩下的 n-1 就能随意拆分，因此答案为 p(n) - p(n-1)。

$\textbf{sol:} $(2)$ 类似的，新增一个非负整数变量，就有 $x_1 + x_2 + \dots + x_{k+1} = n$，因此答案为 $\binom{n+k}{k}$。 --- $40.$ 证明当 $n \ge 2$ 时，在所有将 $n$ 无序拆分成若干个 $2$ 的正整数幂次的方案中，恰好有一半是拆分成偶数个数。 $\textbf{sol:}

显然 n=2 时结论成立，假设对 n' < n 时结论成立，则考虑对有 1 的拆分，删去一个 1，否则将每个数折半，而对于 n-1 和 \frac{n}{2} 结论都成立，因此对于 n 结论成立，所以对 n \ge 2 结论成立。

$\textbf{sol:}

令 f_m(n) = \sum\limits_{\sum \lambda = n} f_m(\lambda), g_m(n) = \sum\limits_{\sum \lambda = n} g_m(\lambda)，对于 f_m(n)，考虑加入一个 m，则有 f_m(n) = f_m(n-m) + p(n-m)，因此有 f_m(n) = \sum\limits_{i \ge 1} p(n-im)。对于 g_m(n)，考虑对每个 i，删去 m 个 i，因此有 g_m(n) = \sum\limits_{i \ge 1} p(n-im)，因此有 f_m(n) = g_m(n)，而 f_1(n) = \sum\limits_{i=0}^{n-1} p(i)

$\textbf{sol:}

每次考虑删去最大的数，并将其写在 \lambda 的最后面，然后将剩下数的个数写来 \mu 的最后，并将每个数都减一，就能建立 (\lambda, \mu) 和 m 的拆分的双射。

生成函数

$$ \frac{F(x) + F(-x)}{2} = \sum\limits_{i \ge 0} f_{2i} x^{2i} $$ $$ \frac{F(x) - F(-x)}{2} = \sum\limits_{i \ge 0} f_{2i+1} x^{2i+1} $$ 且 $$ \forall i \in \mathbb{N}, f_{2n+1} = 0 \Leftrightarrow F(x) = F(-x) $$ $$ \forall i \in \mathbb{N}, f_{2n} = 0 \Leftrightarrow F(x) = - F(-x) $$ $\textbf{sol:}

有

F(-x) = \sum\limits_{i \ge 0} (-1)^i f_i x^i

因此

\frac{F(x) + F(-x)}{2} = \sum\limits_{i \ge 0} \frac{1 + (-1)^i}{2} f_i x^i = \sum\limits_{i \ge 0} f_{2i} x^{2i} \frac{F(x) - F(-x)}{2} = \sum\limits_{i \ge 0} \frac{1 - (-1)^i}{2} f_i x^i = \sum\limits_{i \ge 0} f_{2i+1} x^{2i+1} f_{2n+1} = 0 \Leftrightarrow f_{2n+1} x^{2n+1} = (-1)^{2n+1} f_{2n+1} x^{2n+1} \Leftrightarrow F(x) = F(-x) f_{2n} = 0 \Leftrightarrow f_{2n} x^{2n} = - (-1)^{2n} f_{2n} x^{2n} \Leftrightarrow F(x) = - F(-x) $$ f_n = \sum\limits_{k} \binom{m}{k} \binom{m}{n-2k} $$ $\textbf{sol:}

令 G = \sum\limits_{k \ge 0} \binom{m}{k} x^k = (1+x)^m，则

F = G(x^2) G = (1+x^2)^m (1+x)^m = (1+x+x^2+x^3)^m $$ \sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n $$ $\textbf{sol:}

注意到

(-1)^n = \binom{-1}{n} = \sum\limits_{k=0}^n \binom{- \frac{1}{2}}{k} \binom{- \frac{1}{2}}{n-k} = \left( - \frac{1}{4} \right)^n \sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k}

即

\sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n $$ \sum\limits_{n \ge 0} \binom{2n+1}{n} x^n $$ $$ \sum\limits_{n \ge 0} \binom{n}{n/2} x^n $$ $\textbf{sol:}

注意到

\sum\limits_{n \ge 0} \binom{2n}{n-1} x^n = \sum\limits_{n \ge 0} \binom{2n}{n} x^n - \sum\limits_{n \ge 0} \frac{1}{n+1} \binom{2n}{n} x^n

而

\sum\limits_{n \ge 0} \frac{1}{n+1} \binom{2n}{n} x^n =\frac{\int \frac{1}{\sqrt{1-4x}} dx}{x} = \frac{1 - \sqrt{1-4x}}{2x}

因此

\sum\limits_{n \ge 0} \binom{2n+1}{n} x^n = 2 \sum\limits_{n \ge 0} \binom{2n}{n} x^n - \sum\limits_{n \ge 0} \binom{2n}{n-1} x^n = \frac{2}{\sqrt{1-4x}} + \frac{\sqrt{1-4x} - 1}{2x} = \frac{1 - \sqrt{1-4x}}{2x \sqrt{1-4x}}

而

\sum\limits_{n \ge 0} \binom{n}{n/2} x^n = \sum\limits_{n \ge 0} \binom{2n}{n} x^{2n} + x \sum\limits_{n \ge 0} \binom{2n+1}{n} x^{2n} = \frac{1}{\sqrt{1 - 4 x^2}} + \frac{1 - \sqrt{1 - 4 x^2}}{2 x \sqrt{1 - 4 x^2}} = \frac{2x + 1 - \sqrt{1 - 4 x^2}}{2 x \sqrt{1 - 4 x^2}} $\textbf{sol:}

设 G = \sqrt{1-x}，则有

G' = - \frac{1}{2} \frac{\sqrt{1-x}}{1-x} 2(x-1) G' = G 2x G' - 2 G' = G 2(n-1) g_{n-1} - 2n g_n = g_{n-1} g_n = \frac{2n-3}{2n} g_{n-1}

又 g_0 = 1，因此

g_n = \prod\limits_{i=1}^n \frac{2i-3}{2i} = - \frac{(2n-2)!}{2^{2n-1} (n-1)! n!} F = \frac{G(x^2)}{1-x} f_n = 1 - \sum\limits_{i=1}^{n/2} \frac{(2i-2)!}{2^{2i-1} (i-1)! i!}

即

f_{2n} = f_{2n+1} = 1 - \sum\limits_{i=0}^{n-1} \frac{1}{2i+2} \binom{2i}{i} $$ F = \frac{G}{(1-x)^m} \Leftrightarrow G = F (1-x)^m $$ 找出一种反演。 $\textbf{sol:} f_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{-m}{n-k} g_k = \sum\limits_{k=0}^n \binom{m+k-n-1}{n-k} g_k g_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{m}{n-k} f_k $$ F_n(x+y) = \sum\limits_{k \ge 0} \binom{n}{k} F_k(x) F_{n-k}(y) $$ $\textbf{sol:} F_n(x+y) = \sum\limits_{k \ge 0} {n \brack k} \sum\limits_{i=0}^k \binom{k}{i} x^i y^{k-i} = \sum\limits_{i \ge 0} \sum\limits_{j \ge 0} {n \brack i+j} \binom{i+j}{i} x^i y^j \sum\limits_{k \ge 0} \binom{n}{k} F_k(x) F_{n-k}(y) = \sum\limits_{i \ge 0} \sum\limits_{j \ge 0} x^i y^j \sum\limits_{k \ge 0} \binom{n}{k} {k \brack i} {n-k \brack j}

相当于将 n 划分成 i 个一类环和 j 个二类环，枚举 i 类环的总大小就有两式相等。

$\textbf{sol:} F'_k = \sum\limits_{n \ge 0} {n+1 \brack k} \frac{x^n}{n!} = \sum\limits_{n \ge 0} {n \brack k} \frac{x^n}{(n-1)!} + \sum\limits_{n \ge 0} {n \brack k-1} \frac{x^n}{n!} = x F'_k + F_{k-1} F'_k = \frac{F_{k-1}}{1-x}

而

F_0 = 1

因此

F'_1 = \frac{1}{1-x} F_1 = - \ln(1-x) F'_2 = - \frac{\ln(1-x)}{1-x} F_2 = \frac{\ln^2(1-x)}{2}

有

\ln(1-x) = - \sum\limits_{n \ge 1} \frac{1}{n} x^n

因此

F'_2 = \sum\limits_{n \ge 0} x^i H_n F_2 = \sum\limits_{n \ge 1} \frac{H_{n-1}}{n} x^n

即

{n \brack 2} = H_{n-1} (n-1)!

而

F'_3 = \sum\limits_{n \ge 1} x^n \sum\limits_{i=1}^n \frac{H_{i-1}}{i} F_3 = \sum\limits_{n \ge 1} x^n \sum\limits_{i=1}^{n-1} \frac{H_{i-1}}{in}

即

{n \brack 3} = (n-1)! \sum\limits_{i=1}^{n-1} \frac{H_{i-1}}{i} $$ \frac{1}{1-x} = \prod\limits_{i \ge 0} 1 + x^{2^i} $$ $\textbf{sol:}

根据二进制分解，就有右式为 \sum\limits_{i \ge 0} x^i，因此左右相等。

$$ \frac{F'}{F} = \sum\limits_{i \ge 1} \frac{F'_i}{F_i} $$ 并对于 $$ F = \prod\limits_{i \ge 1} \frac{1}{1 - x^i} $$ 计算 $\frac{F'}{F}$。 $\textbf{sol:}

两边取对数，有

\ln F = \sum\limits_{i \ge 1} \ln F_i

再求导，有

\frac{F'}{F} = \sum\limits_{i \ge 1} \frac{F'_i}{F_i}

因此对 F= \prod\limits_{i \ge 1} \frac{1}{1-x^i}，有

\frac{F'}{F} = - \sum\limits_{i \ge 1} \frac{-i x^{i-1}}{1-x^i} = - \sum\limits_{i \ge 1} \sum\limits_{j \ge 1} -i x^{ij-1} $$ f(n) = \sum\limits_{k=1}^n \binom{n-1}{k-1} \frac{n!}{k!} $$ $\textbf{sol:}

相当于对于 1 \sim n 的排列 P，将其划分成 k 段，并将这 k 段无序化，枚举 k 就能得到总方案。

$$ \sum\limits_{k \ge 1} \frac{x^k}{1 - x^k} $$ $\textbf{sol:} \sum\limits_{k \ge 1} \frac{x^k}{1 - x^k} = \sum\limits_{k \ge 1} \sum\limits_{i \ge 1} x^{ki} = \sum\limits_{k \ge 1} d(k) x^k $$ \prod\limits_{n \ge 1} (1 - x^n)^{- \frac{\mu(n)}{n}} $$ $\textbf{sol:} \prod\limits_{n \ge 1} (1 - x^n)^{- \frac{\mu(n)}{n}} = \exp(\sum\limits_{n \ge 1} - \frac{\mu(n)}{n} \ln(1-x^n)) = \exp(\sum\limits_{n \ge 1} \frac{\mu(n)}{n} \sum\limits_{i \ge 1} \frac{1}{i} x^{ni}) = \exp(\sum\limits_{n \ge 1} \frac{1}{n} x^n \sum\limits_{d \mid n} \mu(d)) = e^x $\textbf{sol:}

相当于有 1 \sim n 种物品，第 i 个物品的重量为 i，每个物品可以取或不取，因此 f_n 为 n 的不同划分的方案数。

$\textbf{sol:} F = 1 + \prod\limits_{n \ge 0} \frac{1}{1 - x^{2^n}} = 1 + \frac{1}{\sum\limits_{n \ge 0} (-1)^{popcount(n)} x^n} G = \frac{1}{1-x} F = \frac{1}{1-x} + \frac{1}{1 + \sum\limits_{n \ge 1} \left( (-1)^{popcount(n)} - (-1)^{popcount(n-1)} \right) x^n} $\textbf{sol:}

对 A 的逆矩阵 B，显然有 b_{i,i} = a_{i,i}^{-1}，因此 A 的主对角线非 0，那么

\sum\limits_{k=j}^i a_{i,k} b_{k,j} = 0 b_{i,j} = - a_{i,i}^{-1} \sum\limits_{k=j}^{i-1} a_{i,k} b_{k,j}

可以推出整个 B。

$$ \forall m \in \mathbb{Z}, P^m_{n,k} = \binom{n}{k} m^{n-k} $$ $\textbf{sol:}

对 m=0，显然成立，那么考虑归纳，对 m>0，有

P^m_{i,j} = \sum\limits_{k=1}^n \binom{i}{k} \binom{k}{j} (m-1)^{k-j} = \binom{i}{j} \sum\limits_{k=1}^n \binom{i-j}{k-j} (m-1)^{k-j} = \binom{i}{j} m^{i-j}

而根据二项式反演，有 P^{-1} = \{ (-1)^{n-k} \binom{n}{k} \}，因此对 m<0，有

P^m_{i,j} = \sum\limits_{k=1}^n (-1)^{i-k} \binom{i}{k} \binom{k}{j} (m+1)^{k-j} = (-1)^{i-j} \binom{i}{j} \sum\limits_{k=1}^n \binom{k-i}{j-i} (-m-1)^{k-j} = \binom{i}{j} m^{i-j} $$ \sum\limits_{k=0}^n (-1)^k \binom{n}{k} (x-k)^n = n! $$ $\textbf{sol:} \sum\limits_{k=0}^n (-1)^k \binom{n}{k} (x-k)^n = \sum\limits_{k=0}^n (-1)^k \binom{n}{k} \sum\limits_{i=0}^n \binom{n}{i} k^i x^{n-i} = \sum\limits_{i=0}^n \binom{n}{i} x^{n-i} \sum\limits_{k=0}^n (-1)^k \binom{n}{k} k^i = \sum\limits_{i=0}^n \binom{n}{i} x^{n-i} n! {i \brace n} = n! $$ x^{\overline{n}} = \sum\limits_{k=0}^n L_{n,k} x^{\underline{k}} $$ $\textbf{sol:} x^{\overline{n}} = \sum\limits_{k=0}^n {n \brack k} x^k = \sum\limits_{k=0}^n \sum\limits_{i=0}^k {n \brack k} {k \brace i} x^{\underline{i}} = \sum\limits_{i=0}^n \left( \sum\limits_{k} {n \brack k} {k \brace i} \right) x^{\underline{i}}

因此

L_{n,k} = \sum\limits_{i} {n \brack i} {i \brace k}

考虑 L_{n,k} 的组合意义，即枚举 i，将 1 \sim n 划分成 i 个环，并将 i 分成 k 组，等同于先将 n 分成 k 组，这 k 组可以任意排列，因此有

L_{n,k} = \binom{n-1}{k-1} \frac{n!}{k!} $\textbf{sol:} x^{\underline{n}} = \sum\limits_{k=0}^n (-1)^{n-k} {n \brack k} x^k = \sum\limits_{k=0}^n \sum\limits_{i=0}^k (-1)^{n-i} {n \brack k} {k \brace i} x^{\overline{i}} = \sum\limits_{i=0}^n (-1)^{n-i} L_{n,i} x^{\overline{i}}

因此

f_n = \sum\limits_{k=0}^n L_{n,k} g_k \Leftrightarrow g_n = \sum\limits_{k=0}^n (-1)^{n-k} L_{n-k} f_k $$ L_{n+1,k+1} = \sum\limits_{i=0}^n L_{i,k} (n+k+1)^{\underline{n-i}} $$ $\textbf{sol:}

根据 L_{n,k} 的组合意义 ，左边就是在枚举第 k+1 组的最小数。

$\textbf{sol:}

见 19.。

$$ (x+1)^{\overline{n}} = \sum\limits_{k=0}^n L_{n+1,k+1} (x-1)^{\underline{k}} $$ $\textbf{sol:}

注意到

(x+1)^{\overline{n}} = x^{\overline{n+1}}, (x-1)^{\underline{k}} = x^{\underline{k+1}}

根据 L_{n,k} 的反演公式即可。

$$ \sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}^{-1} = \frac{m+1}{m+1-n} $$ 并通过二项式反演找到另一个公式。 $\textbf{sol:}

当 n=0 时结论成立，考虑归纳，有

\sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}^{-1} = 1 + \frac{n}{m} \sum\limits_{k=0}^{n-1} \binom{n-1}{k} \binom{m-1}{k}^{-1} = \frac{m+1}{m+1-n}

根据二项式反演，有

\binom{m}{n}^{-1} = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} \frac{m+1}{m+1-k} $$ f_n = \sum\limits_{k=0}^{n/2} \binom{n}{k} g_{n-2k} \Leftrightarrow g_n = \sum\limits_{k=0}^{n/2} (-1)^k \frac{n}{n-k} \binom{n-k}{k} f_{n-2k} $$ $\textbf{sol:} \sum\limits_{k=0}^{n/2} (-1)^k \frac{n}{n-k} \binom{n-k}{k} \sum\limits_{i=0}^{n/2-k} \binom{n-2k}{i} g_{n-2k-2i} = \sum\limits_{k=0}^{n/2} g_{n-2k} \sum\limits_{i=0}^k (-1)^i \frac{n}{n-i} \binom{n-i}{n-2i} \binom{n-2i}{n-k-i} = \sum\limits_{k=0}^{n/2} g_{n-2k} \sum\limits_{i=0}^k (-1)^i \frac{n}{n-i} \binom{n-i}{k} \binom{k}{i} = g_n + \sum\limits_{k=1}^{n/2} g_{n-2k} \frac{n}{k} \sum\limits_{i=0}^k (-1)^i \binom{n-i-1}{k-1} \binom{k}{i} = g_n + \sum\limits_{k=1}^{n/2} g_{n-2k} \frac{n}{k} \sum\limits_{i=0}^k \binom{n-i-1}{k-1} \binom{-k+i-1}{-k-1} = g_n + \sum\limits_{k=1}^{n/2} g_{n-2k} \frac{n}{k} \binom{n-k-2}{n-k} = g_n

因此结论成立。

$\textbf{sol:}

设

H = \sum\limits_{k \ge 0} \binom{m+k}{k} x^k = (-1)^k \binom{-m-1}{k} x^k = (1-x)^{-m-1}

那么

H^{-1} = (1-x)^{m+1} = \sum\limits_{k \ge 0} (-1)^k \binom{m+1}{k} x^k

因此

g_n = \sum\limits_{k=0}^n (-1)^k \binom{m+1}{k} f_{{n-k}} $\textbf{sol:} $$ P_X = 2^{-n} \sum\limits_{k \ge 0} \binom{n}{k} x^k = (\frac{1}{2} + \frac{x}{2})^n $$ $$ \mathbb{E} X = P'_X(1) = \frac{n}{2} $$ $$ \operatorname{Var} X = P''_X(1) + P'_X(1) - P'^2_X(1) = \frac{n}{4} $$ --- $28.$ 令 $X$ 和 $Y$ 为相互独立的随机变量，证明 $P_{X+Y} = P_X \cdot P_Y$。 $\textbf{sol:} P_X \cdot P_Y = \sum\limits_{k \ge 0} x^k \sum\limits_{i=0}^k \operatorname{Prob}(X = i) \operatorname{Prob}(Y = k-i)

即枚举 X 和 Y 的取值，因此上式 = P_{X+Y}。

$\textbf{sol:}

第 n 次第一次正面向上的概率为 2^{-n}，因此

P_X = \sum\limits_{n \ge 0} 2^{-n} x^n = \frac{2}{2-x} \mathbb{E} X = P'_X(1) = 2 \operatorname{Var} X = P''_X(1) + P'_X(1) - P'^2_X(1) = 2 $$ 1 + \sum\limits_{k \ge 1} \mu_k \frac{x^k}{k!} = P_X(e^x) $$ $\textbf{sol:} P_X(e^x) = \sum\limits_{n \ge 0} \operatorname{Prob}(X = n) \sum\limits_{i \ge 0} \frac{(nx)^i}{i!} = \sum\limits_{i \ge 0} \frac{x^i}{i!} \sum\limits_{n \ge 0} \operatorname{Prob}(X = n) n^i = \sum\limits_{k \ge 0} \mu_k \frac{x^k}{k!} $\textbf{sol:}

根据 \min - \max 容斥，答案为

\sum\limits_{i=1}^6 (-1)^{i+1} \binom{6}{i} \frac{6}{i} = 14.7 $\textbf{sol:}

由于长度为 n 且没有相邻的 1 的 01 序列有 f_{n+2} 个，其中 f 表示斐波那契数列，因此 X=n 的方案数为 f_{n-1}，即

P_X = \sum\limits_{n \ge 1} 2^{-n} f_{n-1} x^n = \frac{x^2}{4-2x-x^2} \mathbb{E} X = P'_X(1) = 4 \operatorname{Var} X = P''_X(1) + P'_X(1) - P'^2_X(1) = 40 $\textbf{sol:}

对于任意四个点，他们之间两两连线且有交点只有一种情况，因此每个交点出现的概率为 \frac{f_{n-2}}{f_n}，其中 f_n 为 n 个点的连线个数，有 f_n = (2n-1)!!，因此

\mathbb{E} X = \binom{2n}{4} \frac{f_{n-2}}{f_n} = \binom{2n}{4} \frac{1}{(2n-1)(2n-3)} = \frac{n(n-1)}{6}

考虑枚举任意两个交点，可能是两条线同时交于一条线，也可能是四条线两两相交，因此

\mathbb{E} X^2 = 12 \binom{2n}{6} \frac{f_{n-3}}{f_n} + \binom{2n}{4} \binom{2n-4}{4} \frac{f_{n-4}}{f_n} + \mathbb{E} X \mathbb{E} X^2 = 12 \binom{2n}{6} \frac{1}{(2n-1)(2n-3)(2n-5)} + \binom{2n}{4} \binom{2n-4}{4} \frac{1}{(2n-1)(2n-3)(2n-5)(2n-7)} + \mathbb{E} X \mathbb{E} X^2 = \frac{4 n!}{5 (n-3)!} + \frac{n!}{36 (n-4)!} + \mathbb{E} X \operatorname{Var} X = \mathbb{E} X^2 - \mathbb{E}^2 X = \frac{4 n!}{5 (n-3)!} + \frac{n!}{36 (n-4)!} + \frac{n!}{6 (n-1)!} - \frac{n!^2}{36 (n-1)!^2} $\textbf{sol:}

令 f_n 表示一开始两个点相距 1，且 n 步后第一次重合的概率，g_n 则表示两个点相距 2，则有

F = \frac{3}{4} x F + \frac{1}{4} x G G = \frac{1}{2} x G + \frac{1}{4} x F + \frac{1}{4} x

因此有

F = \frac{x^2}{16 - 20 x + 5 x^2}, G = \frac{4 x^2 - 3 x^3}{16 x - 20 x^2 + 5 x^3} \mathbb{E} X = F'(1) = 12 \operatorname{Var} X = F''(1) + \mathbb{E} X - \mathbb{E}^2 X = 100

数论函数

若无特殊定义，默认所有变量都为正整数，p 为质数，k 为 n 的不同质因数的个数，p_i 为 n 的第 i 大的质因数，n = \prod\limits_{i=1}^k p_i^{c_i}，P 为质数集合。

$(1)$ $2\varphi(n) = n (2)$ $\varphi(n) = \varphi(2n) (3)$ $\varphi(n) = 12 \textbf{sol:} $$ \varphi(n) = \frac{n}{2} \prod\limits_{p \mid n, p \ne 2} (1 - p^{-1}) \le \frac{n}{2} $$ 取等当且仅当 $p$ 没有非 $2$ 的质因数，因此 $2 \varphi(n) = n$ 当且仅当 $n = 2^k$，其中 $k$ 是正整数。 $(2)$ 对奇数 $n$，有 $$ \varphi(2n) = 2n \prod\limits_{p \mid 2n} (1 - p^{-1}) = n \prod\limits_{p \mid 2n, p \ne 2} (1 - p^{-1}) = \varphi(n) $$ $(3)$ 注意到 $$ 12 = 2^2 \times 3 = 2 \times (2-1) \times 3 \times (3-1) = \varphi(36) $$ $$ 12 = 2 \times (2-1) \times (7-1) = \varphi(28) $$ --- $2.$ 证明 $$ \frac{n}{\varphi(n)} = \sum\limits_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} $$ $\textbf{sol:} \sum\limits_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \sum\limits_{S \mid n} \prod\limits_{p \in S} \frac{1}{p-1} = \prod\limits_{p \mid n} (1 + \frac{1}{p-1}) = \prod\limits_{p \mid n} \frac{p}{p-1} = \frac{n}{\varphi(n)} $$ f(n) = 0 \text{ or } f(n) = 1 $$ $\textbf{sol:} f(n) = \sum\limits_{d \mid n} \mu(d) v(\frac{n}{d}) = \sum\limits_{d \mid n} \sum\limits_{p \mid \frac{n}{d}} \mu(d) = \sum\limits_{p \mid n} \sum\limits_{d \mid \frac{n}{p}} \mu(d) = [n \in P] $$ \sum\limits_{d^k \mid n} \mu(d) = [\not\exists m>1, m^k \mid n] $$ $\textbf{sol:}

设 m 为最大的正整数使得 m^k \mid n，则有

\sum\limits_{d^k \mid n} \mu(d) = \sum\limits_{d \mid m} \mu(d) = [m = 1] $$ \forall p, n > 1, \sum\limits_{d \mid n} \mu(d) \mu(\gcd(p,d)) = 2 [\exists k \ge 1, n = p^k] $$ $\textbf{sol:}

令 m 为最大的数使得 m \mid n, p \not\mid m，有

\sum\limits_{d \mid n} \mu(d) \mu(\gcd(d,p)) = \sum\limits_{d \mid m} \mu(d) - \sum\limits_{d \mid m} \mu(d) \mu(p) = 2[m=1]

而 m=1 当且仅当 n=p^k。

$$ \varphi(x,n) = \sum\limits_{i=1}^x [\gcd(i,n) = 1] $$ 证明 $$ \varphi(x,n) = \sum\limits_{d \mid n} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor \tag{1} $$ $$ \sum\limits_{d \mid n} \varphi(\frac{x}{d}, \frac{n}{d}) = \lfloor x \rfloor \tag{2} $$ $\textbf{sol:} (1) \varphi(x,n) = \sum\limits_{i=1}^x [\gcd(i,n) = 1] = \sum\limits_{i=1}^x \sum\limits_{d \mid i, d \mid n} \mu(d) = \sum\limits_{d \mid n} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor $$ A(d) = \sum\limits_{i=1}^x [\gcd(i,n) = d] $$ 显然所有 $A(d)$ 对 $1 \sim x$ 进行了划分，因此有 $$ \lfloor x \rfloor = \sum\limits_{d \mid n} A(d) = \sum\limits_{d \mid n} \varphi(\frac{x}{d}, \frac{n}{d}) $$ --- $7.$ 证明 $$ \prod\limits_{d \mid n} d = n^{\frac{d(n)}{2}} $$ $\textbf{sol:} \left( \prod\limits_{d \mid n} d \right)^2 = \prod\limits_{d \mid n} d \prod\limits_{d \mid n} \frac{n}{d} = \prod\limits_{d \mid n} n = n^{d(n)} \prod\limits_{d \mid n} d = n^{\frac{d(n)}{2}} $\textbf{sol:}

显然除了 \sqrt{n} 以外的所有因数都可以两两分组，每组都是 d 和 \frac{n}{d}，因此 d(n) 为奇数当且仅当 \sqrt{n} 为整数。

$$ \sum\limits_{d \mid n} d(d)^3 = \left( \sum\limits_{d \mid n} d(d) \right)^2 $$ $\textbf{sol:}

令 n = p^k，有

\sum\limits_{d \mid p^k} d(d)^3 = \sum\limits_{i=0}^k (i+1)^3 = \left( \frac{(k+1)(k+2)}{2} \right)^2 = \left( \sum\limits_{i=0}^k (i+1) \right)^2 = \left( \sum\limits_{d \mid p^k} d(d) \right)^2

由于 d^3 * 1 和 (d * 1)^2 都是积性函数，因此对任意 n 都成立。

$$ \varphi_k(n) = \sum\limits_{i=1}^n [\gcd(i,n) = 1] i^k $$ 证明 $$ \sum\limits_{d \mid n} \frac{\varphi_k(d)}{d^k} = n^{-k} \sum\limits_{i=1}^n i^k $$ $\textbf{sol:}

对 n 的所有因数 d，设

A(d) = \sum\limits_{i=1}^n [\gcd(i,n) = d] i^k \sum\limits_{i=1}^n i^k = \sum\limits_{d \mid n} A(d) = \sum\limits_{d \mid n} d^k \varphi_k(\frac{n}{d}) $\textbf{sol:} \varphi_1(n) = \sum\limits_{i=1}^n [\gcd(i,n) = 1] i = \sum\limits_{i=1}^n i \sum\limits_{d \mid i, d \mid n} \mu(d) = \sum\limits_{d \mid n} d \mu(d) \frac{\frac{n}{d} (\frac{n}{d} + 1)}{2} = \frac{n}{2} \sum\limits_{d \mid n} \mu(d)(\frac{n}{d} + 1) = \frac{n}{2} \varphi(n) \varphi_2(n) = \sum\limits_{i=1}^n [\gcd(i,n) = 1] i^2 = \sum\limits_{d \mid n} d^2 \mu(d) \frac{\frac{n}{d} (\frac{n}{d} + \frac{1}{2}) (\frac{n}{d} + 1)}{3} = \frac{n^3}{3} \sum\limits_{d \mid n} \frac{\mu(d)}{d} + \frac{n^2}{2} \sum\limits_{d \mid n} \mu(d) + \frac{n}{6} \sum\limits_{d \mid n} d \mu(d) = \frac{n^2}{3} \varphi(d) + \frac{n}{6} \prod\limits_{p \mid n} ( 1 - p) \varphi_3(n) = \sum\limits_{d \mid n} d^3 \mu(d) \frac{(\frac{n}{d})^2(\frac{n}{d} + 1)^2}{4} = \frac{n^2}{4} \sum\limits_{d \mid n} d \mu(d) (\frac{n}{d} + 1)^2 = \frac{n^4}{4} \sum\limits_{d \mid n} \frac{\mu(d)}{d} + \frac{n^3}{2} \sum\limits_{d \mid n} \mu(d) + \frac{n^2}{4} \sum\limits_{d \mid n} d \mu(d) = \frac{n^3}{4} \varphi(n) + \frac{n^2}{4} \prod\limits_{p \mid n} (1 - p) $$ J_k(n) = n^k \prod\limits_{p \mid n} (1 - p^{-k}) $$ 证明 $$ J_k(n) = \sum\limits_{d \mid n} \mu(d) \left( \frac{n}{d} \right)^k $$ $$ n^k = \sum\limits_{d \mid n} J_k(d) $$ $\textbf{sol:} \sum\limits_{d \mid p^c} J_k(d) = 1 + \sum\limits_{i=1}^c p^{ik} (1 - p^{-k}) = p^{ck}

而显然 J_k 是积性函数，因此有

n^k = \sum\limits_{d \mid n} J_k(d)

根据莫比乌斯反演，有

J_k(n) = \sum\limits_{d \mid n} \mu(d) \left( \frac{n}{d} \right)^k $$ \prod\limits_{1 \le i \le n, \gcd(i,n) = 1} i = n^{\varphi(n)} \prod\limits_{d \mid n} \left( \frac{d!}{d^d} \right)^{\mu(\frac{n}{d})} $$ $\textbf{sol:} n^{\varphi(n)} \prod\limits_{d \mid n} \prod\limits_{i=1}^d \left( \frac{i}{d} \right)^{\mu(\frac{n}{d})} = n^{\varphi(n)} \prod\limits_{d \mid n} \prod\limits_{1 \le i \le n, \gcd(i,n) = 1} \left( \frac{i}{d} \right)^{\sum\limits_{k \mid \frac{n}{d}} \mu(k)} = n^{\varphi(n)} \prod\limits_{1 \le i \le n, \gcd(i,n) = 1} \frac{i}{n} = \prod\limits_{1 \le i \le n, \gcd(i,n) = 1} i $$ D(n) = \sum\limits_{d \mid n} \varphi(d) d(\frac{n}{d}) $$ 并对所有正整数 $k$ 找到 $\sigma_k$ 的递推公式 $\textbf{sol:} D = 1 * \text{id} = 1 * 1 * \varphi = d * \varphi

而

\sigma_k = 1 * \text{id}_k = 1 * 1 * J_k = d * J_k

即

\sigma_k(n) = \sum\limits_{d \mid n} d^k d(\frac{n}{d}) \prod\limits_{p \mid d} (1 - p^{-k}) $$ F(n) = \prod\limits_{d \mid n} f(d) $$ 证明 $F$ 也是积性函数。 $\textbf{sol:}

对 \gcd(n,m) = 1，有

F(nm) = \prod\limits_{c \mid nm} f(c) = \prod\limits_{a \mid n} \prod\limits_{b \mid m} f(ab) = \left( \prod\limits_{a \mid n} f(a) \right) \left( \prod\limits_{b \mid m} f(b) \right) = F(n) F(m) $$ \forall p,c \ge 2, f^{-1}(p^c) = 0 $$ $\textbf{sol:}

对完全积性函数 f，有

f^{-1}(p^c) = (\mu f) (p^c) = 0

而若

\forall p, c \ge 2, f^{-1}(p^c) = 0

则考虑用归纳法证明 f(p^c) = f(p)^c，显然对 c \le 1 成立，那么假设对所有 <c 的都成立，就有

0 = \sum\limits_{d \mid p^c} f(\frac{p^c}{d}) f^{-1}(d) = f(p^c) - f(p^{c-1}) f(p) = f(p^c) - f(p)^c f(p^c) = f(p)^c

因此 f 为完全积性函数。

$$ f (g * h) = (f g) * (fh) $$ $\textbf{sol:} (f (g*h))(n) = f(n) \sum\limits_{d \mid n} g(d) h(\frac{n}{d}) = \sum\limits_{d \mid n} f(d) g(d) f(\frac{n}{d}) h(\frac{n}{d}) = (f g)*(f h) $$ (f \mu) * (f \mu^{-1}) = \varepsilon $$ 证明 $f$ 是完全积性函数。 $\textbf{sol:}

考虑用归纳法证明 f(p^c) = f(p)^c，对 c \le 1 显然成立，那么假设对 <c 结论成立，就有

0 = \sum\limits_{d \mid p^c} f(d) \mu(d) f(\frac{p^c}{d}) = f(p^c) - f(p) f(p^{c-1}) f(p^c) = f(p)^c

因此 f 为完全积性函数。

$$ (f g)^{-1} = f g^{-1} $$ $\textbf{sol:}

对 n=1，结论显然成立。对 n>1，有

\sum\limits_{d \mid n} f(d) g^{-1}(d) f(\frac{n}{d}) g(\frac{n}{d}) = f(n) [n = 1] = 0

因此

f g^{-1} = (fg)^{-1} $$ (f \mu)^{-1} = f I $$ 证明 $f$ 是完全积性函数。 $\textbf{sol:}

考虑用归纳法证明 f(p^c) = f(p)^c，对 c \le 1 显然成立，那么假设对 <c 结论成立，就有

0 = \sum\limits_{d \mid p^c} f(d) \mu(d) f(\frac{n}{d}) = f(p^c) - f(p) f(p^{c-1}) f(p^c) = f(p)^c

因此 f 为完全积性函数。

$$ \sum\limits_{k=1}^n f(\gcd(k,n)) = \sum\limits_{d \mid n} f(d) g(\frac{n}{d}) $$ 并借此证明 $$ \sum\limits_{k=1}^n \gcd(k,n) \mu(\gcd(k,n)) = \mu(n) $$ $\textbf{sol:} \sum\limits_{k=1}^n f(\gcd(k,n)) = \sum\limits_{d \mid n} f(d) \varphi(\frac{n}{d})

取 g = \varphi 即可。

而

\sum\limits_{k=1}^n \gcd(k,n) \mu(\gcd(k,n)) = \sum\limits_{d \mid n} d \mu(d) \varphi(\frac{n}{d})

那么有

(\text{id} \mu * \varphi)(p) = \varphi(p) - p = -1 = \mu(p)

对 c>1，有

(\text{id} \mu * \varphi)(p^c) = \varphi(p^c) - p \varphi(p^{c-1}) = 0 = \mu(p^c)

因为 \text{id}, \mu, \varphi 都是积性函数，因此 \text{id} \mu * \varphi 为积性函数，因此 \text{id} \mu * \varphi = \mu。

$$ f(p^{c+1}) = f(p) f(p^c) - g(p) f(p^{c-1}) $$ 证明 $$ f(n) f(m) = \sum\limits_{d \mid n, d \mid m} g(d) f(\frac{nm}{d^2}) $$ $\textbf{sol:}

注意到

f(p^a) f(p) = f(p^{a+1}) + g(p) f(p^{a-1}) = \sum\limits_{d \mid p} g(d) f(\frac{p^a p}{d})

考虑归纳法，即假设 <b 都有结论成立，那么有

f(p^a) f(p^b) = f(p^a) (f(p) f(p^{b-1}) - g(p) f(p^{b-2})) = f(p) \sum\limits_{i=0}^{b-1} g(p^i) f(p^{a-i+b-1-i}) - g(p) \sum\limits_{i=0}^{b-2} g(p^i) f(p^{a-i+b-2-i}) = \sum\limits_{i=0}^{b-1} g(p)^i (f(p^{a-i+b-i}) + g(p) f(p^{a-i+b-i-2})) - \sum\limits_{i=0}^{b-2} g(p)^{i+1} f(p^{a-i+b-2-i}) = \sum\limits_{i=0}^b g(p^i) f(p^{a-i+b-i})

若 \gcd(n,n') = \gcd(m,m') = 1，那么有

\left( \sum\limits_{d \mid n, d \mid m} g(d) f(\frac{nm}{d^2}) \right) \left( \sum\limits_{d \mid n', d \mid m'} g(d) f(\frac{n' m'}{d^2}) \right) = \sum\limits_{d \mid \gcd(n,m), d' \mid \gcd(n',m')} g(d) g(d') f(\frac{nm}{d^2}) f(\frac{n' m'}{d'^2}) = \sum\limits_{d \mid \gcd(n,m), d' \mid \gcd(n',m')} g(d d') f(\frac{n m n' m'}{d^2 d'^2}) = \sum\limits_{d \mid \gcd(n n', m m')} g(d) f(\frac{n n' m m'}{d^2})

因此等式两边都是积性函数，因此对任意 n 结论都成立。

$$ \lambda(n) = \sum\limits_{d^2 \mid n} \mu(\frac{n}{d^2}) $$ $\textbf{sol:}

令 f(n) = [n \text{ is a square}]，那么

\sum\limits_{i=0}^c \mu(p^i) f(p^{c-i}) = f(p^c) - f(p^{c-1})

而当 c 为偶数时上式为 1，否则上式为 -1，因此

\lambda(p^c) = \sum\limits_{d \mid n} \mu(d) f(\frac{n}{d})

而显然 \lambda, \mu, f 都是积性函数，因此对任意 n 结论成立。

$$ h(n) = \sum\limits_{d^a \mid n} f(\frac{n}{d^a}) g(\frac{n}{d^b}) $$ 证明 $h$ 是积性函数。 $\textbf{sol:}

令 \gcd(n,m) = 1，那么

h(n) h(m) = \sum\limits_{d^a \mid n} f(\frac{n}{d^a}) g(\frac{n}{d^b}) \sum\limits_{d'^a \mid m} f(\frac{m}{d'^a}) g(\frac{m}{d'^b}) = \sum\limits_{d^a \mid nm} f(\frac{nm}{d^a}) g(\frac{nm}{d^b}) = h(nm)