n番目のカタラン数 f[n] は、f[n]＝2nＣn－2nＣ(n-1) と書けます。
カタラン数の数列の母関数をF(x)とします。
つまり、
F(x)＝f[0]＋f[1]x＋f[2]x^2＋f[3]x^3＋……
ということです。
カタラン数の性質より、F(x)は F(x)＝1＋xF(x)^2 を満たします。
そのことを一般化して、
g[n]＝(kn)Ｃn＋(1-k)×(kn)Ｃ(n-1) の数列の母関数G(x)が、
G(x)＝1＋xG(x)^k を満たすこと
に気付きました。
具体例として k＝3 のときを見ます。
g[n]＝3nＣn－2×3nＣ(n-1)
なので
g[0],g[1],g[2],g[3],g[4],……
は
0Ｃ0－2×0Ｃ(-1) , 3Ｃ1－2×3Ｃ0 , 6Ｃ2－2×6Ｃ1 , 9Ｃ3－2×9Ｃ2 , 12Ｃ4－2×12Ｃ3 ,……
です。計算すると
1,1,3,12,55,……
なので、
母関数G(x)＝1＋1x＋3x^2＋12x^3＋55x^4＋……
です。
G(x)^3＝1＋3x＋12x^2＋55x^3＋……
なので、
確かに G(x)＝1＋xG(x)^3 を満たしそうです。
もう少し一般化した、
G(x)＝1＋xG(x)^k とするとき
(kn+a)Ｃn＋(1-k)×(kn+a)Ｃ(n-1) の数列の母関数が、
G(x)^(a+1) になること
を証明します。
a＝-1 のとき つまり、
(kn-1)Ｃn＋(1-k)×(kn-1)Ｃ(n-1) の数列の母関数が G(x)^0＝1 に等しいこと
さえ示せば、
『パスカルの三角形やカタラン数での母関数の関係』で証明した
(kn+b)Ｃn の数列の母関数にG(x)^w を掛けると (kn+b+w)Ｃn の母関数になること
を使うことで、証明が終わります。
(kn-1)Ｃn＋(1-k)×(kn-1)Ｃ(n-1) が n＝0 のとき1、nが正の整数のとき0だと示せば、母関数が 1=G(x)^0 だと分かります。
n＝0 のとき
(kn-1)Ｃ0＋(1-k)×(kn-1)Ｃ(n-1)
＝(-1)Ｃ0＋(1-k)×(-1)Ｃ(-1)
＝1 ※aＣ0＝1, aＣ(-1)＝0 なので
nが正の整数のとき
(kn-1)Ｃn＋(1-k)×(kn-1)Ｃ(n-1)
＝(kn-1)Ｐn×1/n!＋(1-k)×(kn-1)Ｐ(n-1)×1/(n-1)!
＝( (kn-1)Ｐn＋n(1-k)×(kn-1)Ｐ(n-1) )×1/n!
※1/n!を外に出した
＝0×1/n!
※(kn-1)Ｐn＝(kn-n)×(kn-1)Ｐ(n-1) なので
＝0
よって
(kn-1)Ｃn＋(1-k)×(kn-1)Ｃ(n-1) の母関数が G(x)^0=1 に等しい
と示せたので
(kn+a)Ｃn＋(1-k)×(kn+a)Ｃ(n-1) の母関数が G(x)^(a+1) になること
が証明できました。
ちなみに、
(kn+a)Ｃn－(k-1)×(kn+a)Ｃ(n-1)＝(kn+a)Ｃn×(a+1)/(a+1+kn-n)
※ただしa+1+kn-n≠0
なので
(kn+a)Ｃn×(a+1)/(a+1+kn-n) の数列の母関数も G(x)^(a+1) になります。
m行目の母関数が d(x)^m (d(x)はxについての多項式) になるような、
一般化したパスカルの三角形でも同様のことが言えます。
s次多項式 d(x) のr次の係数を {r} と書くことにします。
つまり
d(x)＝{0}＋{1}x＋{2}x^2＋……＋{s}x^s
ということです。
また、
d(x)^u の x^v の係数を uＤv と書くことにします。
※(1+x)^u の x^v の係数が uＣv と書けることに、対応した表記にしました。
{r}＝1Ｄr です。
e[n]＝{0}×nkＤn＋(1-k){1}×nkＤ(n-1)＋(1-2k){2}×nkＤ(n-2)＋……＋(1-sk){s}×nkＤ(n-s)
の数列の母関数E(x)は、
E(x)＝d(xE(x)^k)
つまり
E(x)＝{0}＋{1}(xE(x)^k)＋{2}(xE(x)^k)^2＋……＋{s}(xE(x)^k)^s
になることに気付きました。
{0}＝{1}＝1,{r}＝0 (rは2以上の整数) とすると、前半に証明した命題と同じになります。
前半のパスカルの三角形の時と同様、もう少し一般化して
{0}×(nk+a)Ｄn＋(1-k){1}×(nk+a)Ｄ(n-1)＋……＋(1-sk){s}×(nk+a)Ｄ(n-s)
の数列の母関数が
E(x)^(a+1)になること
を証明します。
『パスカルの三角形やカタラン数での母関数の関係 その２』の内容を踏まえれば
(nk+b)Ｄn の数列の母関数にE(x)^w を掛けると (nk+b+w)Ｄn の母関数になること
が分かるので、
a＝-1 のときを示せば十分です。
なので
{0}×(nk-1)Ｄn＋(1-k){1}×(nk-1)Ｄ(n-1)＋……＋(1-sk){s}×(nk-1)Ｄ(n-s)
の数列の母関数が E(x)^0＝1 になることを示します。
d(x)^nk＝d(x)×d(x)^(nk-1)
の n次の係数を対応させると
nkＤn＝{0}×(nk-1)Ｄn＋{1}×(nk-1)Ｄ(n-1)＋{2}×(nk-1)Ｄ(n-2)＋……＋{s}×(nk-1)Ｄ(n-s)
だと分かるので
{0}×(nk-1)Ｄn＋(1-k){1}×(nk-1)Ｄ(n-1)＋……＋(1-sk){s}×(nk-1)Ｄ(n-s)
＝nkＤn－k×{1}×(nk-1)Ｄ(n-1)－2k×{2}×(nk-1)Ｄ(n-2)－……－sk×{s}×(nk-1)Ｄ(n-s)
です。
n＝0 のときに1、nが正の整数のときに0になると示せば、
母関数が 1＝E(x)^0 だと分かります。
n＝0 のとき
nkＤn－k×{1}×(nk-1)Ｄ(n-1)－2k×{2}×(nk-1)Ｄ(n-2)－……－sk×{s}×(nk-1)Ｄ(n-s)
＝0Ｄ0－k×{1}×(-1)Ｄ(-1)－2k×{2}×(-1)Ｄ(-2)－……－sk×{s}×(-1)Ｄ(-s)
＝0Ｄ0 ※aＤb＝0 (bは負の整数) なので
＝1 ※aＤ0＝{0}^a なので
nが正の整数のとき
nkＤn－k×{1}×(nk-1)Ｄ(n-1)－2k×{2}×(nk-1)Ｄ(n-2)－……－sk×{s}×(nk-1)Ｄ(n-s)＝0
を証明するには、移項した
nkＤn＝k×{1}×(nk-1)Ｄ(n-1)＋2k×{2}×(nk-1)Ｄ(n-2)＋……＋sk×{s}×(nk-1)Ｄ(n-s)
を示せばいいです。以下、この式を☆で表します。
〈0〉,〈1〉,〈2〉,〈3〉,……,〈n〉 を0以上の整数とし、
〈0〉＋〈1〉＋〈2〉＋〈3〉＋……＋〈n〉＝nk
1×〈1〉＋2×〈2〉＋3×〈3〉＋……＋n×〈n〉＝n
を満たすとします。
{0}^〈0〉×{1}^〈1〉×{2}^〈2〉×……×{n}^〈n〉 の係数が☆の両辺で等しいと示せば、
☆が真だと分かります。
☆の左辺 nkＤn の {0}^〈0〉×{1}^〈1〉×{2}^〈2〉×……×{n}^〈n〉 の係数は、
多項定理より
(nk)!/〈0〉!〈1〉!〈2〉!……〈n〉!
です。
zを0以上n以下の整数とすると
zk×{z}×(nk-1)Ｄ(n-z) の
{0}^〈0〉×{1}^〈1〉×{2}^〈2〉×……×{n}^〈n〉の係数は
z×〈z〉k×(nk-1)!/〈0〉!〈1〉!〈2〉!……〈n〉!
です。
〈z〉＝0 のときは係数も0になり、
〈z〉が正の整数のときは、
(nk-1)Ｄ(n-z)＝〈z〉×(nk-1)!/〈0〉!〈1〉!〈2〉!……〈n〉!
になるからです。
よって、☆の右辺の {0}^〈0〉×{1}^〈1〉×{2}^〈2〉×……×{n}^〈n〉の係数は、
(1×〈1〉＋2×〈2〉＋…＋n×〈n〉)k×(nk-1)!/〈0〉!〈1〉!〈2〉!……〈n〉!
＝nk×(nk-1)!/〈0〉!〈1〉!〈2〉!……〈n〉!
※1×〈1〉＋2×〈2〉＋…＋n×〈n〉＝n なので
＝(nk)!/〈0〉!〈1〉!〈2〉!……〈n〉!
※nk×(nk-1)!＝(nk)! なので
よって、☆の両辺の係数が等しいと分かり、☆が真だと証明できました。
なので、
{0}×(nk-1)Ｄn＋(1-k){1}×(nk-1)Ｄ(n-1)＋……＋(1-sk){s}×(nk-1)Ｄ(n-s)
の数列の母関数が E(x)^0＝1 だと分かり、
{0}×(nk+a)Ｄn＋(1-k){1}×(nk+a)Ｄ(n-1)＋……＋(1-sk){s}×(nk+a)Ｄ(n-s)
の数列の母関数が
E(x)^(a+1)になること
が証明できました。
後半の証明が大変で、思いつくまで時間かかりましたが楽しかったです。
以上です。お読みいただきありがとうございました！
【追記】
e[n]＝(nk+1)Ｄn /(nk+1) でもある事に気付きました。
e[n]＝{0}×nkＤn＋(1-k){1}×nkＤ(n-1)＋(1-2k){2}×nkＤ(n-2)＋……＋(1-sk){s}×nkＤ(n-s)
よりもシンプルで良いです。
(nk+1)Ｄn /(nk+1)＝{0}×nkＤn＋(1-k){1}×nkＤ(n-1)＋(1-2k){2}×nkＤ(n-2)＋……＋(1-sk){s}×nkＤ(n-s) ・・・(＄)
を証明します。
{0}×nkＤn＋{1}×nkＤ(n-1)＋{2}×nkＤ(n-2)＋……＋{s}×nkＤ(n-s)＝(nk+1)Ｄn
なので、(＄)の右辺は
(nk+1)Ｄn－k( {1}×nkＤ(n-1)＋2{2}×nkＤ(n-2)＋……＋s{s}×nkＤ(n-s) )
です。
(＄)の両辺を移項して整理すると
n/(nk+1) × (nk+1)Ｄn＝ {1}×nkＤ(n-1)＋2{2}×nkＤ(n-2)＋……＋s{s}×nkＤ(n-s) ・・・＠
となります。
〔0〕,〔1〕, …… ,〔n〕を
〔0〕＋〔1〕＋……＋〔n〕＝nk+1
0×〔0〕＋1×〔1〕＋……＋n×〔n〕＝n
を満たすとします。
{0}^〔0〕×{1}^〔1〕×{2}^〔2〕×……×{n}^〔n〕 の係数が＠の両辺で等しいと示せば、
＠が真だと分かります。
※ (nk+1)Ｄnはd(x)^(nk+1) の x^n の係数なので、
{0},{1},……,{n}の次数の和(〔0〕＋〔1〕＋……＋〔n〕)は(nk+1) でなければならず、
{0},{1},……,{n}の次数にxの次数を掛けた数の和(0×〔0〕＋1×〔1〕＋……＋n×〔n〕)は、nでなければなりません。
＠の左辺 n/(nk+1) × (nk+1)Ｄn の{0}^〔0〕×{1}^〔1〕×{2}^〔2〕×……×{n}^〔n〕 の係数は、
多項定理より
n/(nk+1) ×(nk+1)!/〔0〕!〔1〕!〔2〕!……〔n〕!
＝n×(nk)!/〔0〕!〔1〕!〔2〕!……〔n〕!
です。
＠の右辺の{0}^〔0〕×{1}^〔1〕×{2}^〔2〕×……×{n}^〔n〕 の係数は、
(1×〔1〕＋2×〔2〕＋……＋n×〔n〕)×(nk)!/〔0〕!〔1〕!〔2〕!……〔n〕!
＝n×(nk)!/〔0〕!〔1〕!〔2〕!……〔n〕!
です。
よって＠の両辺が等しいと示せたので、
(nk+1)Ｄn /(nk+1)＝{0}×nkＤn＋(1-k){1}×nkＤ(n-1)＋(1-2k){2}×nkＤ(n-2)＋……＋(1-sk){s}×nkＤ(n-s) が示せ、
e[n]＝(nk+1)Ｄn /(nk+1) が証明できました。
