自然数前段的均衡样本

mathe

发现实际上将n是偶数情况也放入计算会更加容易计算母函数。 现在我找到一种方法应该可以通过留数来计算，不过计算方法还有点复杂，我还没有能够将最终结果化简出来。

wayne

嗯，有些繁琐的东西尽量让计算机来做， 期待mathe再鼓起一层浪。。。

mathe

我们现在还是将n是奇数，偶数统一处理，
如果找到了这种情况对应的母函数$f_k(X)$,那么n仅仅为奇数情况的母函数其实也很简单，
取函数${f_k(X)-f_k(-X)}/{2X}$，它的所有非零项次数为偶数，然后将$X^2$用$X$替换就可以了。
现在考虑
$1<=x_1<x_2<...<x_k<=n$
而且$x_1+x_2+...+x_k={(n+1)k}/2$
那么必然有
$0*(n+1-x_k)+1*(x_k-x_{k-1})+...+(k-1)*(x_2-x_1)+k*x_1={(n+1)k}/2$
做变量替换
${(u_0=n+1-x_k>=1),(u_1=x_k-x_{k-1}>=1),(...),(u_{k-1}=x_2-x_1>=1),(u_k=x_1>=1):}$
于是
$0*u_0+1*u_1+...+k*u_k={(n+1)k}/2$
其中$u_0,u_1,...,u_k$都是正整数，而且$u_0+u_1+...+u_k=n+1$
也就是原问题等于与这个问题的计数，而这个问题的计数相当于函数
$\prod_{h=0}^k {zx^h}/{1-zx^h}$展开后项$z^{n+1}x^{{(n+1)k}/2}$的系数（当然如果(n+1)k是奇数时只能为0）

mathe

上面连乘式
$\prod_{h=0}^k {zx^h}/{1-zx^h}=\prod_{h=0}^k(zx^h+z^2x^{2h}+z^3x^{3h}+...)$
为了得到$z^{n+1}x^{{(n+1)k}/2}=(zx^{k/2})^{n+1}$的各项系数，我们在上面展开式中再做变量替换
${(y=zx^{k/2}),(t=sqrt(x)):}$
于是上面连乘式变成
$\prod_{h=0}^k(y*t^(2h-k)+y^2*t^{4h-2k}+y^3*t^{6h-3k}+...)$
其中当k是偶数时，我们可以写成
$(\prod_{h=-k/2}^1y*t^{2h}+y^2*t^{4h}+y^3*t^{6h}+...)y/{1-y}(\prod_{h=1}^{k/2}y*t^{2h}+y^2*t^{4h}+y^3*t^{6h}+...)$
而当k是奇数时，我们可以写成
$(\prod_{h=-{k-1}/2}^0y*t^{2h-1}+y^2*t^{4h-2}+y^3*t^{6h-3}+...)(\prod_{h=0}^{{k-1}/2}y*t^{2h+1}+y^2*t^{4h+2}+y^3*t^{6h+3}+...)$
或者我们可以在k为偶数时定义
$h_y(t)=sqrt(y/{1-y})\prod_{h=1}^{k/2}y*t^{2h}+y^2*t^{4h}+y^3*t^{6h}+...=sqrt(y/{1-y})\prod_{h=1}^{k/2}{y*t^{2h}}/{1-y*t^{2h}}$
在k为奇数时定义
$h_y(t)=\prod_{h=0}^{{k-1}/2}y*t^{2h+1}+y^2*t^{4h+2}+y^3*t^{6h+3}+...=\prod_{h=0}^{{k-1}/2}{y*t^{2h+1}}/{1-y*t^{2h+1}}$
于是母函数问题变成了求函数$h_y(t)h_y(1/t)$中t的次数为0的项$R_0(y)$
我们现在假设$h_y(t)=\sum_{n=0}^{infty}a_n(y)t^n$,于是$h_y(1/t)=\sum_{n=0}^{infty}a_n(y)t^{-n}$
那么我们得出$R_0(y)=\sum_{n=0}^{infty}a_n(y)^2$

mathe

现在我先引用傅立叶级数里面的一个定理(Parseval等式)，对于函数
$f(t)={a_0}/2+\sum_{n=1}^{infty}(a_ncos(nt)+b_nsin(nt))$
有结论
${a_0^2}/2+\sum_{n=1}^{infty}(a_n^2+b_n^2)=1/{pi}int_{-pi}^{pi}f(t)^2dt$

mathe

于是对于函数$h_y(t)=\sum_{n=0}^{infty}a_n(y)t^n$,注意到$a_0(y)=0$
我们得到
${h_y(e^{is})+h_y(e^{-is})}/2=\sum_{n=1}^{infty}a_n(y)cos(ns)$
${h_y(e^{is})-h_y(e^{-is})}/{2i}=\sum_{n=1}^{infty}a_n(y)sin(ns)$
利用上面定理我们分别得到
$\sum_{n=1}^{infty}a_n(y)^2=1/{pi}int_{-pi}^{pi}({h_y(e^{is})+h_y(e^{-is})}/2)^2ds=1/{pi}int_{-pi}^{pi}({h_y(e^{is})-h_y(e^{-is})}/{2i})^2ds$
然后将后面两式相加求平均值得到
$\sum_{n=1}^{infty}a_n(y)^2=1/{2pi}int_{-pi}^{pi}h_y(e^{is})h_y(e^{-is})ds$
然后我们重新将$t=e^{is}$带入，由于$dt=-itds$,我们得到
$\sum_{n=1}^{infty}a_n(y)^2=1/{2pii}oint_{|t|=1}{h_y(t)h_y(1/t)}/tdt$
根据留数定理，等式右边为函数$1/th_y(t)h_y(1/t)$在$|t|<1$内部所有极点留数之和
于是问题转化为计算函数$1/th_y(t)h_y(1/t)$在单位圆$|t|<1$内部所有的留数之和

mathe

为了方便起见，我们只考虑(0,1)中的实数y,给定y在这个范围，
我们知道$g_y(t)=1/{h_y(t)}$是t的多项式，其所有根在单位圆外部，而且没有重根
可以得到$h_y(t)$的所有极点（有理函数，极点即分母的零点）都在单位圆外部,而函数$1/th_y(1/t)$的所有极点都是一阶的，而且在单位圆内部（0是可去极点，不予考虑）,其极点形式为$\root{h}{y}\omega_h^u$
其中$\omega_h$是方程$x^h=1$的单位根.
而对于每个极点$t_0$，由于它是一阶极点，这个极点出留数的值很简单，就是
$lim_{t->t_0}{t-t_0}/th_y(t)h_y(1/t)$,只要将有理多项式中项$t-t_0$消去，将$t=t_0$带入就可以了。
由此我们得到了母函数$R_0(y)$的计算方法。它需要就算$O(k^2)$个类似上面的极限，然后累加就可以了。
当然如何化简这个表达式还是一个问题

mathe

我们可以先用k=2作为例子（$k>=3$以上手工计算就有点头疼了）
对于k=2,$h_y(t)=sqrt(y/{1-y}){yt^2}/{1-yt^2}$
$h_y(1/t)$的两个极点为$t=sqrt(y)$和$t=-sqrt(y)$
计算$t=sqrt(y)$处的留数，先计算表达式
$y/{1-y}{t-sqrt(y)}/t{yt^2}/{1-yt^2}{yt^-2}/{1-yt^-2}$
$=y^3/{1-y}t/{(1-yt^2)(t+sqrt(y))}$
将$t=sqrt(y)$带入得到留数为${y^3}/{2(1-y)(1-y^2)}$
同样可以得到$t=-sqrt(y)$处留数也是这么多，最后得到母函数$R_0(y)={y^3}/{(1-y)(1-y^2)}$

mathe

用Pari/Gp计算展开母函数
(09:50) gp > y^3/(1-y)/(1-y^2)+y*O(y^100)
%1 = y^3 + y^4 + 2*y^5 + 2*y^6 + 3*y^7 + 3*y^8 + 4*y^9 + 4*y^10 + 5*y^11 + 5*y^1
2 + 6*y^13 + 6*y^14 + 7*y^15 + 7*y^16 + 8*y^17 + 8*y^18 + 9*y^19 + 9*y^20 + 10*y
^21 + 10*y^22 + 11*y^23 + 11*y^24 + 12*y^25 + 12*y^26 + 13*y^27 + 13*y^28 + 14*y
^29 + 14*y^30 + 15*y^31 + 15*y^32 + 16*y^33 + 16*y^34 + 17*y^35 + 17*y^36 + 18*y
^37 + 18*y^38 + 19*y^39 + 19*y^40 + 20*y^41 + 20*y^42 + 21*y^43 + 21*y^44 + 22*y
^45 + 22*y^46 + 23*y^47 + 23*y^48 + 24*y^49 + 24*y^50 + 25*y^51 + 25*y^52 + 26*y
^53 + 26*y^54 + 27*y^55 + 27*y^56 + 28*y^57 + 28*y^58 + 29*y^59 + 29*y^60 + 30*y
^61 + 30*y^62 + 31*y^63 + 31*y^64 + 32*y^65 + 32*y^66 + 33*y^67 + 33*y^68 + 34*y
^69 + 34*y^70 + 35*y^71 + 35*y^72 + 36*y^73 + 36*y^74 + 37*y^75 + 37*y^76 + 38*y
^77 + 38*y^78 + 39*y^79 + 39*y^80 + 40*y^81 + 40*y^82 + 41*y^83 + 41*y^84 + 42*y
^85 + 42*y^86 + 43*y^87 + 43*y^88 + 44*y^89 + 44*y^90 + 45*y^91 + 45*y^92 + 46*y
^93 + 46*y^94 + 47*y^95 + 47*y^96 + 48*y^97 + 48*y^98 + 49*y^99 + 49*y^100 + O(y
^101)
其中n+1项系数表示1~n中选择两个数数字之和为n+1的数目，正好满足要求

mathe

查询了一下wolfram关于Parseval定理的描述: http://mathworld.wolfram.com/ParsevalsTheorem.html