Math Exercise

· · 算法·理论

组合数学

--- $2.$ 给定奇数 $n$，求非负整数对 $(a,b,c)$ 的个数，使得 $a+b+c=n, \max(a,b,c) \le \frac{n}{2}$。 --- $3.$ 根据加法原理，证明 $\sum\limits_{i=0}^n 2^i = 2^{n+1} - 1$，并计算 $\sum\limits_{i=1}^n (n-i) 2^i$。 --- $4.$ 通过两种计数方法证明 $\sum\limits_{i=1}^n i(n-i) = \sum\limits_{i=1}^n \binom{i}{2} = \binom{n+1}{3}$。 --- $5.$ 求有多少个 $1 \sim n$ 的排列 $p$ 有 $\forall 2 \le i \le n, \exists 1 \le j < i, |p_i - p_j| = 1$。 --- $6.$ 令 $f(n,k)$ 表示在 $n$ 个数中选 $k$ 个两两不相邻的数的方案数，证明 $f(n,k) = \binom{n-k+1}{k}$ 且 $\sum\limits_{k=0}^n f(n,k) = F_{n+2}$，其中 $F_n$ 表示斐波那契数列的第 $n$ 项。 --- $7.$ 证明 $\sum\limits_{d \mid n} \varphi(d) = n$。 --- $8.$ 化简 $\sum\limits_{i=1}^n i^2$ 和 $\sum\limits_{i=1}^n i^3$。 --- $9.$ 证明 $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$，并通过两种计数方式证明 $\sum\limits_{k=0}^m \binom{n}{k} \binom{n-k}{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 --- $12.$ 统计有多少个 $01$ 序列满足有 $n$ 个 $1$ 和 $m$ 个 $0$，且有 $k$ 个连续的 $1$ 的段。 --- $13.$ 通过网格路径计数证明 $\sum\limits_{k} \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}$ 和 $\sum\limits_{k} \binom{r}{m+k} \binom{s}{n+k} = \binom{r+s}{r-m+n}$。 --- $14.$ 设 $F(n,m)$ 为每次只能向右、上、右上走一格的情况下，从 $(0,0)$ 走到 $(n,m)$ 的方案数，证明 $F(n,m) = \sum\limits_{k} \binom{m}{k} \binom{n+k}{m}$。 --- $15.$ 证明 $\sum\limits_{k} \binom{m-r+s}{k} \binom{n+r-s}{n-k} \binom{r+k}{m+n} = \binom{r}{m} \binom{s}{n}$。 --- $16.$ 证明 $\sum\limits_{k} {n+1 \brace k+1} x^{\underline{k}} = (x+1)^n$，并借此证明 ${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 {m+i \brace i} = {m+n+1 \brace n} --- $19.$ 用第二类斯特林数表示 $x^{\overline{k}}$ 和 $x^k$ 间的联系。 --- $20.$ 证明 ${n \brace k} = \sum\limits_{\sum\limits_{i=1}^k a_i = n, \forall 1 \le i \le n, a_i \in N_+} \prod\limits_{i=1}^k i^{a_i - 1}$。 --- $21.$ 证明 $\binom{k+r}{k} {n \brace k+r} = \sum\limits_{i=k}^{n-r} \binom{n}{i} {i \brace k} {n-i \brace r}$。 --- $22.$ 求有多少值域为 $[1,k]$ 的整数序列 $a$ 满足对于每个 $1 \le i < k$，$i$ 第一次出现的位置在 $i+1$ 前。 --- $23.$ 证明将 $1 \sim n$ 分类，使得没有连续的数在同一集合内，有 $Bell(n-1)$ 种方案。 --- $24.$ 证明 ${n+1 \brack k+1} = \sum\limits_{i=0}^n \binom{i}{k} {n \brack i}$。 --- $25.$ 设 $f(n)$ 表示有多少个 $1 \sim n$ 的排列 $P$ 满足 $P^2 = id$，证明 $f(n+1) = f(n) + n f(n-1)$。 --- $26.$ 令 $f(n,r)$ 表示有多少个 $1 \sim n$ 的排列 $P$ 满足 $P$ 对应的图不存在大小超过 $r$ 的环，证明 $f(n+1,r) = \sum\limits_{k=n-r+1}^n n^{\underline{n-k}} f(k,r)$。 --- $27.$ 令 $f(n,k)$ 表示有多少个 $1 \sim n$ 的排列 $P$ 满足 $P$ 恰好有 $k$ 个逆序对，证明当 $k < n$ 时有 $f(n,0) = 1$，$f(n,k) = f(n,\binom{n}{2} - k)$，$f(n,k) = f(n-1,k) + f(n,k-1)$，并判断 $k=n$ 时是否任然满足。同时证明当 $n \ge 2$ 时有 $\sum\limits_{k \ge 0} (-1)^k f(n,k) = 0$。 --- $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!$。 --- $29.$ 证明 $$ \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} $$ --- $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$。 --- $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 f(n,k) = \frac{(n+1)!}{2}$。 --- $32.$ 求有多少个 $1 \sim n$ 的排列 $P$ 使得 $1 \sim k$ 在同一个环里。 --- $33.$ 等概率选择一个排列，求期望有多少个环。 --- $34.$ 证明错排 $D$ 的通项公式为 $D_n = (n-1)(D_{n-1} + D_{n-2})$，并借此证明 $D_n = n D_{n-1} + (-1)^n$。 --- **定义：令 $p(n)$ 表示将 $n$ 无序拆分成若干个正整数的方案数，注意 $1,2$ 和 $2,1$ 算一种拆分。$p(n,k)$ 表示将 $n$ 拆分成 $k$ 个正整数的方案数，$p(n,k,m)$ 表示将 $n$ 拆分成 $k$ 个不超过 $m$ 的正整数的方案数，$p_d(n)$ 则要求拆分成若干个不同的正整数。** --- $35.$ 证明当且仅当 $n \ge 2k$ 时，有 $p(n,n-k) = p(k)$。 --- $36.$ 证明 $p_d(n,k) = p(n - \binom{k}{2}, k)$。 --- $37.$ 证明当 $n \ge 5, 2 \le k \le \left\lfloor \frac{n}{2} \right\rfloor$ 时，有 $p_d(n,k) = p_d(n-k,k) + p_d(n-k,k-1)$，且 $p_d(n,1) = 1$，当 $n < \binom{k+1}{2}$，有 $p_d(n,k) = 0$，$p_d(\binom{k+1}{2}, k) = 1$。 --- $38.$ 证明将 $n$ 无序拆分成若干个 $\ge 2$ 的正整数的方案数位 $p(n) - p(n-1)$。 --- $39.$ 求 $x_1 + x_2 + \dots + x_k \le n$ 的正整数解的个数和非负整数解的个数。 --- $40.$ 证明当 $n \ge 2$ 时，在所有将 $n$ 无序拆分成若干个 $2$ 的正整数幂次的方案中，恰好有一半是拆分成偶数个数 --- $41.$ 令 $\lambda$ 为 $n$ 的一种无序拆分，设 $f_m(\lambda)$ 为在 $\lambda$ 中 $m$ 出现的次数，$g_m(\lambda)$ 为在 $\lambda$ 中有多少个数出现了超过 $m$ 次，证明 $\sum\limits_{\lambda} f_m{\lambda} = \sum\limits_{\lambda} g_m(\lambda)$，并求出 $\sum\limits_{\lambda} f_1(\lambda)$。 --- $42.$ 令 $f(m)$ 表示有多少个序列对 $(\lambda, \mu)$，其中 $|\lambda| = |\mu|$，$\lambda$ 为正整数序列，$\mu$ 为非负整数序列，且两个序列都递减。证明 $f(m) = p(m)$。 --- # 生成函数 $1.$ 证明 $$ \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) $$ --- $2.$ 找到生成函数 $F$ 使得 $$ f_n = \sum\limits_{k} \binom{m}{k} \binom{m}{n-2k} $$ --- $3.$ 证明 $$ \sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n $$ --- $4.$ 找出以下函数的封闭型式： $$ \sum\limits_{n \ge 0} \binom{2n+1}{n} x^n $$ $$ \sum\limits_{n \ge 0} \binom{n}{n/2} x^n $$ --- $5.$ 令 $F = \sqrt{\frac{1+x}{1-x}}$，找到 $f_n$ 的通项公式。 --- $6.$ 根据 $$ F(x) = \frac{G(x)}{(1-x)^m} \Leftrightarrow G(x) = F(x) (1-x)^m $$ 找出一种反演。 --- $7.$ 令 $F_n = \sum\limits_{k \ge 0} {n \brack k} x^k$，证明 $$ F_n(x+y) = \sum\limits_{k \ge 0} \binom{n}{k} F_k(x) F_{n-k}(y) $$ --- $8.$ 令 $F_k = \sum\limits_{n \ge 0} {n \brack k} \frac{x^n}{n!}$，证明 $F'_k = \frac{F_{k-1}}{1-x}$，并计算 $F_1$ 和 $F_2$，并用调和级数表示 ${n \brack 2}$ 和 ${n \brack 3}$。 --- $9.$ 证明 $$ \frac{1}{1-x} = \prod\limits_{i \ge 0} 1 + x^{2^i} $$ --- $10.$ 令 $F = \prod\limits_{i \ge 1} 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}$。 --- $11.$ 令 $f(n)$ 表示将 $1 \sim n$ 划分成若干个排列的方案数，证明 $$ f(n) = \sum\limits_{k=1}^n \binom{n-1}{k-1} \frac{n!}{k!} $$ 并借此证明 $$ \prod\limits_{i \ge 1} e^{x^i} = e^{\frac{x}{1-x}} $$ --- $12.$ 计算 $$ \sum\limits_{k \ge 1} \frac{x^k}{1 - x^k} $$ --- $13.$ 计算 $$ \prod\limits_{n \ge 1} (1 - x^n)^{- \frac{\mu(n)}{n}} $$ --- $14.$ 令 $F = \prod\limits_{k \ge 1} 1 + x^k$，问 $f_n$ 的组合意义。 --- $15.$ 令 $f_n$ 表示将 $n$ 无序拆分成若干个 $2$ 的非负整数幂次的方案数，而 $g_n = \sum\limits_{k=0}^n f_k$，计算 $F$ 和 $G$，并推导 $f_n$ 和 $g_n$。 --- $16.$ 证明一个下三角矩阵 $A$ 有逆当且仅当 $A$ 的主对角线都非 $0$。 --- $17.$ 令 $P = \left\{ \binom{n}{k} \right\}$，证明 $$ \forall m \in \mathbb{Z}, P^m_{n,k} = \binom{n}{k} m^{n-k} $$ --- $18.$ 证明 $$ \sum\limits_{k=0}^n (-1)^k \binom{n}{k} (x-k)^n = n! $$ --- $19.$ 找到 $L$ 使得 $$ x^{\overline{n}} = \sum\limits_{k=0}^n L_{n,k} x^{\underline{k}} $$ --- $20.$ 找出根据 $L$ 的反演公式。 --- $21.$ 证明 $$ L_{n+1,k+1} = \sum\limits_{i=0}^n L_{i,k} (n+k+1)^{\underline{n-i}} $$ --- $22.$ 证明 $L_{n+1,k+1}$ 为将 $1 \sim n$ 划分成 $k$ 个排列的方案数。 --- $23.$ 证明 $$ (x+1)^{\overline{n}} = \sum\limits_{k=0}^n L_{n+1,k+1} (x-1)^{\underline{k}} $$ --- $24.$ 证明 $$ \sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}^{-1} = \frac{m+1}{m+1-n} $$ 并通过二项式反演找到另一个公式。 --- $25.$ 证明 $$ 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} $$ --- $26.$ 给定 $f_n = \sum\limits_{k=0}^n \binom{m+k}{k} g_{n-k}$，用 $f$ 来表示 $g_n$。 --- $27.$ 随机抛 $n$ 次硬币，令 $X$ 为正面向上的次数，计算 $P_X, \mathbb{E} x, \operatorname{Var} X$。 --- $28.$ 令 $X$ 和 $Y$ 为相互独立的随机变量，证明 $P_{X+Y} = P_X \cdot P_Y$。 --- $29.$ 随机抛一枚硬币直到正面向上，令 $X$ 为抛的次数，求 $P_X, \mathbb{E} X, \operatorname{Var} X$。 --- $30.$ 对一个随机变量 $X$，令 $\mu_k = \mathbb{E} X^k$，证明 $$ 1 + \sum\limits_{k \ge 1} \mu_k \frac{x^k}{k!} = P_X(e^x) $$ --- $31.$ 随机抛一个骰子直到每面都出现过，令 $X$ 为抛的次数，求 $\mathbb{E} X$。 --- $32.$ 随机抛一枚硬币直到连续两次是正面，令 $X$ 为抛的次数，求 $P_X, \mathbb{E} X, \operatorname{Var} X$。 --- $33.$ 在一个圆上有 $2n$ 个点，随机两两连 $n$ 条线，令 $X$ 为交点的个数，求 $\mathbb{E} X, \operatorname{Var} X$。 --- $34.$ 在一个五边形中，有两个点，一开始他们在相邻的两个顶点上，每次他们都会同时等概率的移动到相邻的顶点，直到他们来到相同的点，令 $X$ 为移动的次数，求 $\mathbb{E} X, \operatorname{Var} X$。如果这两个点一开始隔着一个顶点呢？ --- # 数论函数 **若无特殊定义，默认所有变量都为正整数，$p$ 为质数，$k$ 为 $n$ 的不同质因数的个数，$p_i$ 为 $n$ 的第 $i$ 大的质因数，$n = \prod\limits_{i=1}^k p_i^{c_i}$。** --- $1.$ 找到所有的 $n$ 使得 $(1)$ $2\varphi(n) = n (2)$ $\varphi(n) = \varphi(2n) (3)$ $\varphi(n) = 12 $$ \frac{n}{\varphi(n)} = \sum\limits_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} $$ --- $3.$ 设 $v(n) = k, f = \mu * v$，证明 $$ f(n) = 0 \text{ or } f(n) = 1 $$ --- $4.$ 证明对任意正整数 $k$，有 $$ \sum\limits_{d^k \mid n} \mu(d) = [\exists m>1, m^k \mid n] $$ --- $5.$ 证明 $$ \forall p, n > 1, \sum\limits_{d \mid n} \mu(d) \mu(\gcd(p,d)) = 2 [\exists c \ge 1, n = p^c] $$ --- $6.$ 对实数 $x$，定义 $$ \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} $$ --- $7.$ 证明 $$ \prod\limits_{d \mid n} d = n^{\frac{d(n)}{2}} $$ --- $8.$ 证明 $d(n)$ 为奇数当且仅当 $n$ 为完全平方数。 --- $9.$ 证明 $$ \sum\limits_{d \mid n} d(d)^3 = \left( \sum\limits_{d \mid n} d(d) \right)^2 $$ --- $10.$ 对非负整数 $k$，设 $$ \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 $$ --- $11.$ 对 $1 \le k \le 3$，找到 $\varphi_k(n)$ 的通项公式。 --- $12.$ 设 $$ 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) $$ --- $13.$ 证明 $$ \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})} $$ --- $14.$ 证明 $$ D(n) = \sum\limits_{d \mid n} \varphi(d) d(\frac{n}{d}) $$ 并对所有正整数 $k$ 找到 $\sigma_k$ 的递推公式 --- $15.$ 对积性函数 $f$，设 $$ F(n) = \prod\limits_{d \mid n} f(d) $$ 证明 $F$ 也是积性函数。 --- $16.$ 对积性函数 $f$，证明 $f$ 是完全积性函数当且仅当 $$ \forall p,c \ge 2, f^{-1}(p^c) = 0 $$ --- $17.$ 对完全积性函数 $f$ 和数论函数 $g$ 和 $h$，证明 $$ f \cdot (g * h) = (f \cdot g) * (f \cdot h) $$ --- $18.$ 对积性函数 $f$ 满足 $$ (f \mu) * (f \mu^{-1}) = \varepsilon $$ 证明 $f$ 是完全积性函数。 --- $19.$ 对完全积性函数 $f$ 和数论函数 $g$，证明 $$ (f \cdot g)^{-1} = f \cdot g^{-1} $$ --- $20.$ 对积性函数 $f$ 满足 $$ (f \cdot \mu)^{-1} = f \cdot 1 $$ 证明 $f$ 是完全积性函数。 --- $21.$ 对积性函数 $g$ 和任意数论函数 $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) $$ --- $22.$ 对积性函数 $f$ 和完全积性函数 $g$，若 $$ 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}) $$ --- $23.$ 证明 $$ \lambda(n) = \sum\limits_{d^2 \mid n} \mu(\frac{n}{d^2}) $$ --- $24.$ 对积性函数 $f$ 和 $g$，以及正整数 $a$ 和 $b$ 满足 $a \ge b$，设 $h$ 满足 $$ h(n) = \sum\limits_{d^a \mid n} f(\frac{n}{d^a}) g(\frac{n}{d^b}) $$ 证明 $h$ 是积性函数。