分割函数p(n)

葡萄糖

分割函数\(p(n)\)的每一项总能用其他项的和表示
A000041         a(n) = number of partitions of n (the partition numbers). (Formerly M0663 N0244)
\(1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015……\)
例如：
\(1=1\)
\(2=1+1\)
\(3=2+1\)
\(5=2+3\)
\(7=2+5\)
\(11=1+1+2+7=1+2+3+5\)
\(15=3+5+7\)
\(22=7+15\)
\(30=3+5+7+15\)
\(42=5+7+30\)
\(56=1+11+42\)
\(77=2+3+5+7+11+56\)
\(101=2+22+77\)
\(135=1+1+2+30+101\)
补充：问题：求证：分割函数\(p(n)\)的每一项总能用其他项的和表示

kastin

问题呢？

葡萄糖

kastin 发表于 2014-6-22 16:41
问题呢？

http://zh.wikipedia.org/wiki/整數分拆
分割函数p(n)的每一项总能用其他项的和表示

Lwins_G

只需证明`p(n) \leq \sum_{j=0}^{n-1}p(j)`，而这是显然的。

kastin

终于明白你的意思了，答案告诉你吧，是这个$$p(n) = \sum_{k=±1,±2,±3,...}(-1)^{k-1}p(n-\frac{k(3k-1)}{2}) $$
上面这个叫做欧拉五边形定理，即约定`p(r)=0\quad(r<0)`，那么
$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ... $$

或者利用欧拉乘积公式以及`p(n)`的母函数，也可以得到下面这个递归关系$$p(n)=\frac{1}{n}\sum_{k \geqslant 1} \sigma(k)p(n-k)$$其中数论函数`\sigma(k)`是正整数`k`所有约数的个数。