[答470] ルークの移動

[答470] ルークの移動


　チェスのルーク(rook)は、将棋の飛車のように、1手(1回の移動)で、縦横に何マスでも動けます。

　いま、図のように A1 の位置にある rook を 右か上だけに動かして H8 に移動する方法は何通り？

　( A1 から H8 へは、最少で 2手、最多で 14手 かけて移動することにになります。)


[解答1]

　B1，C1，D1，E1，F1，G1，H1 への移動は途中の各マスで止まるか止まらないかの２通りですので、

　移動の仕方は 1，2，4，8，16，32，64 通り、A2 ～ A8 への移動も同じで、この数を書き込みます。

　B2 への移動は B1，A2 からの移動だから、この数を加えて書き込みます。

　C2 への移動は C1，A2，B2 からの移動だから、この数を加えて書き込みます。

　D2 への移動は D1，A2，B2，C2 からの移動だから、この数を加えて書き込みます。

　同様にして、E2，F2，G2，H2 に何通りかを書き込み、B3 ～ B8 への移動も同じで、この数を書き込みます。

　以下、同様に、

　C3 ～ H3 ，C4 ～ C8 ，D4 ～ H4 ，D5 ～ D8 ，E5 ～ H5 ，E6 ～ E8 ，F6 ～ H6 ，F7 ～ F8 ，……

　と、H8 まで書き込めば、動かす方法は 470010 通りであることが分かります。


[解答2]

　まず、途中で止まる行を 2，3，4，5，6，7 から m個、途中で止まる列を B，C，D，E，F，G から n個

　を選び、上へ m＋1 回，右へ n＋1 回の移動で、H8 に達することになります。

　従って、₆Ｃ_m･₆Ｃ_n･_m+n+2Ｃ_m+1 (0≦m≦6，0≦n≦6) の総和を求めることになります。

　_m+n+2Ｃ_m+1 は、選んだ m＋n 個と x，y を付加したものから m＋1 個を選ぶ場合の数です。

　例えば、2，3，4，5，B，C，D，x，y からは５個を選ぶことになりますが、

　(1) 2，3，4，5，6，7 から (3，4)、 B，C，D，E，F，G から (B，D) のように同数個を選んで

　 　残り 2，5，6，7，C，E，F，G から 2，5，C を選ぶと、2，3，4，5，B，C，D を選んだことになり、

　 　行は 3，4 以外を、列は B，D を 書き出せば、2，5，B，D 、これに x，y のうちどちらかを加えれば、

　 　x，y のうち１つだけを含む５個の選び方になります。

　(2) 2，3，4，5，6，7 から (3，4)、 B，C，D，E，F，G から (D) のように行を１個多く選んで

　 　残り 2，5，6，7，B，C，E，F，G から 2，5，B，C を選ぶと、2，3，4，5，B，C，D を選んだことになり、

　 　行は 3，4 以外を、列は D を 書き出せば、2，5，D 、これに x，y の両方を加えれば、

　 　x，y の両方を含む５個の選び方になります。

　(3) 2，3，4，5，6，7 から (4)、 B，C，D，E，F，G から (B，D) のように列を１個多く選んで

　 　残り 2，3，5，6，7，C，E，F，G から 2，3，5，C を選ぶと、2，3，4，5，B，C，D を選んだことになり、

　 　行は 4 以外を、列は B，D を 書き出せば、2，3，5，B，D 、

　 　これは、x，y のどちらも含まない５個の選び方になります。

　(1)のように行と列から同数個選び、残りから任意に選ぶような選び方は、₆Ｃ_k･₆Ｃ_k･2^12-2k (0≦k≦6) 通りで、

　 (2x＋1)⁶ の展開式における x^6-k の係数は ₆Ｃ_k･2^6-k 、(2＋x)⁶ の展開式における x^k の係数は ₆Ｃ_k･2^6-k 、

　 よって、 {(2x＋1)(2＋x)}⁶ の展開式における x⁶ の係数になります。

　(2)のように行を１個多く選び、残りから任意に選ぶような選び方は、₆Ｃ_k+1･₆Ｃ_k･2^11-2k (0≦k≦5) 通りで、

　 (2x＋1)⁶ の展開式における x^5-k の係数は ₆Ｃ_k+1･2^5-k 、(2＋x)⁶ の展開式における x^k の係数は ₆Ｃ_k･2^6-k 、

　 よって、 {(2x＋1)(2＋x)}⁶ の展開式における x⁵ の係数になります。

　(3)のように列を１個多く選び、残りから任意に選ぶような選び方は、₆Ｃ_k+1･₆Ｃ_k･2^11-2k (0≦k≦5) 通りで、

　 (2)と同数です。

　従って、(2x²＋5x＋2)⁶ の展開式における x⁶ の係数と x⁵ の係数の和の２倍が答です。

　展開したときの一般項は {6!/(a!b!c!)}･(2x²)^a(5x)^b･2^c (a＋b＋c＝6) だから、

　x の指数は 2a＋b＝5，6 で、係数は {6!/(a!b!c!)}･2^a･5^b･2^c 、

　(a，b，c)＝(0，5，1)，(1，3，2)，(2，1，3)，(0，6，0)，(1，4，1)，(2，2，2)，(3，0，3) 、

　{6!/(a!b!c!)}･2^a･5^b･2^c＝37500，60000，9600，15625，75000，36000，1280 となり、

　その和の２倍は 2(37500＋60000＋9600＋15625＋75000＋36000＋1280)＝470010 です。


[参考]

　f(x)＝(2x²＋5x＋2)ⁿ の xⁿ⁺¹，x^n-1 の係数を b_n ，xⁿ の係数を a_n－b_n とします。

　f(x) の xⁿ⁺¹ の係数は b_n ，xⁿ の係数は a_n－b_n で、

　f'(x) の xⁿ の係数は (n＋1)b_n ，x^n-1 の係数は n(a_n－b_n) です。

　また、f'(x)＝n(2x²＋5x＋2)^n-1(4x＋5) で、

　(2x²＋5x＋2)^n-1 の xⁿ，x^n-2 の係数は b_n-1 ，x^n-1 の係数は a_n-1－b_n-1 だから、

　xⁿ の係数は n{4(a_n-1－b_n-1)＋5b_n-1} ，x^n-1 の係数は n{4b_n-1＋5(a_n-1－b_n-1)} です。

　よって、(n＋1)b_n＝n(4a_n-1＋b_n-1) ……(1) 、n(a_n－b_n)＝n(5a_n-1－b_n-1) ……(2) 、

　(2)より、a_n－5a_n-1＝b_n－b_n-1 、

　(1)＋(2) より、na_n＋b_n＝9na_n-1 従って、(n－1)a_n-1＋b_n-1＝9(n－1)a_n-2 、

　辺々減じて、na_n－(n－1)a_n-1＋(a_n－5a_n-1)＝9na_n-1－9(n－1)a_n-2 、

　a_n＝{(10n＋4)a_n-1－9(n－1)a_n-2}/(n＋1) になります。

　n×n の盤の左下隅から右上隅への移動の仕方を R_n 通りとすれば、R_n＝2a_n-2 になります。

　R₂＝2a₀＝2 ，R_n+2＝2a_n＝2{(10n＋4)a_n-1－9(n－1)a_n-2}/(n＋1)＝{(10n＋4)R_n+1－9(n－1)R_n}/(n＋1) 、

　この漸化式で順に計算すると、

　R₃＝14R₂/2＝14 ，R₄＝(24R₃－9R₂)/3＝106 ，R₅＝(34R₄－18R₃)/4＝838 ，R₆＝(44R₅－27R₄)/5＝6802 ，

　R₇＝(54R₆－36R₅)/6＝56190 ，R₈＝(64R₇－45R₆)/7＝470010 が答になります。

.