分割函数p(n)
本帖最后由 葡萄糖 于 2014-6-22 17:37 编辑分割函数\(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)\)的每一项总能用其他项的和表示 问题呢？ 本帖最后由 葡萄糖 于 2014-6-22 17:36 编辑
kastin 发表于 2014-6-22 16:41
问题呢？
http://zh.wikipedia.org/wiki/整數分拆
分割函数p(n)的每一项总能用其他项的和表示 只需证明`p(n) \leq \sum_{j=0}^{n-1}p(j)`，而这是显然的。 终于明白你的意思了，答案告诉你吧，是这个$$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`所有约数的个数。
页:
[1]