面白い問題おしえて~な@数学板 組合せ20051012224832

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

組合せ10-4

399 名前:132人目の素数さん[] 投稿日:2005/10/12(水) 22:48:32
Σ_[p+q+r=n] C[p+q,p]C[q+r,q]C[r+p,r] = Σ_[s=0,n] C[2s,s]
を示せ。

解答

460 名前:132人目の素数さん[] 投稿日:2005/10/17(月) 14:07:34
>>399
texでもないと証明が読めないのでtexで。(1)
$$\sum_{p\geq 0}\frac{(p+q)!}{p!q!}x^p=\frac{1}{(1-x)^{1+q}},
\sum_{p\geq 0}\frac{(p+r)!}{p!r!}(\frac{t}{x})^p=
\frac{1}{(1-\frac{t}{x})^{1+r}}$$
から$0<t< k <1$ を固定して, $C:\mid x \mid =k$に関する周回積分
に関する等式
$$\sum_{p\geq 0}\frac{(p+q)!}{p!q!}
\frac{(p+r)!}{p!r!}t^p
=\frac{1}{2\pi i}
\int_C\frac{1}{(1-x)^{1+q}(1-\frac{t}{x})^{1+r}}\frac{dx}{x}$$
を得る。これに$\displaystyle\frac{(q+r)!}{q!r!}t^{q+r}$をかけて
$q+r=m, q\geq 0, r\geq 0$に関して加えれば、
\begin{align*}
& \sum_{q+r=m, q\geq 0, r\geq 0}\sum_{p\geq 0}\frac{(p+q)!}{p!q!}
\frac{(p+r)!}{p!r!}\frac{(q+r)!}{q!r!}t^{p+q+r} \\
= &\frac{1}{2\pi i}
\int_C\frac{1}{(1-x)(1-\frac{t}{x})}
(\frac{1}{1-x}+\frac{1}{1-\frac{t}{x}})^m
\frac{dx}{x} t^{m}
\end{align*}

461 名前:132人目の素数さん[] 投稿日:2005/10/17(月) 14:08:14
>>399
texでもないと証明が読めないのでtexで。(2)
上の式を(1)として
$m$に関する和を取るのだが、その前に$C$を$\bold C-\{1,t\}$でのhomotopy
equivalentな$D$で取り換えて、あとの都合上、$D$上で
$$\mid x-t \mid \geq\frac{1}{8}, \mid 1-x \mid \geq \frac{1}{8},
\mid x \mid <1$$
としたいのだが、これは$t$が十分$0$に近いときに可能なのでこの様に
$t$を取り換えておく。さらに必要なら$t$を小くとり、$D$上で
$$\mid t \frac{x^2-2x+t}{(1-x)(x-t)} \mid <1$$
となるようにとる。こうしておいて、$m\geq 0$に関して和をとれば、
\begin{align*}
& \sum_{q+r=m, q\geq 0, r\geq 0}\sum_{p\geq 0}\frac{(p+q)!}{p!q!}
\frac{(p+r)!}{p!r!}\frac{(q+r)!}{q!r!}t^{p+q+r} \\
= &\frac{1}{2\pi i}
\int_D\frac{dx}{(t-1)(x^2-x+t)} \\
=&\frac{1}{1-t}(1-4t^2)^{-\frac{1}{2}}
\end{align*}
ここで
$$(1-4t^2)^{-\frac{1}{2}}=\sum_{i \geq 0}\frac{(2i)!}{i!i!}t^{2i}$$
をもちいて$t^n$の係数を比較して定理を得る。

462 名前:132人目の素数さん[] 投稿日:2005/10/17(月) 17:25:30
>>461
訂正 1-4t^2を1-4tに

463 名前:132人目の素数さん[sage] 投稿日:2005/10/18(火) 10:36:09
>>399
やっとできたと思ったら答えでてたのか。せっかくなので書いてみる。TeXじゃないし。
∑[p+q+r=n]C[p+q,p]C[q+r,q]C[r+p,p]をanとおく。
非負整数nに対して多項式Pnを
 Pn=∑[r=0,n](xy(x+y+2))^(n-r)・((x+1)(y+1))^r
とおく。まずこの(xy)^nの項の係数がanに等しいことをしめす。
(x+y+2)^(n-r)=(x+1+y+1)^(n-r)に2項定理を使って
 Pn=(xy)^(n-r)∑[r=0,n]∑[p=0,n-r]C[n-r,p](x+1)^(p+r)・(y+1)^(n-p)
であるが(x+1)^(p+r)・(y+1)^(n-p)の(xy)^rの係数は
C[p+r,r]C[n-p,r]に等しい。よって主張が得られた。
容易に
 Pn=xy(x+y+2)P[n-1]+((x+1)(y+1))^n――(1)
  =(x+1)(y+1)P[n-1]+(xy(x+y+2))^n――(2)
であるから(xy)×(2)-(1)により
(xy-1)Pn=(xy)^2-xy)P[n-1]+(xy(x+y+2))^n-((x+1)(y+1))^n
 ∴Pn=xyP[n-1]+((xy)^(n+1)・(x+y+2)^n-((x+1)(y+1))^n)/(xy-1)
そこで右辺第2項の(xy)^nの項を計算する。
 ((xy)^(n+1)・(x+y+2)^n-((x+1)(y+1))^n)/(xy-1)
 =((xy)^n+(xy)^(n+1)+・・・+1)(x+y+2)^n+((x+y+2)^n-((x+1)(y+1))^n)/(xy-1)
であるが第2項はx,yに関する次数が2n未満の多項式であるので(xy)^nの項は現れない。
第1項の(xy)^nの係数は(x+y+2)^nの(xy)^iの形の項の係数の総和にひとしい。
それはx=t^2,y=1/t^2を代入したときの定数項に等しいがそれは
(x+y+2)^n=(t+1/t)^2nであるゆえC[2n,n]にひとしい。
以上よりPn-xyP[n-1]の(xy)^nの項の係数はC[2n,n]に等しい。
P0=1の定数項は1であるゆえC[0,0]に等しくよって以上により
an=∑[s=0,n]C[2s,s]となる。□