n分拆成3个整數有$\frac{n^2}{12}$种方法

hbghlyj

Wikipedia
OIwiki
分拆：将自然数 $n$ 写成递降正整数之和
$$
n=r_1+r_2+\ldots+r_k \quad r_1 \ge r_2 \ge \ldots \ge r_k \ge 1
$$和式中每个正整数称为一个部分。
分拆数：$p(n)$。自然数 $n$ 的分拆方法数。
自 $0$ 开始的分拆数：

$n$	0	1	2	3	4	5	6	7	8
$p(n)$	1	1	2	3	5	7	11	15	22

4可以用5種方法寫成和式：
    4
    3 + 1
    2 + 2
    2 + 1 + 1
    1 + 1 + 1 + 1
因此 $p(4)=5$。

部分個數上限的分拆
當限定將\(n\)表示成剛好\(k\)個正整數之和時，可以表示為\(p_k(n)\)。顯然，\(p(n) = \sum_{k=1}^{n} p_k(n)\)。

• 對於\(n>1\)，\(p_n(n) = p_1(n) = 1\)
• \(p_2(n) = \left\lfloor \frac{n}{2} \right\rfloor\) (OEIS:A004526)
• \(p_3(n)\) = 最接近\(\frac{n^2}{12}\)的正整數。(OEIS:A069905)
• \(p_{n-1}(n) = 1\)
• \(p_k(n) = p_{k-1}(n-1) + p_k(n-k)\)

如何证明3.呢

hbghlyj

Mathematical Gems III第44页
$$
\frac{n^2}{12}-\frac{1}{3}\le p_3(n)\le\frac{n^2}{12}+\frac{1}{4}.
$$

---

证明：
从Ferrer图的转置，看出$p_3(n)$等于将$n$分成若干个$1$、若干个$2$、若干个$3$之和且至少有一个$3$的方法数.
把这个必须的$3$扣掉，$p_3(n)$就等于将$n-3$分成若干个$1$、若干个$2$、若干个$3$之和的方法数.
构造生成函数\[f(x)= \left(1+x+x^2+x^3+\cdots\right)\left(1+x^2+x^4+x^6+\cdots\right)\left(1+x^3+x^6+x^9+\cdots\right) .\]$p_3(n)$等于$f(x)$的$x^{n-3}$项的系数
\begin{aligned} f(x) & =(1-x)^{-1}\left(1-x^2\right)^{-1}\left(1-x^3\right)^{-1} \\ & =\frac{1}{(1-x)\left(1-x^2\right)\left(1-x^3\right)} .\end{aligned}部分分式，得\begin{aligned} f(x) & =\frac{1 / 6}{(1-x)^3}+\frac{1 / 4}{(1-x)^2}+\frac{1 / 4}{1-x^2}+\frac{1 / 3}{1-x^3} \\ & =\frac{1}{6}(1-x)^{-3}+\frac{1}{4}(1-x)^{-2}+\frac{1}{4}\left(1-x^2\right)^{-1}+\frac{1}{3}\left(1-x^3\right)^{-1} .\end{aligned}Therefore, the desired coefficient of $x^{n-3}$ is the sum of the coefficients of $x^{n-3}$ that are obtained from these four parts. But these may be extracted by straightforward applications of the binomial theorem. From the first part we get
\begin{aligned}
& \frac{1}{6} \cdot \frac{(-3)(-4) \cdots[-3-(n-3)+1]}{(n-3) !}(-1)^{n-3} \\
& =\frac{1}{6} \cdot \frac{3 \cdot 4 \cdots(n-1)}{(n-3) !}=\frac{1}{6} \cdot \frac{(n-2)(n-1)}{2} \text {, }
\end{aligned}and from the second part we similarly obtain $(1 / 4)(n-2)$.
In the third part, only even powers of $x$ occur, and we obtain the coefficient 0 if $n-3$ is odd, and $(1 / 4)(1)=1 / 4$ if $n-3$ is even. We may express this by saying that the coefficient is $(1 / 4) k$, where $k$ is either 0 or 1 . Similarly, in the final part, the coefficient is $(1 / 3) t$, where $t$ is either 0 or 1 . In these terms, then, we have
\begin{aligned}
p_3(n) & =\frac{1}{6} \cdot \frac{(n-1)(n-2)}{2}+\frac{1}{4}(n-2)+\frac{1}{4} k+\frac{1}{3} t \\
& =\frac{n^2-4+3 k+4 t}{12} .
\end{aligned}Now the most that $3 k+4 t$ can be is 7 and the least is 0 . Therefore, we have
$$
\frac{n^2-4}{12} \leq p_3(n) \leq \frac{n^2+3}{12},
$$
that is,
$$
\frac{n^2}{12}-\frac{1}{3} \leq p_3(n) \leq \frac{n^2}{12}+\frac{1}{4} .
$$