15/09/09 08:47:55.91 S3Yd5Wui.net
>>138
p組の夫婦が並んでいて、その内q組が隣り合っている状態を考える。
そこに新たな夫婦を追加するパターンは
(1)新たな夫婦が隣り合っている
(1-1)隣り合った夫婦の間に割り込む場合がq通り。隣り合う夫婦の数は変わらない。
(1-2)夫婦に割り込まない場合が2p+1-q通り。隣り合う夫婦の数は1増える。
(2)新たな夫婦が隣り合わない
(2-1)二組の夫婦に割り込む場合が、q(q-1)/2通り。隣り合う夫婦の数は2減る。
(2-2)一組の夫婦に割り込む場合が、q(2p+1-q)通り。隣り合う夫婦の数は1減る。
(2-3)夫婦の間に割り込まない場合が、(2p-q)(2p+1-q)/2通り。隣り合う夫婦の数は変わらない。
一応、これで漸化式が組めるはず。
とは言え、一般項どころか順次求めるのもすごく面倒そうだ。