【(2nCn)/(n+1)】カタラン数【(2n)!/(n+1)!n!】

209 ：１３２人目の素数さん ：2006/04/19(水) 00:25:21

　Ｃ[2k,k]Ｃ[2n-2k,n-k] が Ｃ[n,k] で割り切れることを示せ。
　お長居します。

さくらスレ１９０
http://science4.2ch.net/test/read.cgi/math/1145250000/209

>33
任意の素数pについて
　Ｃ(2k,k)･Ｃ(2n-2k,n-k) 中のpの巾指数 ≧ Ｃ(n,k) 中のpの巾指数.
を示す。
　Ｃ(2k,k)･Ｃ(2n-2k,n-k) = (2k)!(2n-2k)!/(k!･k!･(n-k)!･(n-k)!),
　Ｃ(n,k) = n!/(k!･(n-k)!).

さて、1,2,…,m のうち p^e の倍数は [m/(p^e)] 個(p^e自身も含む)だから
　m!中のpの巾指数 = ��(e=1,m) [m/(p^e)].
これと補題↓を使うと, 成り立つことを示せる。(終)

※ p進表示 m=��(e=0,m) d_e･p^e を使えば pの巾指数 = ��(e=1,m) d_e･(p^e -1)/(p-1).

(補題)
　[2x] + [2y] - 2[x] - 2[y] ≧ [x+y] - [x] -[y].
(略証)
　x=[x]+{x}, y=[y]+{y} とおく。0≦{x},{y}<1.
　(左辺) = [2{x}] + [2{y}],　(右辺) = [{x}+{y}].
　　(右辺)=1　⇒　{x}+{y}≧1　⇒　2{x}≧1 or 2{y}≧1　⇒　(左辺)≧1.
　　(左辺)=0　⇒　2{x}<1 & 2{y}<1　⇒　{x}+{y}<1　⇒ (右辺)=0.
∴ (左辺) ≧ (右辺).