問題5268・・・やどかりさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/31063904.html より Orz〜
チェスのルーク(rook)は、将棋の飛車のように、1手(1回の移動)で、縦横に何マスでも動けます。
いま、図のように A1 の位置にある rook を 右か上だけに動かして H8 に移動する方法は何通り
( A1 から H8 へは、最少で 2手、最多で 14手 かけて移動することにになります。)
解答
[解答1]
B1,C1,D1,E1,F1,G1,H1 への移動は途中の各マスで止まるか止まらないかの2通りですので、 移動の仕方は 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 に達することになります。
従って、6Cm・6Cn・m+n+2Cm+1 (0≦m≦6,0≦n≦6) の総和を求めることになります。
m+n+2Cm+1 は、選んだ m+n 個と x,y を付加したものから m+1 個を選ぶ場合の数です。
例えば、2,3,4,5,B,C,D,x,y からは5個を選ぶことになりますが、
(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 のうち1つだけを含む5個の選び方になります。
(2) 2,3,4,5,6,7 から (3,4)、 B,C,D,E,F,G から (D) のように行を1個多く選んで 残り 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 の両方を含む5個の選び方になります。
(3) 2,3,4,5,6,7 から (4)、 B,C,D,E,F,G から (B,D) のように列を1個多く選んで 残り 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 のどちらも含まない5個の選び方になります。
(1)のように行と列から同数個選び、残りから任意に選ぶような選び方は、6Ck・6Ck・212-2k (0≦k≦6) 通りで、 (2x+1)6 の展開式における x6-k の係数は 6Ck・26-k 、(2+x)6 の展開式における xk の係数は 6Ck・26-k 、 よって、 {(2x+1)(2+x)}6 の展開式における x6 の係数になります。
(2)のように行を1個多く選び、残りから任意に選ぶような選び方は、6Ck+1・6Ck・211-2k (0≦k≦5) 通りで、 (2x+1)6 の展開式における x5-k の係数は 6Ck+1・25-k 、(2+x)6 の展開式における xk の係数は 6Ck・26-k 、 よって、 {(2x+1)(2+x)}6 の展開式における x5 の係数になります。
(3)のように列を1個多く選び、残りから任意に選ぶような選び方は、6Ck+1・6Ck・211-2k (0≦k≦5) 通りで、 (2)と同数です。
従って、(2x2+5x+2)6 の展開式における x6 の係数と x5 の係数の和の2倍が答です。
展開したときの一般項は {6!/(a!b!c!)}・(2x2)a(5x)b・2c (a+b+c=6) だから、 x の指数は 2a+b=5,6 で、係数は {6!/(a!b!c!)}・2a・5b・2c 、 (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!)}・2a・5b・2c=37500,60000,9600,15625,75000,36000,1280 となり、 その和の2倍は 2(37500+60000+9600+15625+75000+36000+1280)=470010 です。
[参考]
f(x)=(2x2+5x+2)n の xn+1,xn-1 の係数を bn ,xn の係数を an−bn とします。
f(x) の xn+1 の係数は bn ,xn の係数は an−bn で、 f'(x) の xn の係数は (n+1)bn ,xn-1 の係数は n(an−bn) です。
また、f'(x)=n(2x2+5x+2)n-1(4x+5) で、 (2x2+5x+2)n-1 の xn,xn-2 の係数は bn-1 ,xn-1 の係数は an-1−bn-1 だから、 xn の係数は n{4(an-1−bn-1)+5bn-1} ,xn-1 の係数は n{4bn-1+5(an-1−bn-1)} です。
よって、(n+1)bn=n(4an-1+bn-1) ……(1) 、n(an−bn)=n(5an-1−bn-1) ……(2) 、 (2)より、an−5an-1=bn−bn-1 、 (1)+(2) より、nan+bn=9nan-1 従って、(n−1)an-1+bn-1=9(n−1)an-2 、 辺々減じて、nan−(n−1)an-1+(an−5an-1)=9nan-1−9(n−1)an-2 、 an={(10n+4)an-1−9(n−1)an-2}/(n+1) になります。
n×n の盤の左下隅から右上隅への移動の仕方を Rn 通りとすれば、Rn=2an-2 になります。 R2=2a0=2 ,Rn+2=2an=2{(10n+4)an-1−9(n−1)an-2}/(n+1)={(10n+4)Rn+1−9(n−1)Rn}/(n+1) 、
この漸化式で順に計算すると、 R3=14R2/2=14 ,R4=(24R3−9R2)/3=106 ,R5=(34R4−18R3)/4=838 ,R6=(44R5−27R4)/5=6802 , R7=(54R6−36R5)/6=56190 ,R8=(64R7−45R6)/7=470010 が答になります。
*わたしゃ...地道に解法1しかわからず...^^;
|