第３５３問の解答

問題［場合の数］

問題図

 トモエさん、マサルさん、ツヨシ君、マサヒコ君、サトルさん、ヤオミン君の６人の身長はそれぞれ１２０cm、１４０cm、１６０cm、１８０cm、２００cm、２２０cmです。

この６人が縦に１列に並ぶとき、背の低い順に並べば全員が前方を見ることが出来ますが、 左図のような並び方をすると、ツヨシ君、マサヒコ君、サトルさん、ヤオミン君の４人は前方を見ることができますが、トモエさん、マサルさんは前の人の背中しか見えません。

では、この６人の並び方で、「４人だけが前方を見ることができる」ような並び方は何通りあるでしょうか。

解答例１

まるケンさん、takaisaさん、ponta55555さん、中村明海さん、 他

６人に対して、背の低い順に番号をつけます。

まず、６人全員が見えるのは、６人が背の低い順に並ぶ１通りだけです。

次に、５人が見える（１人だけが見えない）場合を考えてみましょう。
見えない１人を選ぶのは、１番背の高い６番を除く、１〜５番の５通りあります。
見えない人の番号で場合分けして数えます。

  • 見えないのが１番の人のとき：この人は１番低いので、２〜６番のどの人の後ろに来ても見えない・・・５通り

  • 見えないのが２番の人のとき：この人より高い３〜６番の後ろに来ると見えない・・・４通り

  • 見えないのが３番の人のとき：この人より高い４〜６番の後ろに来ると見えない・・・３通り

  • 見えないのが４番の人のとき：この人より高い５〜６番の後ろに来ると見えない・・・２通り

  • 見えないのが５番の人のとき：この人より高い６番の後ろに来ると見えない・・・１通り

参考図１

では、いよいよ４人が見える（２人が見えない）場合を考えてみましょう。
見えない２人を選ぶのは、１番背の高い６番を除く５人から２人を選ぶ5C2＝１０通りあります。
見えない人の番号で場合分けして数えます。

  • 見えないのが１番、２番のとき：
    まず大きい２番の人は３〜６番の後ろに来る場合・・・４通り
    １番    の人は、２番の人の場所にかかわらず残り５人いずれかの後ろへ来る・・・５通り
    　

  • 見えないのが１番、３番のとき：
    まず大きい３番の人は４〜６番の後ろに来る場合・・・３通り
    １番    の人は、３番の人の場所にかかわらず残り５人いずれかの後ろへ来る・・・５通り
    　

  • 見えないのが１番、４番のとき：
    まず大きい３番の人は５〜６番の後ろに来る場合・・・２通り
    １番    の人は、４番の人の場所にかかわらず残り５人いずれかの後ろへ来る・・・５通り
    　

  • 見えないのが１番、５番のとき：
    まず大きい５番の人は６番の後ろに来る場合・・・１通り
    １番    の人は、５番の人の場所にかかわらず残り５人いずれかの後ろへ来る・・・５通り

参考図２

以下、同様にして、
　合計＝（４＋３＋２＋１）×５＋（３＋２＋１）×４＋（２＋１）×３＋１×２＝８５通りと求まります。

なお、同じ考え方でn人いて、そのうちk人が見える場合をS（n、k）とすると、
　S（n、k）は、（n-1）以下の整数より(n-k)個選んで掛け合わせたものの和
となることが分かります。

従って、ｆ（ｘ）＝（ｘ＋１）（ｘ＋２）・・・（ｘ＋n-１）とすると、
　S（n、k）は、ｆ（ｘ）のｘk-1の係数と考えることもできます。

本問はS（６、４）を求めることになり、数式処理ソフトを使って展開すると、
　ｆ（ｘ）＝（ｘ＋１）（ｘ＋２）（ｘ＋３）（ｘ＋４）（ｘ＋５）
　　　　＝ｘ5＋１５ｘ4＋８５ｘ3＋２２５ｘ2＋２７４ｘ＋１２０
のｘ3の係数８５と求まります。

（参考）第１種スターリング数
　ｓ(n、k)＝ｘ(x−１）（ｘ−２）・・・（ｘ−(n-１)）のｘkの係数
　従って、今回のS（n、k）は第１種スターリング数の絶対値となり、
　符号無し第１種スターリング数とも呼ばれているようです。

答：　８５通り

以上

解答例２

Toru Fukatsuさん、清川　育男さん、ミミズクはくず耳さん、 他

解答例１と同じく、n人いて、そのうちk人が見える場合をS（n、k）として、
　S（n＋１、k）に対する漸化式求めます。

参考図３

ｎ人が並んでいる後に１番小さい人を並べるものと考えます。

  • ｎ人中（ｋ−１）人が見えていたとき：
    後の人は見える位置、すなわち１番前に並ぶ必要がある・・・Ｓ（ｎ、ｋ−１）通り
    　

  • ｎ人中ｋ人が見えていたとき：
    後の人は見えない位置、すなわちｎ人の人のいずれかの後ろに並ぶ必要がある
    　・・・Ｓ（ｎ、ｋ）×ｎ通り

従って、
　S（n＋１、k）＝Ｓ（ｎ、ｋ−１）＋Ｓ（ｎ、ｋ）×ｎ
を得ます。

S（ｎ、０）＝０、S（１、１）＝１から順次求めると、下表のようになり、S（６、４）＝８５と求まります。

参考図４

（補足）
　S（ｎ、ｎ）＝１
　S（ｎ、ｎ−１）＝Σj(j=1〜n-1)＝n(n-1)/2（ｎ≧2）
　S（ｎ、ｎ−２）＝Σj×k(j,k=1〜n-1,j>k)＝n(n-1)(n-2)(3n-1)/24（n≧3）
および
　S（ｎ、１）＝（n-1）! 
が成り立ちます。

（その他の解法）