 pc ( No.11 ) |
- 日時： 2013/08/13 01:08
- 名前： Nighteck
- わかったと言って暗号のような文を載せておいて説明なしでは無責任だと思うので(笑)、
一応、解説を載せておきます
cの式の解説をする前に、割る回数(すなわちa、b)について述べておきます
実は、割る回数はどのような折り方をしても一定で、その回数はxy-1となります
どのように割っても、一回割るごとにかたまりは一つずつ増えます
最終的にピースの数（xy個）だけ増やせばいいから、
最初の1個の状態から、xy個まで、xy-1回増やせばいいので、割る回数はxy-1です
cの説明には、これがわかっていることが前提です
続いてcについてです
まず、チョコ板の2つのかたまりがある場合の割り方の総数を考えます
それぞれのチョコ板の割り方に加え、2つのかたまりを割っていく順序も考慮する必要があります
片方のチョコ板を縦x1ピース・横y1ピース、その割り方の総数をa1通り
もう片方チョコ板を縦x2ピース・横y2ピース、その割り方の総数をa2通りとすると、
片方のチョコ板の割る回数はx1y1-1回、
もう片方チョコ板の割る回数はx2y2-1回となります
両方のチョコ板の割り方の総数はa1×a2通り
片方をx1y1-1回、もう片方をx2y2-1回、両方とも合わせて好きな順番で割る方法は(x1y1-1+x2y2-1)!/(x1y1-1)!(x2y2-1)!通り （同じものを含む順列の考え方）
すなわち、2つのチョコ板の割り方の総数は
a1×a2×(x1y1-1+x2y2-1)!/(x1y1-1)!(x2y2-1)!
=a1a2(x1y1-x2y2-2)!/(x1y1-1)!(x2y2-1)!・・・①通りとなります
そこで、1回目の割りで分かれた2つのかたまりについて、この考え方を使います
これ以降、cを求めるチョコ板を縦xピース・横yピースとし、そのcの値をcx,yとします
1回目の割りでは、横に割るのがx-1通り、縦に割るのがy-1通りあります
そのすべてのパターンに対して使い、それを合計すれば、cx,yが求められます
横に割るパターンが 縦1・横yと縦x-1・横y、縦2・横yと縦x-2・横y、・・・縦x-1・横yと縦1・横y
縦に割るパターンが 縦x・横1と縦x・横y-1、縦x・横2と縦x・横y-2、・・・縦x・横y-1と縦x・横1
①に、a1=c赤,青、a2=c緑,紫、x1=赤、y1=青、x2=緑、y2=紫としてそれぞれ代入し、合計を求めます（横に割るパターンと縦に割るパターンもたします）
Σを使って表現すると
cx,y=Σ(k=1,x-1) {ck,ycx-k,y(yk+y(x-k)-2)!}/{(yk-1)!(y(x-k)-1)!} +
Σ(k=1,y-1) {ck,xcy-k,x(xk+x(y-k)-2)!}/{(xk-1)!(x(y-k)-1)!}
一行目が横に割るパターンの合計、二行目が縦に割るパターンの合計です
ただし、これだとxやyが1のときにΣの範囲がおかしくなってしまいます
なのでxやyが1になるときのみ場合分けを行うと、No.10のスレのようになります
以上です
あくまで漸化式なので、小さい数から順番に求める必要があります
c1,k=(k-1)!は考えればすぐわかるし、c2,2=4は数えればすぐわかります
これらを使えば、式によりc2,3が求まり
c2,3からc2,4、c3,3が求まります
さらにc2,3、c2,4、c3,3からc3,4が求まる・・・というように、小さい数から順に求めていけばあらゆるcの値を求めていくことができます
>>12
確かにそうですね。
cx,y→Ax,yと書き直すと
Σ(k=1,x-1) {ck,ycx-k,y(yk+y(x-k)-2)!}/{(yk-1)!(y(x-k)-1)!}
→Σ(k=1,x-1) {Ak,yAx-k,y yk+y(x-k)-2Cyk-1}
Σ(k=1,y-1) {ck,xcy-k,x(xk+x(y-k)-2)!}/{(xk-1)!(x(y-k)-1)!}
→Σ(k=1,y-1) {Ak,xAy-k,x xk+x(y-k)-2Cxk-1}
となり、もっと簡潔に表せますね
|
|
FAQ
RSS