『二項係数 Part２』解答

◆愛知県　Y.M.Ojisan さんからの解答。

ｒ＝−１まで拡張して　次の定義としてもよい。
(1) B(0, r)　= 1 （r≧0）
(2) B(n, r)　= B(n-1, r+1) + B(n, r-1) （n＞0，r≧0 のとき）
(3) B(n, -1) = 0 （n＞0）

【問題１】
　式(2)を図に表すと　パスカルの三角形の半分を歪ませた構造であり、中央線上で０である。
従って、B(n, r)　は(1-x)(x+1)^2n+rの xⁿ の係数である。 ----(4)
即ち、

【問題２】　母関数から証明する。

　【補題１】　Ｐ，Ｑを非負整数とするとき

　∵　地道に微分を繰り返し整理すると等式が得られる。

2^2Q+12^P(-1)^P+1=2^2Q2^P+1(-1)^P+1=4^Q(-4)^P+1 であるから補題１が成立する。

　【補題２】　Ｑを１以上の整数とし、　Ｐ＝flloor(Q/2) R=floor((Q-1)/2)とするとき。　

∵　Ｑが偶数と奇数の場合に分け、２項展開を行って、補題１を適用する。このとき√（１−４ｘ）の偶数乗の項はｘのＰ次以下の整式なのでＰ＋１回微分すると０であることを利用する。
Ｑ＝２Ｐ 　Ｐ≧１　の時 Ｒ＝Ｐ−１　であって、

同様に　Ｑ＝２Ｐ＋１　Ｐ≧０　の時 Ｒ＝Ｐ　であって、

　【補題３】　Ｂ（ｎ，ｒ）の母関数　f（ｒ、ｘ）は　下記である。　


∵　次の計算を行うと

であり、下記である。

上記式は補題２に他ならず、

である。これを計算すれば補題３が得られる。

【問題２本題】
　　補題３より　ｆ（(u+v+1)+1、ｘ）＝ｇ（ｘ）^u+v+2　である。
　　ｇ（ｘ）^u+v+2＝ｇ（ｘ）^u+1×ｇ（ｘ）^v+1=ｆ（u+1、ｘ）×ｆ（ｖ+1、ｘ）である。
　　この等式のｘのｎ乗の係数を比較すれば問題の等式（下記）が得られる。

【問題３】　初等的に求める。

（１）一列に並んだ２ｎ−１個からｎを選ぶ組み合わせの数はC(2n-1,n）＝C(2n-1,n-1)である。
一方、選んだものの左端の位置（ｋ）　ｋ＝１〜ｎで分類して合算すると　

であり、これらは等しい。

(2)一列に並んだ２ｎ個からｎ+1を選ぶ組み合わせの数はC(2n,n+1）＝C(2n,n-1)である。
一方、選んだものの左端から２番目のもの位置（ｋ＋１）　ｋ＝１〜ｎ　で分類して合算すると
左側　ｋとおり、右側　 C(2n-k-1, n-1)とおり　であるから

であり、これらは等しい。

(3)一列に並んだ２ｎ+1個からｎ+2を選ぶ組み合わせの数はC(2n+1,n+2）＝C(2n+1,n-1)である。
一方、選んだものの左端から3番目のもの位置（ｋ＋2）　ｋ＝１〜ｎ　で分類して合算すると
左側　ｋ(k+1)/2 とおり、右側　 C(2n-k-1, n-1)とおり　であるから

であり、これらは等しい。問題２の結果とあわせると、

【問題４】　これも初等的に求める。

（１）一列に並んだ２ｎ−１個からn個以上を選ぶ組み合わせの数の２倍は対称性から　2^2n-１である。
一方、選んだものの右からｎ番目のもの左端からの位置（ｋ）　ｋ＝１〜ｎで分類して合算して２倍すると　

であり、これらは等しい。

（2）一列に並んだ２ｎ個からn＋１個以上を選ぶ組み合わせの数の２倍は対称性から　2²ⁿ−C(2n,n)である。
一方、選んだものの右からｎ＋１番目のもの左端からの位置（ｋ）　ｋ＝１〜ｎで分類して合算して２倍すると　

であり、これらは等しい。計算すると　Ans＝ｎC(2n,n)

（3）一列に並んだ２ｎ+1個からn＋2個以上を選ぶ組み合わせの数の２倍は対称性から　2²ⁿ⁺¹-2C(2n+1,n)である。
一方、選んだものの右からｎ＋2番目のもの左端からの位置（ｋ）　ｋ＝１〜ｎで分類して合算して２倍すると　

であり、これらは等しい。
計算すると　Ans＝（2²ⁿ⁺¹-2C(2n+1,n)）*n*(n+1)＋(4n+1)*問題４（２）Ans-(4n+2)*n*問題４(1)Ans
即ち

【Ｐ．Ｓ．】　問題３の流れでは　(4)として　

が成立するのかと思いましたが、成立していないので、Ｂの方から攻めるのはやめました。偶然の産物でしょうか？

【出題者のコメント】

Y.M.Ojisan 氏に早速解かれてしまいましたが，問題２と問題３（P.S.）に関してコメントします。

●問題２に対するコメント

上記補題３の B(n, r) の母関数は漸化式から直接導くこともできます。 まず，母関数を番号をずらさずに

	g(x, r)　=　B(0, r) + B(1, r) x + B(2, r) x2 + …

と定義すると，B(n, r) の関係式から

	x g(x, 1) + 1　=　g(x, 0)
	x g(x, r+1) + g(x, r-1)　=　g(x, r)

が得られます。 ここで，g(x, 0) は Catalan 数の母関数ですから，

g(x, 0)　=

2 1+√(1-4x)

（ =

-1 2x

∞ Σ r=1

(-4x) r (

1 2

)(

1 2

- 1 ) … (

1 2

- r + 1 )  =

∞ Σ r=0

x r

C(2r, r) r + 1

）

であり，これを用いて

g(x, 1)　=

g(x, 0) - 1 x

=

1 x

{

2 1+√(1-4x)

- 1 }　=

1-√(1-4x) x (1+√(1-4x))

=

4 (1+√(1-4x)) 2

=　{ g(x, 0) } 2

となるので，あとは

	g(x, r+1)　=	g(x, r) - g(x, r-1) x	=	g(x, 0) r+1 - g(x, 0) r x	=	g(x, 0) - 1 x	{ g(x, 0) } r　=　{ g(x, 0) } r+2

のようにして g(x, r) の具体的な式が得られます （数学的帰納法）。 以上の結果を用いれば，

	g(x, u) g(x, v)　=　{ g(x, 0) } u+v+2　=　g(x, u+v+1)

が成り立つので，両辺の xⁿ の係数を比較して

	Σ	B(i, u) B(j, v)　=　B(n, u+v+1)
	i+j=n

が得られます。

●問題３に対するコメント

当初，出題者は母関数を利用した下記のような解答を用意していたのですが，これをもう一段進めて計算してみると，

	n Σ k=0	k3 C(2n-k-1, n-1)　=	2 n2 (13n - 1) (n + 1)(n + 2)(n + 3)	C(2n-1, n)　=	n (13n - 1) 4 (2n + 1)	B(n-1, 3)

が得られました。 さらにこの一般化を考えることも不可能ではないでしょうが，B(・,・) につく係数は複雑なものになりそうです。

［母関数を利用した解答３・４］

6 本の等式で，n の代わりに n+1 とした式を証明することにする。 さらに，証明すべき式を次のように変形して，計算しやすい形に直しておく：

	n+1 Σ k=1	φ(k) C(2n-k+1, n)　=	n Σ k'=0	φ(k'+1) C(2n-k', n)　=	n Σ k''=0	φ(n-k''+1) C(n+k'', k'')

ここで，C(n+k, k) の母関数を次の式で定義する。

	fn(x)　=	n Σ k=0	xk C(n+k, k)

ただし，以下では f_n(x) の式で n を動かすことがないので，n を省略して f(x) と書くことにする。 これを用いると，

問題 3 (1)　：	n Σ k=0	C(n+k, k)  =　f(1)

問題 4 (1)　：	n Σ k=0	2n-k+1 C(n+k, k)  =　2n+1	n Σ k=0		1 2k	C(n+k, k)  =　2n+1  f(	1 2	)

問題 3 (2)　：	n Σ k=0	(n-k+1) C(n+k, k)  =　(n+1)		n Σ k=0	C(n+k, k)  -		n Σ k=1	k C(n+k, k)  =　(n+1) f(1) - f’(1)

問題 4 (2)　：

n Σ k=0

(n-k+1) 2n-k+1 C(n+k, k)  =　2n+1 ｛ (n+1)

n Σ k=0

1 2k

C(n+k, k)  -

1 2

n Σ k=1

k

1 2k-1

C(n+k, k) ｝

=　2n+1 ｛ (n+1) f(	1 2	)　-	1 2	f’(	1 2	) ｝

問題 3 (3)　：

n Σ k=0

(n-k+1)2 C(n+k, k)  =　(n+1)2

n Σ k=0

C(n+k, k)  - 2(n+1)

n Σ k=1

k C(n+k, k)  +

n Σ k=1

k2 C(n+k, k)

=　(n+1)2 f(1) - 2(n+1) f’(1) + ( f’(1) + f”(1) )

問題 4 (3)　：	n Σ k=0	(n-k+1)2 2n-k+1 C(n+k, k)

=　2n+1 ｛ (n+1)2

n Σ k=0

1 2k

C(n+k, k)  -　(n+1)

n Σ k=1

k

1 2k-1

C(n+k, k)　+

1 2

n Σ k=1

k2

1 2k-1

C(n+k, k) ｝

=　2n+1 ｛ (n+1)2 f(	1 2	)　-　(n+1) f’(	1 2	)　+	1 2	f’(	1 2	)　+	1 4	f”(	1 2	) ｝

のように，すべての式の値を f(x) やその導関数の 1 と

1 2

における値で表すことができる。

（注：　問題 3・4 の (3) では，　( x f’(x) )’　=	n Σ k=1	k2 xk-1	C(n+k, k)  　のようにして k2 を作る。）

一方， f(x) について

	d dx	(1-x) f(x)　=　n f(x)　-　(n+1) C(2n+1, n) xn

が成立することがわかる。 そこで，左辺の微分を計算し，両辺を整理して，

	(1-x) f’(x)　=　(n+1) { f(x)　-　C(2n+1, n) xn } 　　　　　　(*)

を得る。

[1]　この式に x = 1 を代入すれば，

	f(1)　=　C(2n+1, n)

を得る。

[2]　また， x≠1 のとき，微分方程式

	f’(x)　=	(n+1) f(x)　-　(n+1) C(2n+1, n) xn 1 - x	(**)

を解くと，

	f(x)　=	1　-　(n+1) C(2n+1) x ∫ 0   tn (1-t)n dt  (1 - x)n+1

となるが，この式で x =

1 2

とおけば

	f(	1 2	)　=　2n

を得る。

[3]　式 (**) で x→1 の極限を取り，右辺を l'Hospital の定理を用いて計算すると，

	f’(1)　=　- (n+1) { f’(1) - n C(2n+1, n) }

すなわち，

	f’(1)　=	n(n+1) n+2	C(2n+1, n)

を得る。　（注：　f(x) は多項式なので，値の存在は保証されている）

[4]　式 (**) に x =

1 2

を代入すると，

	f’(	1 2	)　=　2(n+1) { 2n　-　C(2n+1, n)	1 2n	}

を得る。

[5]　式 (*) をさらに微分すると

	f”(x)　=	(n+2) f’(x)　-　n(n+1) C(2n+1, n) xn-1 1 - x	(***)

となるから， x→1 の極限を取って，

	f”(1)　=	(n-1)n(n+1) n+3	C(2n+1, n)

を得る。

[6]　式 (***) に x =

1 2

を代入すると，

	f”(	1 2	)　=　2(n+2) f’(	1 2	)　-　2n(n+1) C(2n+1, n)	1 2n-1

を得る。

以上 [1]〜[6] の具体的な値を問題 3・4 の (1)〜(3) に代入すれば，証明すべき式の右辺が得られる。

◆愛知県　Y.M.Ojisan さんからのコメント。

問題３と問題４を母関数から解くほうは、次の関係をベースに、
問題３はa=1 問題４はa=2として考えました。

a=1のとき（問題３）では下記ですが、これに(1+x)^2n-1を両辺に掛け、ｘのｎ−１乗の係数を比較すれば（１）です。

　また、(1+x)²ⁿを両辺に掛け、ｘのｎ乗の係数を比較すれば
（２）のｋのところが(2-k/n)のものが得られます。
さらに、(1+x)^2n＋１を両辺に掛け、ｘのｎ＋１乗の係数を比較すれば
（３）のｋ²のところが(2-k/n)（2−(k+1)/(n+1)）のものが得られます。
後は四則演算です。

a=２のとき（問題４）では下記ですが、これに(1+x)^2n-1を両辺に掛け、
Σ内のｘのｎ−１乗の係数を計算すれば（１）です。

　これは若干説明が必要です。
Σの前に（１−ｘ）が掛かっています。
これはΣ内のx^pとx^p−１の項の係数の差が右辺のx^pの項の係数であることを示しています。
従って左辺のΣ内のx^ｎ−１の係数は右辺のｘの０〜ｎ−１乗の係数の和となります。

右辺は２^ｎ＋１（１＋ｘ）^ｎー１−２（１＋ｘ）^２ｎー１です。
１項目はｘ＝１　、　２項目は対称性からｘ＝１とした値の半分がその和となることが判ります。

（２）も問題３と同様で(1+x)²ⁿを両辺に掛け、Σ内のｘのｎ乗の係数を求めます。
右辺は２^ｎ＋１（１＋ｘ）^ｎ−２（１＋ｘ）^２ｎです。
１項目はｘ＝１、２項目は対称性からｘ＝１とした値の半分とＣ（２ｎ，ｎ）がその和となります。

（３）も問題３と同様、(1+x)^2n＋１を両辺に掛け、Σ内のｘのｎ＋１乗の係数を求めます。
右辺は２^ｎ＋１（１＋ｘ）^ｎ＋１−２（１＋ｘ）^２ｎ＋１です。
１項目はｘ＝１、２項目は対称性からｘ＝１とした値の半分がその和となります。
後はまた四則演算です。

　『二項係数 Part２』へ

　数学の部屋へもどる