数学の部屋へもどる
山梨県 Footmark さんからの問題です。
ｎ(≧１)人の集団があり、集団のどの人もその集団の何人でも殺すことができるとします。
（自殺することはないとします）
また、殺すときは必ず１人で殺します。
(残酷ですが、問題上の設定なのでお許しください。)
ｎ人を左から １,２,３,…,ｎ と番号を付けて、横１行に書きます。
その下の行に上の人を殺した殺人犯の番号を書きます。
ただし、殺されない人の下には◎を書くものとします。
このとき、下の行の順列を殺人犯順列と呼ぶものとします。
誰も殺されないときは、殺人犯順列は◎,◎,◎,…,◎の１通りですね。
以下の問いに答えてください。答えだけでなく考え方も示してください。
【問題１】
１人だけ生き残るときは、殺人犯順列は何通りあるでしょうか？
ｎを使って表してください。
【問題２】
ｋ人が殺されるときは、殺人犯順列は何通りあるでしょうか？
ｎとｋを使って表してください。
(ただし、少なくとも１人は生き残るので ０≦ｋ≦ｎー１ とします。)
【問題３】
考えられるすべての殺人犯順列は何通りあるでしょうか？
ｎを使って表してください。
【ＰＳ】
この問題は私の創作ですが、混乱順列(乱列)に真似て「殺人犯順列」と名付けました。(笑)
【ヒント】
出題から２週間過ぎても解答が皆無なのでヒントを出します。
必ずしも良いヒントになるかどうかは判りませんが、「私が一般解を得るまでの手順」に沿ったヒントです。
（直接的なヒントは敢えて控えましたが、あしからず。）
n(≧1)人集団内でk人が殺されるときの殺人犯順列の数を F(n,k)とすると、
[１] k＝0 のとき、F(n,0)=1
[２] k≧1 のとき、
F(n,k)=nＣk*[{F(k,0)*(n-k)k}+{F(k,1)*(n-k)k-1}+…+{F(k,k-1)*(n-k)1}]
が成立します。
[１]は、説明するまでもありませんね。
[２]は、まず、n人から殺されるk人を特定するのに nＣk通りです。
次に、(ここが漸化式発見の要ですが)特定したk人集団内での殺人を考えてみます。
すると、[0人殺されるとき]〜[(k-1)人殺されるとき] のｋ通りがある筈です。
その内の１つ、r(0≦r≦k-1)人が殺されるときの殺され方を考えると、
k人集団内でr人が殺されるときの殺人犯順列の数になり、F(k,r)通りあります。
その各々において、残った(k-r)人の殺され方は、いずれの人も(n-k)人の内の１人に殺されるので
(n-k)k-r通りです。
よって、n人集団内でk人が殺され、そのk人集団内でr人が殺されるときの殺人犯順列の数は、
nＣk*F(k,r)*(n-k)k-r通りです。
ここで、rは0,1,2,…,(k-1)のｋ通りがあるので[２]の漸化式が成立します。
kは 0≦k≦n-1 なので、[１],[２]が成立すると、1人集団〜(n-1)人集団のすべてのkにおける殺人犯順列の数が判れば、 n人集団のすべてのkにおける殺人犯順列の数もおのずと判ることになります。
よって、F(1,0)=1 から順次求めていけば、どんな F(n,k)も必ず求められる筈です。
とりあえず、6人集団くらいまでの F(n,k)を順次求めてみてください。
「F(n,k)の一般式らしきもの」が見えてくると思います。
（とは言っても、誰にでも必ず見えるという意味ではありません。）
ここまではそう難しくもないでしょうが、問題はここからです。
順次求めた F(n,k)に対して成立しても、任意の F(n,k)に対して成立する保証はないので、見えた「F(n,k)の一般式らしきもの」はあくまで予想式です。
ですから、この予想式が任意の F(n,k)に対して成立することを証明しなければなりません。
その証明こそがこの問題で一番大事なところなので、これ以上のヒントは控えます。
寄せられる解答を楽しみに待っています。
◆個数を数える問題へもどる
数学の部屋へもどる