分拆数
LYH_cpp
·
·
个人记录
分拆数
分拆数：从入门到放弃
本文用空心方格 \square 表示“证毕”
\textbf{Part 1:} 定义
分拆：将 n\in \mathbb{N} 写成单调不升的正整数的和。
n=r_1+r_2+r_3+\cdots+r_k\quad r_1\ge r_2\ge r_3\ge\cdots\ge r_k\ge 1
“单调不升”表示分拆是无序的。
分拆数：n\in \mathbb{N} 的分拆方案数，记作 p_n。A000041
| p_0 |
p_1 |
p_2 |
p_3 |
p_4 |
p_5 |
p_6 |
p_7 |
p_8 |
| 1 |
1 |
2 |
3 |
5 |
7 |
11 |
15 |
22 |
\textbf{Part 2:} Ferrers 图
一个 Ferrers 图是一个分拆的几何表示，是推导分拆数强有力的工具。
其中第 $i$ 行有 $r_i$ 个点。
例如 $9=4+2+2+1$ 的 Ferrers 图如下：
通过在 Ferrers 图上操作，我们能建立起分拆之间的对应关系
从而轻易推出分拆数的很多性质。
本文后面的推导中将用到 Ferrers 图，这里先介绍最重要的一个关系：**共轭**。
我们将一个分拆 $\lambda$ 的 Ferrers 图画出来，
然后按**从左上到右下的对角线翻转**，得到一张新的 Ferrers 图。
这个 Ferrers 图可以表示为一个新的分拆 $\lambda^*$。
我们称 n 的分拆 $\lambda$ 的**共轭分拆**是分拆 $\lambda^*$。
显然 $\lambda=(\lambda^*)^*$。
且 $\forall\lambda_1\neq\lambda_2$，都有 $\lambda^*_1\neq\lambda^*_2$。
$\therefore \lambda$ 和 $\lambda^*$ 是一一对应的。
例如 $9=4+2+2+1$ 的共轭分拆为 $9=4+3+1+1$。
---
## $\textbf{Part 3:}$ 各种限制的分拆数
### 1. $k$ 部分拆数
$k$ 部分拆数：$n\in \mathbb{N}$ 恰好分拆成 $k$ 个正整数的方案数，记作 $p(n,k)$。
显然 $p_n=\sum\limits_{k=0}^{n}p(n,k)$。
我们考虑如何递推。
> 定理 3.1.1：
> $$p(n,k)=\begin{cases}1&n=k=0\\p(n-1,k-1)+p(n-k,k)&1\le k\le n\\0&\text{otherwise.}\end{cases} \tag{3.1.1}$$
**证：** 考虑 $p(n,k)(1\le k\le n)$ 的一个分拆 $\lambda$。
$n=r_1+r_2+r_3+\cdots+r_k,\quad r_1\ge r_2\ge r_3\ge\cdots\ge r_k\ge 1$。
如果我们将每个 $r_i$ 减去 $1$，那么得到
$n-k=(r_1-1)+(r_2-1)+(r_3-1)+\cdots+(r_k-1)$。
如果此时 $r_i-1$ 中有 $j$ 个为 $0$，那么该方案会被统计在 $p(n-k,k-j)$ 中。
于是得：$p(n,k)=\sum\limits_{j=0}^{k}p(n-k,j)$。
$$\begin{aligned}p(n,k)-p(n-1,k-1)&=\sum\limits_{j=0}^{k}p(n-k,j)-\sum\limits_{j=0}^{k-1}p((n-1)-(k-1),j)\\&=\sum\limits_{j=0}^{k}p(n-k,j)-\sum\limits_{j=0}^{k-1}p(n-k,j)\\&=p(n-k,k)\end{aligned}$$
$$\therefore p(n,k)=p(n-1,k-1)+p(n-k,k)\quad \square$$
至此，我们可以用 $\mathcal{O}(n^2)$ 的时间复杂度 求出 $[1,n]$ 的 分拆数 和 $k$ 部分拆数 了。
---
### 2. 互异分拆数
互异分拆：将 $n\in \mathbb{N}$ 写成**严格单调递降**的正整数的和。
$n=r_1+r_2+r_3+\cdots+r_k\quad r_1> r_2> r_3>\cdots> r_k> 0$。
后面的定义与分拆类似。
$pd_n$：互异分拆数。[A000009](https://oeis.org/A000009)
$pd(n,k)$：$k$ 部互异分拆数。
| $pd_0$ | $pd_1$ | $pd_2$ | $pd_3$ | $pd_4$ | $pd_5$ | $pd_6$ | $pd_7$ | $pd_8$ |
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
| $1$ | $1$ | $1$ | $2$ | $2$ | $3$ | $4$ | $5$ | $6$ |
> 定理 3.2.1
> $$pd(n,k)=\begin{cases}1&n=k=0\\pd(n-k,k-1)+pd(n-k,k)& 1\le k<\sqrt{2n}\\0&\text{otherwise.}\end{cases} \tag{3.2.1}$$
**证：** 与 定理 3.1.1 的证明同理。
不过因为 $r_i$ 互不相同，所以 $j$ 至多为 $1$。
所以直接得到 $pd(n,k)=pd(n-k,k-1)+pd(n-k,k)$。
注意到 $2$ 式的限制：$1\le k<\sqrt{2n}
我们尝试将 n 拆出尽可能多的数，显然为 1,2,3,\dots,k。
此时 n=\sum\limits_{i=1}^{k}i=\dfrac{k(k+1)}{2}>\dfrac{k^2}{2}
所以对于 $n\in \mathbb{N}_+$，$pd(n,k)$ 非 $0$ 的 $k$ 不到 $\sqrt{2n}$ 个。
我们可以用 $\mathcal{O}(n\sqrt{n})$ 的时间复杂度 求出 $[1,n]$ 的 互异分拆数 和 $k$ 部互异分拆数 了。
---
### 3. 最大部分为 $m$ 的分拆数
定义 $p^{max}(n,m)$ 为 最大部分为 $m$ 的分拆的方案数
类似的，定义 $pd^{max}(n,m)$ 为 最大部分为 $m$ 的互异分拆的方案数
> 定理 3.3.1：
> $$p^{max}(n,m)=p(n,m)$$
> $$pd^{max}(n,m)=pd(n,m)\tag{3.3.1}$$
**证：** 考虑 $p^{max}(n,k)$ 的一个分拆 $\lambda$ 的 Ferrers 图，显然它有 $k$ 列。
我们发现其共轭分拆 $\lambda^*$ 有 $k$ 行，正好被 $p(n,k)$ 统计一次。
因为 $\lambda$ 和 $\lambda^*$ 一一对应，所以 $p^{max}(n,m)=p(n,m)$。
$pd$ 同理 $\ \square$。
这是利用 Ferrers 图证明分拆数的模板，**通过建立一一对应的关系来证明分拆数的相等关系**
---
### 4. (互异)奇/偶分拆数
奇分拆数：$po_n$ 表示将 $n\in \mathbb{N}$ 拆成**每个部分为奇数**的分拆的方案数。[A000009](https://oeis.org/A000009)
偶分拆数：$pe_n$ 表示将 $n\in \mathbb{N}$ 拆成**每个部分为偶数**的分拆的方案数。
互异奇分拆数：$pdo_n$ 表示将 $n\in \mathbb{N}$ 拆成**每个部分为奇数**的互异分拆的方案数。[A000700](https://oeis.org/A000700)
互异偶分拆数：$pde_n$ 表示将 $n\in \mathbb{N}$ 拆成**每个部分为偶数**的互异分拆的方案数。
---
对于（互异）偶拆分数，我们显然有:
$$pe_n=\begin{cases}p_{\frac{n}{2}}& n\equiv 0\pmod{2}\\0& \text{else}\end{cases}$$
$$pde_n=\begin{cases}pd_{\frac{n}{2}}& n\equiv 0\pmod{2}\\0& \text{else}\end{cases}$$
所以（互异）偶拆分数没什么用，这里只是为了定义的对称。
> 定理 3.4.1：
> $$po_n=pd_n\tag{3.4.1}$$
**证：** 尝试构造一一对应的关系。
我们考虑一个互异分拆，如果它已经是奇分拆那我们不考虑
反之一定 $\exists i,r_i=2k$。
那么我们将 $r_i$ 平分为两个 $k$。
经过若干次操作后一定不存在 $r_i$ 是偶数。
这样我们就将一个互异分拆**单射**到一个奇分拆。
> 这里满足单射，是因为一个互异分拆至少操作一次后就不满足“互异”的条件了。
>
> 换句话说，**不存在**两个不同的互异分拆经过若干次操作变成同一个奇分拆。
>
> 在其它构造证明中我们也要注意这点
注意到操作可逆，于是可以将任意一个奇分拆单射到一个互异分拆。
这样我们就建立了一一对应的关系。
于是 $po_n=pd_n\quad \square$。
---
### 5. (互异)奇/偶**部**拆分数
奇部分拆数：$p^o_n$ 表示将 $n\in \mathbb{N}$ 拆成**奇数个部分**的分拆的方案数。
偶部分拆数：$p^e_n$ 表示将 $n\in \mathbb{N}$ 拆成**偶数个部分**的分拆的方案数。
类似的，还有
互异奇部分拆数：$pd^o_n$ 表示将 $n\in \mathbb{N}$ 拆成**奇数个部分**的互异分拆的方案数。
互异偶部分拆数：$pd^e_n$ 表示将 $n\in \mathbb{N}$ 拆成**偶数个部分**的互异分拆的方案数。
显然有
$$p^o_n+p^e_n=p_n$$
$$pd^o_n+pd^e_n=pd_n$$
注意 奇/偶分拆数（$po/pe$）和 奇/偶部分拆数（$p^o/p^e$）是两个完全不同的概念。
---
### 6. 自共轭分拆数
自共轭分拆：共轭分拆与本身相同的分拆。
自共轭分拆数：$ps_n$ 表示 表示将 $n\in \mathbb{N}$ 的自共轭分拆的方案数。[A000700](https://oeis.org/A000700)
> 定理 3.6.1：
> $$pdo_n=ps_n\tag{3.6.1}$$
**证：** 还是尝试构造一一对应的关系。
考虑一个自共轭分拆。
我们将这个分拆从左上到右下分层。
如下图所示：
显然每一“块”有奇数个点，且外层的块大于内层的块。
于是我们将其重新按每一块拆分开，如下图：
这样我们就得到了一个互异奇分拆。
和前面的证明类似，因为操作可逆，所以我们能建立一一对应的关系，从而证明 $pdo_n=ps_n\quad \square$。
---
## $\textbf{Part 4:}$ 生成函数
### 1. 分拆数
$\textbf{Part 3}$ 的推导比较纯数学。
这里换个角度思考，分拆数其实是个完全背包板子。
```cpp
F[0]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
F[j]+=F[j-i];
```
时间复杂度 $\mathcal{O}(n^2)$。
> 定理 4.1.1：分拆数 $p$ 的生成函数：
> $$F_p(x)=\prod\limits_{i=1}^{+\infty}\dfrac{1}{1-x^i} \tag{4.1.1}$$
**证：**
背包可以看作 $n$ 个多项式相乘，`F[i]` 表示 $x^i$ 的系数。
又 $\because \sum\limits_{i=0}^{+\infty}x^k=1+x^k+x^{2k}+x^{3k}+\cdots=\dfrac{1}{1-x^k}
于是我们能据此写出分拆数的生成函数：
\begin{aligned}F_p(x)&=\sum\limits_{i=0}^{+\infty}p_ix^i\\&=1(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)\cdots\\&=\prod\limits_{i=1}^{+\infty}\frac{1}{1-x^i}\quad \square\end{aligned}
其实不用背包，这个式子也很好理解。
如果实在搞不懂，出门左转搜“生成函数”。
ps: 背包求 k 部分拆数 是 \mathcal{O}(n^3) 的，所以 定理3.1.1 还是要记的。
2. 互异分拆数
与分拆数类似，互异分拆数是 0/1背包。
定理 4.2.1：互异分拆数 pd 的生成函数：
F_{pd}(x)=\prod\limits_{i=1}^{+\infty}(1+x^i) \tag{4.2.1}
证： 类似 定理4.1.1 可得：
\begin{aligned}F_{pd}(x)&=\sum\limits_{i=0}^{+\infty}pd_ix^i\\&=1(1+x)(1+x^2)(1+x^3)\cdots\\&=\prod\limits_{i=1}^{+\infty}(1+x^i)\quad \square\end{aligned}
3. 奇分拆数
定理 4.3.1：奇分拆数 po 的生成函数：
F_{po}(x)=\prod\limits_{i=1}^{+\infty}\frac{1}{1-x^{2i-1}}=F_{pd}(x)\tag{4.3.1}
证：
\begin{aligned}F_{po}(x)&=1(1+x+x^2+x^3+\cdots)(1+x^3+x^6+\cdots)\cdots\\&=\prod\limits_{i=1}^{+\infty}\frac{1}{1-x^{2i-1}}\\&=\frac{1}{(1-x)(1-x^3)(1-x^5)\cdots}\\&=\frac{(1-x^2)(1-x^4)(1-x^6)\cdots}{(1-x)(1-x^1)(1-x^2)(1-x^3)\cdots}\\&=\frac{\prod\limits_{i=1}^{+\infty}(1-x^{2i})}{\prod\limits_{i=1}^{+\infty}(1-x^i)}\\&=\frac{\prod\limits_{i=1}^{+\infty}(1-x^{i})(1+x^i)}{\prod\limits_{i=1}^{+\infty}(1-x^i)}\\&=\prod\limits_{i=1}^{+\infty}(1+x^i)\quad \square\end{aligned}
\textbf{Part 5:} 优化
1.五边形数定理
五边形数（A000326）就是指下面这种数（图来自 StudyingFather）。
运用小学知识可知：
\begin{aligned}P_5(n)&=P_5(n-1)+3n-2\\&=\sum\limits_{i=1}^{n}(3i-2)\\&=3\frac{n(n+1)}{2}-2n\\&=\frac{3n^2+3n-4n}{2}\\&=\frac{n(3n-1)}{2}\end{aligned}
顺便说一嘴，\dfrac{n(n+1)}{2} 就是三角形数的通项公式，n^2 就是四边形数的通项公式（
广义五边形数（A001318）就是五边形数的公式扩展到 \mathbb{Z}：
| x |
0 |
1 |
-1 |
2 |
-2 |
3 |
-3 |
4 |
-4 |
| exP_5(x) |
0 |
1 |
2 |
5 |
7 |
12 |
15 |
22 |
26 |
为了公式简洁，后文的 P_5(x) 都表示广义五边形数（即定义域为 \mathbb{Z}）。
这里不深入探讨五边形数性质，仅使用其通项公式和上面这个数列。
定理 5.1.1：
pd^e_n=pd^o_n+\Delta_n\tag{5.1.1}
其中 \Delta_n 是误差项，如果 n=P_5(i) 时（即 n 是广义五边形数）值为 (-1)^i，否则为 0。
证： 注意到 \Delta_n 非常小，我们还是尝试构造一一对应。
定理 5.1.2（五边形数定理）：
\begin{aligned}\phi(x)&=\prod_{i=1}^{+\infty}(1-x^i)\\&=\sum\limits_{i=-\infty}^{+\infty}(-1)^{i}x^{P_{5}(i)}\end{aligned}\tag{5.1.2}
其中 \phi(x) 是欧拉函数（不是常见的互质的那个 \varphi(x)），该定理由欧拉首先完成推导。
证： 考虑第一行柿子的组合意义。
将其展开：(1-x^1)(1-x^2)(1-x^3)\cdots
每个括号中，要么选 1（相当于没选），要么选 -x^i。
(-x^{r_1})(-x^{r_2})(-x^{r_3})\cdots(-x^{r_k})=(-1)^{k}x^{n}\quad n=\sum\limits_{i=1}^{k}r_i\quad r_1>r_2>r_3>\cdots>r_k>0
相当于为 x^n 贡献了一个 (-1)^k 的系数。
考虑 n 的互异分拆数，x^n 的系数为 (pd^e_n-pd^o_n)=\Delta_n（定理 5.1.1）。
所以 \phi(x)=\sum\limits_{i=0}^{+\infty}\Delta_{n}x^n=\sum\limits_{i=-\infty}^{+\infty}(-1)^{i}x^{P_{5}(i)}\quad \square。
定理 5.1.3（分拆数的递归式）：
\begin{aligned}p_n&=\sum\limits_{i>0 \And n\ge P_5(-i)}(-1)^{i+1}(p_{n-P_5(i)}+p_{n-P_5(-i)})\\&=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+p_{n-12}+p_{n-15}-\cdots\end{aligned}\tag{5.1.3}
证： 回顾分拆数的生成函数：F_p(x)=\prod\limits_{i=1}^{+\infty}\dfrac{1}{1-x^i}=\dfrac{1}{\phi(x)}
将其乘上一个 \phi(x) 得：
\begin{aligned}
F_p(x)\phi(x)&=\frac{1}{\phi(x)}\phi(x)\\
&=(\sum\limits_{i=0}^{+\infty}p_ix^i)(\sum\limits_{i=-\infty}^{+\infty}(-1)^{i}x^{P_{5}(i)})\\
&=(p_0+p_1x^1+p_2x^2+p_3x^3+\cdots)(1-x^1-x^2+x^5+x^7-x^{12}-x^{15}+\cdots)\\
&=1\\
&=1+0x+0x^2+0x^3+\cdots
\end{aligned}
考虑 x^n 的系数是怎么变成 0 的。
所以 $x^n$ 的系数为 $p_n-p_{n-1}-p_{n-2}+p_{n-5}+p_{n-7}-p_{n-12}-p_{n-15}+\cdots=0$。
移项得 $p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+p_{n-12}+p_{n-15}-\cdots\quad \square$。
因为 $P_5(x)=\dfrac{x(3x-1)}{2}$ 是个二次函数。
所以 $n$ 以内的广义五边形数只有大约 $3\sqrt{n}$ 个。
所以我们可以用 $\mathcal{O}(n\sqrt{n})$ 的时间复杂度 求出 $[1,n]$ 的 分拆数。
```cpp
constexpr int Mod=998244353;
static int p[100010];
int n;
read(n);
p[0]=1;
for(int i=1;i<=n;i++){
int sign=1;
for(int j=1,k;(k=j*(3*j-1)>>1)<=i;j<0?(j=-j+1,sign=-sign):j=-j){
p[i]+=p[i-k]*sign;
if(p[i]>=Mod)p[i]-=Mod;
else if(p[i]<0)p[i]+=Mod;
}
}
```
---
### 2.根号分治
---
### 3.多重背包计数
---
## $\textbf{Part 6:}$ 练习
[P6189 [NOI Online #1 入门组] 跑步](https://www.luogu.com.cn/problem/P6189)
[[ABC221H] Count Multiset](https://www.luogu.com.cn/problem/AT_abc221_h)
[P5824 十二重计数法](https://www.luogu.com.cn/problem/P5824)
[P4128 [SHOI2006] 有色图](https://www.luogu.com.cn/problem/P4128)
## $\textbf{Part 7:}$ 参考
[分拆数 - OI Wiki](https://oi-wiki.org/math/combinatorics/partition/)
《组合数学(原书第五版)》- [美] Richard A. Brualdi
[多项式计数杂谈 - command_block 的博客 - 洛谷博客](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan)
[分拆数的四种求法 - 木xx木大 的博客 - 洛谷博客](https://www.luogu.com.cn/blog/flyingfan/fen-chai-shuo-di-si-zhong-qiu-fa)
[整数分拆中的一个出人意料的结论 | Matrix67: The Aha Moments](http://www.matrix67.com/blog/archives/6348)
[五边形数定理的一种证明_欧拉五边形数定理-CSDN博客](https://blog.csdn.net/visit_world/article/details/52734860)
[Euler's pentagonal number theorem and Dedekind eta function | Travor's Home Page](https://travorlzh.github.io/2023/03/19/euler-pentagonal-and-dedekind-eta.html)