『殺人犯順列』


山梨県 Footmark さんからの問題です。

n(≧1)人の集団があり、集団のどの人もその集団の何人でも殺すことができるとします。
(自殺することはないとします)

また、殺すときは必ず1人で殺します。
(残酷ですが、問題上の設定なのでお許しください。)

n人を左から 1,2,3,…,n と番号を付けて、横1行に書きます。
その下の行に上の人を殺した殺人犯の番号を書きます。
ただし、殺されない人の下には◎を書くものとします。

このとき、下の行の順列を殺人犯順列と呼ぶものとします。

誰も殺されないときは、殺人犯順列は◎,◎,◎,…,◎の1通りですね。

以下の問いに答えてください。答えだけでなく考え方も示してください。

【問題1】

1人だけ生き残るときは、殺人犯順列は何通りあるでしょうか?
nを使って表してください。

【問題2】

k人が殺されるときは、殺人犯順列は何通りあるでしょうか?
nとkを使って表してください。
(ただし、少なくとも1人は生き残るので 0≦k≦nー1 とします。)

【問題3】

考えられるすべての殺人犯順列は何通りあるでしょうか?
nを使って表してください。

【PS】

この問題は私の創作ですが、混乱順列(乱列)に真似て「殺人犯順列」と名付けました。(笑)


【ヒント】

出題から2週間過ぎても解答が皆無なのでヒントを出します。

必ずしも良いヒントになるかどうかは判りませんが、「私が一般解を得るまでの手順」に沿ったヒントです。
(直接的なヒントは敢えて控えましたが、あしからず。)

n(≧1)人集団内でk人が殺されるときの殺人犯順列の数を F(n,k)とすると、

[1] k=0 のとき、F(n,0)=1
[2] k≧1 のとき、
F(n,k)=nk*[{F(k,0)*(n-k)k}+{F(k,1)*(n-k)k-1}+…+{F(k,k-1)*(n-k)1}]

が成立します。

[1]は、説明するまでもありませんね。

[2]は、まず、n人から殺されるk人を特定するのに nk通りです。
次に、(ここが漸化式発見の要ですが)特定したk人集団内での殺人を考えてみます。
すると、[0人殺されるとき]〜[(k-1)人殺されるとき] のk通りがある筈です。

その内の1つ、r(0≦r≦k-1)人が殺されるときの殺され方を考えると、
k人集団内でr人が殺されるときの殺人犯順列の数になり、F(k,r)通りあります。

その各々において、残った(k-r)人の殺され方は、いずれの人も(n-k)人の内の1人に殺されるので
(n-k)k-r通りです。

よって、n人集団内でk人が殺され、そのk人集団内でr人が殺されるときの殺人犯順列の数は、
nk*F(k,r)*(n-k)k-r通りです。

ここで、rは0,1,2,…,(k-1)のk通りがあるので[2]の漸化式が成立します。

kは 0≦k≦n-1 なので、[1],[2]が成立すると、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)に対して成立することを証明しなければなりません。

その証明こそがこの問題で一番大事なところなので、これ以上のヒントは控えます。
寄せられる解答を楽しみに待っています。


解答用紙はこちらです。 【寄せられた解答】


 ◆個数を数える問題へもどる

 数学の部屋へもどる