不完整，待后人补充

归纳与递推

无平局无运气的游戏绝对有必胜策略。

$n$ 颗糖，A，B 轮流取 $2^k$ 个，取完最后一个的获胜。

第一制胜点：0
递推：

能到制胜点的都必败；
无论怎么走都是必败点才是制胜点。

猜：

$P(3k)=1,P(3k+1)=0,P(3k+2)=0$。

基本不等式（$\forall x_i\in\mathbb{R^+}$）：$\frac{x+y}{2}\ge \sqrt{xy}$。

均值不等式（$\forall x_i\in\mathbb{R^+}$）：

\[\frac{\sum\limits_{i=1}^{n}x_i}{n}\ge \sqrt[n]{\prod\limits_{i=1}^{n}x_i} \]

证明： #第三数学归纳法

第三数学归纳法：
1. 证 $P(1)=1$；
2. 证 $\exists$ 递增数列 $\{a_n\}$，满足 $\forall 1\le i\le n,P(a_i)=1$；
3. 证若 $P(k)=1$ 则 $P(k-1)=1$。

显然 $n=2$ 成立。

若 $n=2^k$ 成立，则 $n=2^{k+1}$ 成立。
$n=2^k$，有 $\frac{\sum\limits_{i=1}^{2^k}x_i}{2^k}\ge \sqrt[2^k]{\prod\limits_{i=1}^{2^k}x_i}$。
当 $n=2^{k+1}$，有

\[\begin{aligned}\frac{\sum\limits_{i=1}^{2^{k+1}}x_i}{2^{k+1}}&\ge \frac{\sum\limits_{i=1}^{2^k}x_i+\sum\limits_{i=2^k+1}^{2^{k+1}}x_i}{2^{k+1}}\\&\ge \frac{2^k\sqrt[2^k]{\prod\limits_{i=1}^{2^k}x_i}+2^k\sqrt[2^k]{\prod\limits_{i=2^k+1}^{2^{k+1}}x_i}}{2^{k+1}}\\&=\frac{\sqrt[2^k]{\prod\limits_{i=1}^{2^k}x_i}+\sqrt[2^k]{\prod\limits_{i=2^k+1}^{2^{k+1}}x_i}}{2}\\&\ge \sqrt{\sqrt[2^k]{\prod\limits_{i=1}^{2^{k}}x_i}\cdot\sqrt[2^k]{\prod\limits_{i=2^k+1}^{2^{k+1}}x_i}}\\&=\sqrt[2^{k+1}]{\prod\limits_{i=1}^{2^{k+1}}x_i}\end{aligned} \]

若 $n=m$ 成立，则 $n=m-1$ 成立。

$n=m$，有 $\frac{\sum\limits_{i=1}^{m}x_i}{m}\ge \sqrt[m]{\prod\limits_{i=1}^{m}x_i}$。
当 $n=m-1$，有

\[\begin{aligned}\frac{\sum\limits_{i=1}^{m-1}x_i}{m-1}&=\frac{\sum\limits_{i=1}^{m}x_i+\frac{\sum\limits_{i=1}^{m-1}x_i}{m-1}}{m}\\&\ge\left(\frac{\prod\limits_{i=1}^{m-1}x_i}{m-1}\right)^{\frac{1}{m}}\left(\frac{\sum\limits_{i=1}^{m-1}x_i}{m-1}\right)^{\frac{1}{m}}\\\therefore \left(\frac{\sum\limits_{i=1}^{m-1}x_i}{m-1}\right)^{\frac{m-1}{m}}&\ge\left(\frac{\prod\limits_{i=1}^{m-1}x_i}{m-1}\right)^{\frac{1}{m}}\\\frac{\sum\limits_{i=1}^{m-1}x_i}{m-1}&\ge\left(\frac{\prod\limits_{i=1}^{m-1}x_i}{m-1}\right)^{\frac{1}{m-1}}\\&\ge\sqrt[m-1]{\prod\limits_{i=1}^{m-1}x_i}\end{aligned} \]

Q1. 砝码问题 - 可以放一边

Q2. 砝码问题 - 可以放两边

Q2.1：6 个砝码最多称出的重量数为 $\frac{3^n-1}{2}$，方案：$1,3,9,27,...$。
Q2.2：先给出 1, 2, 3, 4 g，再放 $x$ 个砝码，递推：$a_{n+1}=3 a_n+1,a_0=1+2+3+4$（不放，放左盘，放右盘）。
Q2.3：6 个砝码恰好称出 1 - 100 g

$a_1=1$，因为需要称出 99 g，即 $a_1+a_2+a_3+a_4+a_5+a_6-1$。
$a_6$ 下限 30，上限 67.
上限：$a_6\le 2(a_1+a_2+a_3+a_4+a_5)+1=2(100-a_6)+1$，$a_6\le 67$。否则无法称出 $a_1+a_2+a_3+a_4+a_5+1$。

Q3.

1, 2, 4, 8, 16 g 的砝码全部按顺序放在天平左右两侧，保证左边一直重于右边，求方案数。

1 g，$a_1=1$；
1, 2 g，$a_2=3$；[1, 2|], [2, 1|], [2|1]
1, 2, 4 g，考虑把 1, 2 替换成 1x2, 2x2，放 1 不会改变两边的大小关系，于是在第 1 步以后，左右都可放，递推式：$a_{n+1}=(2n+1)a_n$。

Q4. 天平找次品

三分分的是次品信息，不是次品
Q4.1：$n$ 个，其中 1 个轻次品，求最少称重次数。$\left \lceil \log_3 n \right \rceil$。
Q4.2：$n$ 次，最多可称几个品。$3^n$。
Q4.3：$12$ 个，其中有 1 个次品，求最少称重次数。 #Google

3-3-3-3 第一次只能确定 12 种情况，不行；
5-5-2 同理不行；
4-4-4 可以：
对于第二次，= 代表次品不在天平上，同（第一次）号说明次品同侧，异号说明次品第二次改变了位置。
构造：

证明
Step 1：
1234 = 5678
Step 2:
1 9 10 11 = 5 2 3 4
Step 3:
6 = 7 : 8
6 < 7 : 6
6 > 7 : 7

1234 > 5678
1234 < 5678

Q5. 染色问题

Q5.1：$n$ 边形，顶点染色为 A, B, C，相邻点颜色不同，求方案数。

答案为 $3\times 2^n-1 和 n 颜色相同的方案数$。可以发现，要减去的相当于把 $1$ 和 $n$ 视为一个点，即为 $n-1$ 时的答案，所以递推：$a_{n+1}=3\times 2^n-a_n,a_3=1$。

Q5.2：1, 2, 3 组成 $n$ 位数，且需满足：1 的下一位不是 2，2 的下一位是 3。求方案数。

转化题意，1 的上一位是 1 或 3，2 的上一位是 3，3 的上一位是 1 或 2 或 3.

设第 $k$ 位为 1 的有 $x_k$ 个，为 2 的有 $y_k$ 个，为 3 的有 $z_k$ 个。

则有：$x_1=y_1=z_1=1,x_{k+1}=x_k+z_k,y_{k+1}=z_k,z_{k+1}=x_k+y_k+z_k$。

Q6. 错排问题

$D_n$ 为 $n$ 元错排。

\[D_n=n!\sum_{i=0}^n (-1)^i \frac{1}{i!}\approx\frac{n!}{e} \]

\[e^k=\sum_{i=0}^{\infty} \frac{k^i}{i!} \]

这个的精度误差在四舍五入范围内，但 $n$ 很大时，同时需要 $e$ 的精度足够高。

递推。

\[D_n=(n-1)(D_{n-1}+D_{n-2}) \]

或

\[D_n=nD_{n-1}+(-1)^n \]

Q7. 间排问题

$G_n$ 为 1-n 的排列满足 $\forall 1\le i<n$，不存在 $a_i+1=a_{i+1}$ 的方案数。

容斥。

\[\begin{aligned}G_n&=n!-\binom{n-1}{1}(n-1)!+\binom{n-1}{2}(n-2)!+...\\&=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}{i}(n-i)!\end{aligned} \]

Q8. 卡特兰数

$C_n$ 为 $n$ 对括号，括号匹配（本质一样，左括号个数永远大于等于右括号个数）的序列数。
递推：

\[C_n=\sum_{i=1}^{n-1}C_iC_{n-i} \]

通项：

\[C_n=\binom{2n}{n}-\binom{2n}{n−1}=\frac{\binom{2n}{n}}{n+1} \]

$C_n$ 为 A, B 打乒乓球，从 $0:0$ 打到 $n:n$，A 从来没有落后过的方案数。

$C_n$ 为在 $n×n$ 的网格中，一开始在 $(0,0)$ 处，每次可以向上走一格或者向右走一格，在任一时刻，向右走的次数不能少于向上走的次数，合法路径数。

“在任一时刻，向右走的次数不能少于向上走的次数” 的意思即是路径不能与$y=x+1$ 有交点。对于与 $y=x+1$ 有交点的路径，把第一个交点之后的路径沿 $y=x+1$ 对称过去，可以发现每一个与 $y=x+1$ 有交点的路径都唯一对应一条从 $(0,0)$ 到 $(n-1,n+1)$ 的路径，这样的路径一共有 $\binom{2n}{n−1}$ 条，所以合法路径有 $\boxed{C_n=\binom{2n}{n}-\binom{2n}{n−1}}$ 种，即为通项公式。

$C_n$ 为一个圆周上有 $2n$ 个点，两两配对并在两点间连一条弦，要求所连的n条弦没有交点，配对数。

锁定一个点，这个点最多连接两个点，连两边，即转化为括号序列。

$C_{n-2}$ 为将 $n$ 边的凸多边形以不相交的对角线分成 $n-2$ 个三角形的方案数。

锁定一条边，这条边最多连接一个点，再考虑两边，同上。

$C_n$ 为 $\sum\limits_{i=1}^{2n} a_i(a_i\in\{-1,1\})=0,\forall 1\le k\le 2n,\sum\limits_{i=1}^k a_i\ge 0$ 的方案数。

Q9. 递推转通项

$a_{n+1}=2a_n+1,a_1=1$
设 $a_{n+1}+k=2(a_n+k)$，解得 $k=1$.
所以 $a_{n+1}+1=2(a_n+1),a_1+1=2$.
所以 $a_n+1=2\times 2^{n-1},a_n=2^n-1$.
$a_{n+1}=2a_n+3^n,a_1=1$
1. 设 $a_{n+1}+k3^{n+1}=2(a_n+k3^n)$，解得 $k=-1$.
  $\therefore a_{n+1}-3^{n+1}=2(a_n-2^n),a_1-3^1=-2$.
  $\therefore a_n-3^n=-2\times 2^{n-1}=-2^n,a_n=3^n-2^n$.
2. 当 $3^n\to 2^n$，1) 不可做.
  $\therefore \frac{a_{n+1}}{2^{n+1}}=\frac{a_n}{2^n}+\frac 12$.
  令 $b_n=\frac{a_n}{2^n},b_1=\frac{1}{2^1}=\frac 12$.
  $\therefore b_n=\frac n2,a_n=2^n\times\frac n2=2^{n-1}n$.
$a_{n+1}=2a_n+n,a_1=1$
观察到 $a_{n+1}$ 与 $a_n$ 齐次（一次），于是可以联想到一次函数，设 $a_{n+1}+k(n+1)+b=2(a_n+(kn+b))$，解得 $b=k=1$.
所以 $a_{n+1}+(n+1)+1=2(a_n+n+1),a_1+1+1=3$.
所以 $a_n+n+1=3\times 2^{n-1},a_n=3\times 2^{n-1}-n-1$.
$a_{n+1}=\frac{a_n}{1+a_n},a_1=\frac 12$
考虑把等式两边取倒数，有 $\frac{1}{a_{n+1}}=\frac{1}{a_n}+1,\frac{1}{a_1}=2$.
于是就和 0. 一样了，甚至更简单.
$a_n=\frac{1}{n+1}$.
$a_{n+2}=a_{n+1}+a_{n},a_1=a_2=1$
本质上就是 fibonacci .
考虑使用线性代数求解：
```
### 线性代数
#### 线性空间
**群**：见 Day 5
**线性空间自由度**：同方程（组）的自由度，是指递推初始值的个数.
```
我们可以发现 Fibonacci 数列的递推式后面没有常数项，线性空间自由度为 2，所以可以说明 Fibonacci 是由 2 个由等比数列构成的线性空间的乘积，设等比数列为 $\{q_n\}(\forall q_i\not= 0)$，则有 $q^{n+2}=q^{n+1}+q^n,q^2-q-1=0,q=\frac{1\pm \sqrt 5}{2}$.
因为 $a_1=a_2=1$，所以设 $x,y$ 为 $q$ 的系数，有：
\[\begin{cases}\left(\frac{1+ \sqrt 5}{2}\right)x&+\left(\frac{1- \sqrt 5}{2}\right)y&=1\\\left(\frac{1+ \sqrt 5}{2}\right)^2x&+\left(\frac{1- \sqrt 5}{2}\right)^2y&=1\end{cases} \]

解得

\[\begin{cases}x=\frac{1}{\sqrt{5}}\\y=-\frac{1}{\sqrt 5}\end{cases} \]

Q10. 数列差分(差分算子)

定义：$\Delta h_n=h_{n+1}-h_n$.
二次差分 $\Delta^2 h_n=\Delta h_{n+1}-\Delta h_n$.
与求和互为逆运算。
$\Delta^2 a_n=0$ 的数列为等差数列。
$\Delta^3 a_n=0$ 的数列为二级等差数列（平方数列）。
结论 1：若 $f(n)$ 为 $k$ 次多项式，$\Delta^{k+1}f(n)=0$.

结论 2：$\Delta$ 是线性算子。$\Delta(a_n+b_n)=\Delta a_n=\Delta b_n,\Delta(ka_n)=k\Delta a_n$.
原数列 $a_n$ 与 $\Delta^n a_0$ 一一对应。
设单位数列（基） $e_n^{(m)}=\{x|\forall 1\le i\le n[i=m]\}$，所有数列都可以用 $e$ 线性组合得到。

$n^p=C_n^p+x_1C_n^{p-1}+x_2C_n^{p-2}+...+x_nC_n^1=\sum\limits_{i=0}^pS(p,i)A_n^i$
其中系数 $S(p,i)$ 为第二类 Stirling 数。
$n^1=0A_1^0+1A_1^1\to S(1,0)=0,S(1,1)=1$,
$n^2=0A_2^0+1A_2^1+(2/2)A_2^2\to S(2,0)=0,S(2,1)=1,S(2,2)=1$,

a3:   0 1 8 27
Δa3:   1 7 19
Δ^2a3:  6 12
Δ^3a3:   6
Δ^4a3:    0

$n^3=0A_3^0+1A_3^1+(6/2)A_3^2+1(6/6)A_3^3\to S(3,0)=0,S(3,1)=1,S(3,2)=3,S(3,3)=1$
特别地，规定 $S(0,0)=1$.

\[\begin{array}{c|c|c|c|c|c|c} S(p,i) & 0 &1&2&3&4&5\\ \hline 0 & 1 \\ \hline 1 & 0&1 \\ \hline 2 & 0&1&1 \\ \hline 3 & 0&1&3&1 \\ \hline 4 & 0&1&7&6&1 \\ \hline 5 & 0&1&15&25&10&1 \\ \end{array} \]

递推式：$S(p,i)=S(p-1,i-1)+i\times S(p-1,i)(1\le i\le p-1)$.
组合意义：将 $p$ 个不同元素划分成 $i$ 个不计顺序的部分的方案数.

显然 $S(p,1)=1$.
下证：$S(p,i)=S(p-1,i-1)+i\times S(p-1,i)$.
这相当于现有 $p$ 个元素，其中有一个元素 $x$，则有两种划分：

$x$ 单独一组，则 $p-1$ 个元素分成 $i-1$ 组，$S(p-1,i-1)$.
$x$ 在某一组里，则 $p-1$ 个元素分成 $i$ 组，此时 $x$ 可以在任意一组内，$i\times S(p-1,i)$.
证毕。

从另一方面看，这相当于把元素映射到组中去，是 $p$ 元集 $\mapsto$ $i$ 元集的满射。
所以考虑容斥：

\[\begin{aligned}S(p,i)&=i^p-C_p^1(i-1)^p+C_p^2(i-2)^p-...\\&=\frac{1}{i!}\left(\sum_{k=0}^i(-1)^kC_p^k(1-k)^p\right)\end{aligned} \]

Bell 数：$B_p$ 表示把 p 个元素分为若干个部分的方案数。

\[B_p=\sum_{i=0}^pS(p,i) \]

$B_0=1,B_1=1,B_2=2,B_3=5$.
![[Pasted image 20230809102747.png]]
即 $$B_p=\sum_{i=0}^{p-1}C_{p-1}iB_{p-i-1}$$
第一类 Stirling 数：表示满足 $A_n^p=\sum(-1)^{p-i}s(p,i)n^i$ 的 $s(p,i)$，即 $A_n^p$ $i$ 次项系数的绝对值.

递推式：$s(p,i)=s(p-1,i-1)+(p-1)s(p-1,i)$.

\[\begin{array}{c|c|c|c|c|c|c} s(p,i)\\ p\ i& 0 &1&2&3&4&5&6\\ \hline 0 & 0&1 \\ \hline 1 & 0&1&1 \\ \hline 2 & 0&2&3&1 \\ \hline 3 & 0&6&11&6&1 \\ \hline 4 & 0&24&50&35&10&1 \\ \hline 5 & 0&120&274&225&85&15&1 \\ \end{array} \]

组合意义：将 $p$ 个元素划分成 $i$ 个圆排列的方案数。
考虑 $n+1$ 个元素中有一个元素 $x$，则有两种划分：