平成２８年１０月２日

[流れ星]

　　　　　第338回数学的な応募解答

　　　　　　＜解答募集期間：９月４日〜10月２日＞

［同タイムの順位］

リオデジャネイロ五輪水泳競技で同タイムが3人いて、2位の銀メダル3個という現象がおきました。陸上や水泳競技において１レース８人で争うことがあります。

ここで、同タイムも起こり得ると考えて、次のような作問をしました。例えば、３人の場合順位の起こり方は、（１、１、１）、（１、１、３）、（１、２、２）、（１、２、３）の４通りあります。

問１：　８人でタイムを争うとき、順位の起こり方は何通りあるか。

問２：　一般にｎ人で争うとき（マラソンみたいに大勢で）、順位の起こり方は何通りあるか。

さらに、人を区別したとき、例えば（A、B）の２人の場合は、順に（１、１）、（１、２）、（２、１）の３通りあります。以下、人を区別して順位の起こり方を考えます。

問３：　（A,B,C）の３人のとき、順位の起こり方は何通りあるか。

問４：（A,B,C、D）の４人のとき、順位の起こり方は何通りあるか。

問５：（A,B,C、・・・・）のｎ人のとき、順位の起こり方は何通りあるか考察せよ。

No1「uchinyan」 09/04 17時15分　受信 更新

「uchinyan」 09/07 14時22分　受信 更新 10/02

問１：

まず４人の場合を考えてみましょう。

３人の場合は，例にあるように，(1,1,1)，(1,1,3)，(1,2,2)，(1,2,3)，ですが，

これに１人加わると４人目は３人の場合を崩さずに付け加えると考えて，

(1,1,1) のとき，１位か４位しかないので，(1,1,1,1) 又は (1,1,1,4) の 2 通り，

(1,1,3) のとき，３位か４位しかないので，(1,1,3,3) 又は (1,1,3,4) の 2 通り，

(1,2,2) のとき，２位か４位しかないので，(1,2,2,2) 又は (1,2,2,4) の 2 通り，

(1,2,3) のとき，３位か４位しかないので，(1,2,3,3) 又は (1,2,3,4) の 2 通り，

これですべてなので 4 * 2 = 8 通りです。

５人の場合も同様で，次のとおり。

(1,1,1,1) のとき，１位か５位しかないので，(1,1,1,1,1) 又は (1,1,1,1,5) の 2 通り，

(1,1,1,4) のとき，４位か５位しかないので，(1,1,1,4,4) 又は (1,1,1,4,5) の 2 通り，

(1,1,3,3) のとき，３位か５位しかないので，(1,1,3,3,3) 又は (1,1,3,3,5) の 2 通り，

(1,1,3,4) のとき，４位か５位しかないので，(1,1,3,4,4) 又は (1,1,3,4,5) の 2 通り，

(1,2,2,2) のとき，２位か５位しかないので，(1,2,2,2,2) 又は (1,2,2,2,5) の 2 通り，

(1,2,2,4) のとき，４位か５位しかないので，(1,2,2,4,4) 又は (1,2,2,4,5) の 2 通り，

(1,2,3,3) のとき，３位か５位しかないので，(1,2,3,3,3) 又は (1,2,3,3,5) の 2 通り，

(1,2,3,4) のとき，４位か５位しかないので，(1,2,3,4,4) 又は (1,2,3,4,5) の 2 通り，

結局，４人の場合の各パターンの最下位の順位か５位の 2 通りずつなので，8 * 2 = 16 通り，

以下同様にして，

６人の場合は 16 * 2 = 32 通り，７人の場合は 32 * 2 = 64 通り，８人の場合は 64 * 2 = 128 通り，

になります。

問２：

問１：より明らかですが．．．

n 人の場合は，n-1 人の場合の各パターンの最下位の順位かｎ位の 2 通りずつなので，

起こり得るパターンは n-1 人の場合の 2 倍です。

このことと問１：の結果から，数学的帰納法で，2^(n-1) 通り，になります。

問３：

人を区別しない場合の各パターンに関して，

(1,1,1) のとき，(1,1,1) の 1 通り，

(1,1,3) のとき，(1,1,3), (1,3,1), (3,1,1) の 3 通り，

(1,2,2) のとき，(1,2,2), (2,1,2), (2,2,1) の 3 通り，

(1,2,3) のとき，(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) の 6 通り，

これですべてなので，1 + 3 + 3 + 6 = 13 通り，になります。

問４：

問１：の最初より４人の人を区別しない場合のパターンは分かっているので，それに対して，

(1,1,1,1) のとき，1 通り，

(1,1,1,4), (1,2,2,2) のとき，4 通りずつの 4 * 2 = 8 通り，

(1,1,3,3) のとき，4C2 = 6 通り，

(1,1,3,4), (1,2,2,4), (1,2,3,3) のとき，4!/2!1!1! = 12 通りずつの 12 * 3 = 36 通り，

(1,2,3,4) のとき，4! = 24 通り，

これですべてなので，1 + 8 + 6 + 36 + 24 = 75 通り，になります。

問５：

問２：の途中の結果を基に５人の場合を計算してみると，

(1,1,1,1,1) のとき，1 通り，

(1,1,1,1,5), (1,2,2,2,2) のとき，5C1 = 5 通りずつの 5 * 2 = 10 通り，

(1,1,1,4,4), (1,1,3,3,3) のとき，5C2 = 10 通りずつの 10 * 2 = 20 通り，

(1,1,1,4,5), (1,2,2,2,5), (1,2,3,3,3) のとき，5!/3!1!1! = 20 通りずつの 20 * 3 = 60 通り，

(1,1,3,3,5), (1,1,3,4,4), (1,2,2,4,4) のとき，5!/2!2!1! = 30 通りずつの 30 * 3 = 90 通り，

(1,1,3,4,5), (1,2,2,4,5), (1,2,3,3,5),(1,2,3,4,4) のとき，5!/2!1!1!1! = 60 通りずつの 60 * 4 = 240 通り，

(1,2,3,4,5) のとき，5! = 120 通り，

これですべてなので，1 + 10 + 20 + 60 + 90 + 240 + 120 = 541 通り，になります。

この方法をさらに続けることも可能ですが，

規則性が見えてこないので，方針を変えて漸化式を試みてみます。

n 人の場合を f(n) 通りとします。

順位の最下位が k 位のときは，k 位より上位の人は k-1 人いますが，

これらの人を選ぶのに nC(k-1) 通りで，残りの人はすべて k 位になります。

そして，k 位より上位の人の順位の場合の数は f(k-1) 通りです。

そこで，

f(n) = Σ[k=1,n]{nC(k-1) * f(k-1)}，

となります。ただし，明らかに，f(1) = 1，なので，f(0) = 1，とします。

この漸化式で計算すると，

１人の場合，

f(1) = nC0 * f(0) = 1 * 1 = 1 通り，

２人の場合，

f(2) = 2C0 * f(0) + 2C1 * f(1) = 1 * 1 + 2 * 1 = 1 + 2 = 3 通り，

３人の場合，

f(3) = 3C0 * f(0) + 3C1 * f(1) + 3C2 * f(2)

= 1 * 1 + 3 * 1 + 3 * 3 = 1 + 3 + 9 = 13 通り，

４人の場合，

f(4) = 4C0 * f(0) + 4C1 * f(1) + 4C2 * f(2) + 4C3 * f(3)

= 1 * 1 + 4 * 1 + 6 * 3 + 4 * 13 = 1 + 4 + 18 + 52 = 75 通り，

５人の場合，

f(5) = 5C0 * f(0) + 5C1 * f(1) + 5C2 * f(2) + 5C3 * f(3) + 5C4 * f(4)

= 1 * 1 + 5 * 1 + 10 * 3 + 10 * 13 + 5 * 75 = 1 + 5 + 30 + 130 + 375 = 541 通り，

．．．

少しは計算が楽になりました。

ただ，残念ながら，この漸化式を解いて f(n) を n の式で書き下せるかまでは分かっていません。

なお，人を区別しない問２：の場合には nC(k-1) が不要なので，

f(n) = Σ[k=1,n]{f(k-1)} = Σ[k=1,n-1]{f(k-1)} + f(n-1) = ，f(n-1) + f(n-1) = 2 * f(n-1)，

f(1) = 1 なので，f(n) = 2^(n-1) 通り，となって，問２：の結果を再現します。

(別解)

上記までの解答を水の流れさんに送ったのですが，正解ではあったものの，

詰め切れなかった部分などの新たな解法のアイディアを頂きました。

それは，同順位の人が手をつなぐ，というものです。

手をつないでゴールする，とイメージするといいでしょう。

実はこの方法は私も一度は考えたのですが，

ちょっとした考え違いからうまくいかないと思ってしまったものでした。

これをヒントに改めて考え直して，等価ですが若干着目点が違う解法を思い付きました。

それは，同順位の人数に注目する，というアプローチです。

＜お詫び水の流れから：以下10月2日午後7時半頃　追加しました。全く私の過失です。申し訳ありませんでした＞

一般に n 人の場合で考えます。

１位の人は必ずいるのでこれを p 人とします。

すると次は p+1 位ですがこれが q 人，次は p+q+1 位が r 人，…，とします。

このとき，n = p + q + r + …，がいえています。

逆に，n をそれ自身又はいくつかの 1 以上の整数の和，n = p + q + r + …，として，

n 自身は，１位が n 人，

n = p + q + r + …，は，１位の人が p 人，p+1 位が q 人，p+q+1 位が r 人，…，

と考えれば，順位のパターンが一意に決まります。

つまり，順位のパターンと n のそれ自身を含む 1 以上の整数の和への分解が１対１に対応しています。

さらに，この和への分解は，

n に対して，1 1 1 …n 個… 1 1 1 を考え，いくつかの 1 と 1 の間に + を挟み込み，

+ を入れずに隙間のままの 1 の集まりを足して整数にすれば，和への分解と１対１に対応します。

そこで，和への分解は，1 と 1 の間が n-1 箇所あるので 2^(n-1) 通りです。

これより，順位のパターンも 2^(n-1) 通りあることになります。

人を区別しない場合は，このパターンそのものなので，2^(n-1) 通り，になります。

人を区別する場合は，各パターンに人を割り当てる，並べる，順列になるので，

Σ[n=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/(p!q!r!…)} 通り，

になります。

少し例を示しましょう。

３人の場合

3

= 1 1 1 = 3，１位が３人，

= 1 + (1 1) = 1 + 2，１位が１人，２位が２人，

= (1 1) + 1 = 2 + 1，１位が２人，３位が１人，

= 1 + 1 + 1 = ，１位が１人，２位が２人，３位が１人，

人を区別しない場合，2^2 = 4 通り，

人を区別する場合，3!/3! + 3!/1!2! + 3!/2!1! + 3!/1!1!1! = 1 + 3 + 3 + 6 = 13 通り，

になります。

４人の場合

4

= 1 1 1 1 = 4，１位が４人，

= 1 + (1 1 1) = 1 + 3，１位が１人，２位が３人，

= (1 1) + (1 1) = 2 + 2，１位が２人，３位が２人，

= (1 1 1) + 1 = 3 + 1，１位が３人，４位が１人，

= 1 + 1 + (1 1) = 1 + 1 + 2，１位が１人，２位が１人，３位が２人，

= 1 + (1 1) + 1 = 1 + 2 + 1，１位が１人，２位が２人，４位が１人，

= (1 1) + 1 + 1 = 2 + 1 + 1，１位が２人，３位が１人，４位が１人，

= 1 + 1 + 1 + 1，１位が１人，２位が１人，３位が１人，４位が１人，

人を区別しない場合，2^3 = 8 通り，

人を区別する場合，

4!/4! + 4!/1!3! + 4!/2!2! + 4!/3!1! + 4!/1!1!2! + 4!/1!2!1! + 4!/2!1!1! + 4!/1!1!1!1!

= 1 + 4 + 6 + 4 + 12 + 12 + 12 + 24 = 75 通り，

になります。

５人の場合

少し省略しそれに合わせて分解の順番を少し変えます。

5

= 5，

= 4 + 1 = 1 + 4，

= 3 + 2 = 2 + 3，

= 3 + 1 + 1 = 1 + 3 + 1 = 1 + 1 + 3，

= 2 + 2 + 1 = 2 + 1 + 2 = 1 + 2 + 2，

= 2 + 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 1 + 1 + 1 + 2，

= 1 + 1 + 1 + 1 + 1，

人を区別しない場合，2^4 = 16 通り，

人を区別する場合，

5!/5! + 5!/4!1! * 2 + 5!/3!2! * 2 + 5!/3!1!1! * 3 + 5!/2!2!1! * 3 + 5!/2!1!1!1! * 4 + 5!/1!1!1!1!1!

= 1 + 10 + 20 + 60 + 90 + 240 + 120 = 541 通り，

になります。

以上より明らかですが，この方法で問題を解いてみると．．．

問１：

2^7 = 128 通り。

問２：

2^(n-1) 通り。

問３：

3!/3! + 3!/1!2! + 3!/2!1! + 3!/1!1!1! = 1 + 3 + 3 + 6 = 13 通り。

問４：

4!4! + 4!/1!3! + 4!/2!2! + 4!/3!1! + 4!/1!1!2! + 4!/1!2!1! + 4!/2!1!1! + 4!/1!1!1!1!

= 1 + 4 + 6 + 4 + 12 + 12 + 12 + 24 = 75 通り。

問５：

ｎ人の場合の数は，

Σ[n=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/(p!q!r!…)} 通り。

また，漸化式の解法での f(n) は，

f(n) = Σ[n=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/(p!q!r!…)}，

です。そして，

f(n) = Σ[k=1,n]{nC(k-1) * f(k-1)}

= Σ[k=1,n]{nC(k-1) * Σ[k-1=p+q+r+…，p,q,r,... は 1 以上の整数]{(k-1)!/(p!q!r!…)}}

= Σ[k=1,n]{Σ[k-1=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/(n-k+1)!(k-1)! * (k-1)!/(p!q!r!…)}}

= Σ[k=1,n]{Σ[k-1=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/((n-k+1)!p!q!r!…)}}

n-k+1 = s とおくと，s は 1 以上の整数で，

n = (k-1) + s = (p + q + r + …) + s = s + p + q + r + …，

なので，

= Σ[n=s+p+q+r+…，s,p,q,r,... は 1 以上の整数]{n!/(s!p!q!r!…)}}，

s -> p，p -> q，q -> r，r は … の一部，と置き換えれば，

= Σ[n=p+q+r+…，p,q,r,... は 1 以上の整数]{n!/(p!q!r!…)}}，

となって，確かに漸化式を満たします。

なお，最初の解法と(別解)を比べると，

人を区別しない場合は大きな差はなさそうですが，

人を区別する場合まで考えると(別解)の方が見通しがよく考えやすいです。

ただ，人を区別する場合で人数が増えると計算が大変になりますが，

漸化式の方が少し楽かも知れません。

(感想)

人を区別しない場合には簡単な式になるのは意外でした。

人を区別した場合は今一つ詰め切れませんでした。

簡単な式になるのかなぁ．．．

この後に解答を送って，頂いた返信メールにあったアイディアを基に(別解)を追加しました。

確かにこの考え方の方が見通しがよくスッキリしています。

ただ，人を区別した場合の一般式は簡単にはなりそうにないですね。

そうなると，実用上は漸化式も悪くないと思います。

NO2「浜田明巳」 　　09/15 14時18分　受信 更新 10/02

問１．
　　(１，１，１，１，１，１，１，１)
　　(１，１，１，１，１，１，１，８)
　　(１，１，１，１，１，１，７，７)
　　(１，１，１，１，１，１，７，８)
　　(１，１，１，１，１，６，６，６)
　　・・・
のように，ｋ番目と(ｋ＋１)番目の人の順位は，等しいか等しくないかの２通りある．
　８人いるので，全部で，
　　２^７＝１２８（通り）

問２．
　問１と同様に，２^ｎ−１通り．

次に問５を解く．
問５．
　着数がｍ種類ある場合の組合せ数をａ_ｍとすると，
　　ａ_１＝１^ｎ＝１
　　　（すべて１）
　　ａ_２＝２^ｎ−_２Ｃ_１・ａ_１
　　　（１が数個，Ａが数個（１＜Ａ≦ｎ））
　　ａ_３＝３^ｎ−_３Ｃ_１・ａ_１−_３Ｃ_２・ａ_２
　　　（１が数個，Ａが数個，Ｂが数個（１＜Ａ＜Ｂ≦ｎ））
　　ａ_４＝４^ｎ−_４Ｃ_１・ａ_１−_４Ｃ_２・ａ_２−_４Ｃ_３・ａ_３
　　　（１が数個，Ａが数個，Ｂが数個，Ｃが数個（１＜Ａ＜Ｂ＜Ｃ≦ｎ））
　　ａ_５＝５^ｎ−_５Ｃ_１・ａ_１−_５Ｃ_２・ａ_２−_５Ｃ_３・ａ_３−_５Ｃ_４・ａ_４
　　　（１が数個，Ａが数個，Ｂが数個，Ｃが数個，Ｄが数個（１＜Ａ＜Ｂ＜Ｃ＜Ｄ≦ｎ））
　　・・・
　　ａ_ｎ＝ｎ^ｎ−_ｎＣ_１・ａ_１−_ｎＣ_２・ａ_２−_ｎＣ_３・ａ_３−・・・−_ｎＣ_ｎ−１ａ_ｎ−１
　　　（１，２，３，・・・，ｎが１個ずつ）
　求める組合せは，
　　ａ_１＋ａ_２＋ａ_３＋・・・＋ａ_ｎ（通り）

問３．
　問５において，ｎ＝３とする．
　　ａ_１＝１
　　ａ_２＝２^３−_２Ｃ_１・ａ_１＝８−２＝６
　　ａ_３＝３^３−_３Ｃ_１・ａ_１−_３Ｃ_２・ａ_２＝２７−３−１８＝６
　　∴ａ_１＋ａ_２＋ａ_３＝１＋６＋６＝１３（通り）

問４．
　問５において，ｎ＝４とする．
　　ａ_１＝１
　　ａ_２＝２^４−_２Ｃ_１・ａ_１＝１６−２＝１４
　　ａ_３＝３^４−_３Ｃ_１・ａ_１−_３Ｃ_２・ａ_２＝８１−３−４２＝３６
　　ａ_４＝４^４−_４Ｃ_１・ａ_１−_４Ｃ_２・ａ_２−_４Ｃ_３・ａ_３＝２５６−４−８４−１４４＝２４
　　∴ａ_１＋ａ_２＋ａ_３＋ａ_４＝１＋１４＋３６＋２４＝７５（通り）

NO3「早起きのおじさん」 09/19 21時45分　受信 更新

「早起きのおじさん」 09/26 09時14分　受信 更新 10/02

338解答　早起きのおじさん

※ 人を1(数字)で表します。

※ ここでは、順位に差があるときに、境目にカンマ“,”を入れ、ないときは続けて書くことにします。

問0

●3人の場合の順位の起こり方を考えます。

人と人との間“v”が2つあります。

（1v1v1）

その2つの間に順位差があるか、ないかの場合の数を数えます。

0：どこにも順位差がないとき、全員1位です。　（111）･････････････････ 通り

1：順位差のあるところが1つある。　　　　　　（1，22）、（11，3）･･････ 通り

2：すべてに順位差がある。　　　　　　　　　　（1，2，3）･････････････ 通り

以上から、 通りです。

●4人の場合の順位の起こり方を考えます。

3人目までの順位の起こり方は、上の4通りです。

4人目の1人が増えると、順位の種類は、そのままか、1つ増えるかのどちらかです。

（順位の種類が減ることはありません）

n人のときの場合の数を とすると、 なので、4人の場合は、2×4＝8 通りです。

また、 通りです。

問1

8人のときは、 通りです。

問2

通りです。

※※　左からカンマまでが同順位とします。

※※　n人の順位の起こり方で、k種類のときの場合の数をf(n,k)で表すことにします。

問2.5

●2人の順位の起こり方を考えます。

0：1種類のとき、全員同じ順位です。　（AB）

1：2種類のとき、　　　　　　　　　　（A，B）、（B，A）

つまり、ｆ(2,1)＝1、f(2,2)＝2 なので、合計3通りです。

問3

3人目のCの順位の起こり方を考えます。

順位の種類の数が変わらないか、1種類増えるか、のどちらかです

1種類のとき、f(3,1)＝1 は、明らかです。

2種類のときは、f(2,1)の1種類の左右の順位に入るか、f(2,2)の2種類のどちらかと同順位です。

3種類のときは、f(2,2)の2種類の間か左右の順位に入ると考えて、f(3,3)＝3×f(2,2)＝3×2×1＝3!＝6

つまり、場合の数は、

問4

4人のときを考えます。

1種類のとき、f(4,1)＝1は、明らかです。

2種類のときは、f(3,1)の1種類の左右の順位に入るか、f(3,2)の2種類のどちらかと同順位です。

3種類のときは、f(3,2)の2種類の間か左右の順位に入る、またはf(3,3)の3種類のどこかと同順位です。

4種類のときは、f(3,3)の3種類の間か左右の順位に入ると考えて、f(4,4)＝4×f(3,3)＝4×3!＝4!＝24

つまり、場合の数は、

問4.5

●まず、今までのことから、次の漸化式を確認します。

1人増えたときは、1つ順位の種類が増えるか、どこかの同順位の人が増えるかのどちらかです。

この漸化式から次の表の計算ができます。

この表で、f(n,1)＝1、f(n,n)＝n! です。

また、この表は、次の表のような構造をしています。

エクセルなどを用いれば、式のコピーで簡単に作成できます。

●二項定理から次の式を確認しておきます。

●階差 が分かっている数列 の一般項の式を確認しておきます。

問5

順位の種類数ごとに調べてみます。

・k＝1のとき、f(n,1)＝1は明らかです。

・k＝2のときは、1位が1人のとき、2人のとき、3人のとき、･･･というように総数を数えます。

・k＝3のときの漸化式に上の結果を用いると、(n≧4です)

よって、nを1ずらした式と差をとると、階差の式が導けます。

この両辺を で割ります。

ここで、

とおくと、

両辺に3を足すと、

は、公比3/2の等比数列です。

階差が2つの等比数列の差なので、

以上のように求められますが、計算が大変です。

（k＝4のとき、手間は格段に増えます）

別の方法を考えます。

1位の人数が、1人のとき、2人のとき、3人のとき、･･･というように総数を数えてみます。

すると、

のようにかなり楽にできます。

・k＝4のときも、1位の人数が、1人のとき、2人のとき、3人のとき、･･･というように総数を数えます。

以上のようにできますが、だいぶ大変になります。

そこでまた別の方法を考えます。

結果を並べてみます。

例えば、k＝2のとき、順位は2種類です。

上位か下位の選択は、2ⁿ通りあります。

そして、上位だけ、あるいは下位だけに集まる場合の数を引いています。

k＝3のときは、上中下の3種類を選ぶ場合の数から、最大2種類までの場合の数、1種類だけの場合の数で補正しています。

あえて組み合わせの記号を用いて書き直します。

このピラミッド型に並ぶ数の総合計が求める数です。

これを指数が同じになるように、右下がりの斜め線で切り、1つずつ調べていきます。

・まず、赤いところは、

・橙色のところは、

・黄色のところは、

・・・

・黄緑のところは、

・・・

以上をまとめると、

さて、計算結果の｛1,3,13,75,541,･･･｝にはどんな意味があるのかは、分かりません。

NO4「二度漬け白菜」 09/24 16時15分　受信 更新 10/02

問1：2^7=128 通り (答)

問2：2^(n-1) 通り (答)

問3：13 通り (答)

問4：75 通り (答)

問5：人を区別する場合，n人で争うときの順位の起こり方が全部で b(n) 通りあるとする．

b(n)の漸化式：
b(0)=1，
b(n)=Σ[k=0,n-1]comb(n,k)*b(k)．(答)

b(n)を，シグマ和を2回使って書き表す：
b(n)=Σ[k=1,n]Σ[j=0,k]comb(k,j)*(j^n)*(-1)^(k-j)．(答)

b(n)を，自然対数 e と，ガウス記号(floor関数)を使って書き表す：
b(n)=floor(n!*(n!*8^n)^n/(2-e^(1/(n!*8^n))))-(n!*8^n)*floor(n!*(n!*8^n)^(n-1)/(2-e^(1/(n!*8^n))))．(答)

xの関数f(x)を級数展開したときのx^nの係数を [x^n]f(x) と表すことにする．
人を区別しない場合，n人で争うときの順位の起こり方が全部で a(n) 通りあるとする．

問1：
a(8)
=[x^8]((x+x^2+x^3+ …)+(x+x^2+x^3+ …)^2+ … +(x+x^2+x^3+ …)^8)
=[x^8]((x+x^2+x^3+ …)+(x+x^2+x^3+…)^2+(x+x^ 2+x^3+$ B!D)^3+ …)
=[x^8](x/(1-x)+(x/(1-x))^2+(x/(1-x))^3+ …)
=[x^8](x/(1-x)/(1-x/(1-x)))
=[x^8](x/(1-2*x))
=[x^7](1/(1-2*x))
=2^7
=128．

問2：
a(n)
=[x^n]((x+x^2+x^3+ …)+(x+x^2+x^3+ …)^2+(x+x^2+x^3+ …)^3+ …)
=[x^n](x/(1-2*x))
=[x^(n-1)](1/(1-2*x))
=2^(n-1)．

問3：
b(3)
=[x^3](3!*(x+x^2/2!+x^3/3!)+3!*(x+x^2/2!+x^3/3!)^2+3!*(x+x^2/2!+x^3/3!)^3)
=13

問4：
b(3)
=[x^4](4!*(x+x^2/2!+x^3/3!+x^4/4!)+4!*(x+x^2/2!+x^3/3!+x^4/4!)^2+4!*(x+x^2/2!+x^3/3!+x^4/4!)^3+4!*(x+x^2/2!+x^3/3!+x^4/4!)^4)
=75

問5：
b(n)
=[x^n](n!*(x+x^2/2!+ … +x^n/n!)+n!*(x+x^2/2!+ … +x^n/n!)^2+ … +n!*(x+x^2/2!+ … +x^n/n!)^n)
=n!*[x^n]((x+x^2/2!+ … +x^n/n!)+(x+x^2/2!+ … +x^n/n!)^2+ … +(x+x^2/2!+ … +x^n/n!)^n)
=n!*[x^n]((x+x^2/2!+ …щu梠梟弌・指)�氤J・・涓・゛�凾ﾀ… +x^n/n!)^2+ … )
=n!*[x^n]((x+x^2/2!+ … )+(x+x^2/2!+ … )^2+ … )
=n!*[x^n]((e^x - 1)+(e^x - 1)^2+ … )
=n!*[x^n]((e^x - 1)/(1-(e^x - 1)))
=n!*[x^n]((e^x - 1)/(2-e^x))
=n!*[x^n](1/(2-e^x) - 1)
=n!*[x^n](1/(2-e^x))．

よって，b(n)/(n!)=[x^n](1/(2-e^x))．
B(x)=Σ[n=0,∞](b(n)/(n!))*x^n， b(0)=1 とおくと，
B(x)
=Σ[n=0,∞]([x^n](1/(2-e^x))*x^n)
=(1/(2-e^x))．
よって，(2-e^x)*B(x)=1．
この式の両辺の x^n の係数を比較して，
2*b(n)/(n!)-Σ[k=0,n]*b(k)/(k!)*(1/((n-k)!))=0．
よって，b(n)/(n!)-Σ[k=0,n-1]*b(k)/(k!)*(1/((n-k)!))=0．
つまり，b(n)=n!*Σ[k=0,n-1]*b(k)/(k!*(n-k)!)=Σ[k=0,n-1]comb(n,k)*b(k)．

また，b(n)=n!*[x^n]((e^x - 1)+(e^x - 1)^2+ … +((e^x - 1)^n)) であることと，
[x^n](e^x - 1)^k
=[x^n](Σ[j=0,k]comb(k,j)*(e^(j*x))*(-1)^(k-j))
=Σ[j=0,k]comb(k,j)*(j^n/(n!))*(-1)^(k-j)
であることとから，
b(n)=Σ[k=1,n]Σ[j=0,k]comb(k,j)*(j^n)*(-1)^(k-j)．

B(x)=Σ[n=0,∞](b(n)/(n!))*x^n より，
n!*B(x)/(x^n)=Σ[k=1,n](n!/(n-k)!)*b(n-k)/(x^k) + b(n) + Σ[k=1,∞](n!/(n+k)!)*b(n+k)*(x^k)．
x=1/(n!*8^n) を代入して，
n!*B(1/(n!*8^n))*(n!*8^n)^n = Σ[k=1,n](n!/(n-k)!)*b(n-k)*(n!*8^n)^k + b(n) + Σ[k=1,∞](n!/(n+k)!)*b(n+k)*(1/(n!*8^n))^k．
ここで，Σ[k=1,n](n!/(n-k)!)*b(n-k)*(n!*8^n)^k は (n!*8^n) の倍数．
また，b(n+j)＜(n+j)!*2^(n+j) (j=0,1,2,…) に注意すると，
Σ[k=1,∞](n!/(n+k)!)*b(n+k)*(1/(n!*8^n))^k
＜ Σ[k=1,∞](n!/(n+k)!)*(n+k)!*2^(n+k)*(1/(n!*8^n))^k
＜ Σ[k=1,∞]2^(n+k)*(1/(8^n))^k
=(2^n)*Σ[k=1, $B!g] (2/(8^n))^k
=(2^(n+1))/(8^n - 2)
＜1．
よって，b(n)は n!*B(1/(n!*8^n))*(n!*8^n)^n の整数部分を (n!*8^n) で割ったときの余りになっていることがわかる．
よって，
b(n)
=floor(n!*B(1/(n!*8^n))*(n!*8^n)^n)-(n!*8^n)*floor(n!*B(1/(n!*8^n))*(n!*8^n)^(n-1))
=floor(n!*(n!*8^n)^n/(2-e^(1/(n!*8^n))))-(n!*8^n)*floor(n!*(n!*8^n)^(n-1)/(2-e^(1/(n!*8^n))))．

----------------------------------------------------------------------------------------------------

今回の問題に関連して次のような問題を考えているのですが，規則性がつかめません．
人を区別しない場合，3人で争うときの順位の起こり方は，
(1,1,1)，(1,1,3)，(1,2,2)，(1,2,3)
の4通り．
このとき現れる数を全て足し合わせると，
(1+1+1)+(1+1+3)+(1+2+2)+(1+2+3)=19．

人を区別しない場合，4人で争うときの順位の起こり方は，
(1,1,1,1)，(1,1,1,4)，(1,1,3,3)，(1,1,3,4)，(1,2,2,2)，(1,2,2,4)，(1,2,3,3)，(1,2,3 ,4)
の8通り．
このとき現れる数を全て足し合わせると，
(1+1+1+1)+(1+1+1+4)+(1+1+3+3)+(1+1+3+4)+(1+2+2+2)+(1+2+2+4)+(1+2+3+3)+(1+2+3+4)=63．

一般に，人を区別しない場合，n人で争うときの順位の起こり方を全て書き出したときに

現れる数を全て足し合わせたものをC(n)とする．
C(n)はどのように書き表されるか

「二度漬け白菜」 09/25 21時07分　受信 更新 10/02

＜水の流れ：問５の数列は１、３、１３、７５、５４１、・・・はどんな意味になるのか気がかりです。＞

この返信です。

問5は，数列の「意味」を答える問題であったのですか？
問題文には，
「（A,B,C、・・・・）のｎ人のとき、順位の起こり方は何通りあるか考察せよ。」
とあります．
「n人のとき，順位の起こり方は何通りあるか」
という問いなのですから，
「この数列の一般項はどのように書けるか」
というふうに私は解釈しました．

この数列の「意味」は，
「n人に順位をつけるときの ，順位の付け方の総数」
だと思います．

「n人を，最大n個の組に分けて，それらの組に順番を付けて
区別する方法の総数」ということもできます．

オンライン整数列大辞典には，「Fubini numbers」という
名称がつけられて登録されていますね．
https://oeis.org/A000670

「二度漬け白菜」 10/01 13時43分　受信 更新 10/02

9月24に私が送信したメールの最後に次のような疑問を書きました．

「一般に，人を区別しない場合，n人で争うときの順位の起こり方を全て書き出したときに
現れる数を全て足し合わせたものをC(n)とする．
C(n)はどのように書き表されるか？」

この疑問について，C(n)をnで表す式がわかりましたので，
報告をしておきます．

C(n)=(n^2-n+4)*2^(n-2)-1　と書き表されます．

以上報告まで．

NO5「にいばりZ12」　　　10/03 00時04分　受信 更新 10/03

問１：　８人でタイムを争うとき、順位の起こり方は何通りあるか。

問２：　一般にｎ人で争うとき（マラソンみたいに大勢で）、順位の起こり方は何通りあるか。

（マラソンと言うより、同じスコアにひしめき合うゴルフの試合に多いケースですね・・・。）

次のように考えます

ｎ人を着順に左から並べます。・・・・（�T）

○○○○○○○○・・・・○○○（○がｎ個（人））

この時次のように同着を衝立で仕切ります

○○○｜○○○○｜○・・・・○○○

上の場合1位が３人、４位が４人８位がｎ-7人となります

衝立が無い場合は全員同着で１位

全ての間に衝立が入る場合同着がなく１位からｎ位までとなります。

衝立の入る場所はｎ-1か所(植木算)で、衝立の数のケースは0からｎ-1までです

つまり衝立の入り方の総数が順位の起こり方の総数となります

よってその数は

_n-1C₀+_n-1C₁+ _n-1C₂+ _n-1C₃+ _n-1C₄+ _n-1C₅+ ・・・・_n-1C_n-1=Σ_k=0→n-1( _n-1C_k）=2^n-1（∵2項係数の総和に等しい）

よって順位の起こり方の総数

2^n-1通り・・・問2回答

8人の時はn=8で

2^8-1=128通り・・・問1回答

問３：　（A,B,C）の３人のとき、順位の起こり方は何通りあるか。

問４：（A,B,C,D）の４人のとき、順位の起こり方は何通りあるか。

問５：（A,B,C,・・・・）のｎ人のとき、順位の起こり方は何通りあるか考察せよ。

（�T）と同様に着順で並べます。この時同着はどう並べても同じと考えます。

また、衝立の入る場所を左から1番目、2番目・・・ｎ-1番目とします

ひたすら地道に計算してみます

・衝立が無い場合

全員1位なので1通り

_nC₀

・衝立が1本の場合(n>1)

　　・衝立が1番目に入る場合

　　　1位は_nC₁=n通りあります

　　・衝立が2番目に入る場合

　　　1位は_nC₂通りあります

　　・衝立がm番目に入る場合

　　　1位は_nC_m通りあります

　　・衝立がn-1番目に入る場合

　　　1位は_nC_n-1=n通りあります

・これらの総和は

_nC₁+ _nC₂+ _nC₃+ _nC₄+ _nC₅+ ・・・・_nC_n-1=Σ_k=1→n-1( _nC_k）=Σ_k=0→n ( _nC_k）- _nC₀- _nC_n=2ⁿ-2

・衝立が2本の場合(n>2)

　　・1本目の衝立が1番目に入る場合

　　　1位は_nC₁=n通りあります

　　　　　　　それに対し2本目の衝立が2番目に入ると

　　　　　　　　　2位は_n-1C₁= n-1通りあります

　　　　　　　2本目の衝立が3番目に入ると

　　　　　　　　　2位は_n-1C₂通りあります

　　　　　　　2本目の衝立が4番目に入ると

　　　　　　　　　2位は_n-1C₃通りあります

　　　　　　　2本目の衝立がn-1番目に入ると

　　　　　　　　　2位は_n-1C_n-2= n-1通りあります

　　　　　　　2本目の衝立を立てた時の

　　　　　　　　　2位の現れ方は

_n-1C₁+ _n-1C₂+ _n-1C₃+ _n-1C₄+ _n-1C₅+ ・・・・_n-1C_n-2=Σ_k=1→n-2( _n-1C_k）=Σ_k=0→n-1 ( _n-1C_k）- _n-1C₀- _n-1C_n-1=2^n-1-2

　　・1本目の衝立が2番目に入る場合

　　　1位は_nC₂通りあります

　　　　　　　それに対し2本目の衝立が3番目に入ると

　　　　　　　　　3位は_n-2C₁= n-2通りあります

　　　　　　　2本目の衝立が4番目に入ると

　　　　　　　　　3位は_n-2C₂通りあります

　　　　　　　2本目の衝立が4番目に入ると

　　　　　　　　　3位は_n-2C₃通りあります

　　　　　　　2本目の衝立がn-1番目に入ると

　　　　　　　　　3位は_n-2C_n-3= n-1通りあります

　　　　　　　2本目の衝立を立てた時の

　　　　　　　　　3位の現れ方は

_n-2C₁+ _n-2C₂+ _n-2C₃+ _n-2C₄+ _n-2C₅+ ・・・・_n-2C_n-3=Σ_k=1→n-3( _n-2C_k）=Σ_k=0→n-2 ( _n-2C_k）- _n-2C₀- _n-2C_n-2=2^n-2-2

　　・1本目の衝立が3番目に入る場合

　　　1位は_nC₃通りあります

　　　　　　　それに対し2本目の衝立が4番目に入ると

　　　　　　　　　4位は_n-3C₁= n-3通りあります

　　　　　　　2本目の衝立が4番目に入ると

　　　　　　　　　4位は_n-3C₂通りあります

　　　　　　　2本目の衝立が4番目に入ると

　　　　　　　　　4位は_n-3C₃通りあります

　　　　　　　2本目の衝立がn-1番目に入ると

　　　　　　　　　4位は_n-3C_n-4= n-3通りあります

　　　　　　　2本目の衝立を立てた時の

　　　　　　　　　4位の現れ方は

_n-3C₁+ _n-3C₂+ _n-3C₃+ _n-3C₄+ _n-3C₅+ ・・・・_n-3C_n-4=Σ_k=1→n-4( _n-3C_k）=Σ_k=0→n-3 ( _n-3C_k）- _n-3C₀- _n-3C_n-3=2^n-3-2

　　・1本目の衝立が4番目に入る場合

　　　1位は_nC₄通りあります

　　　　　　　それに対し2本目の衝立が5番目に入ると

　　　　　　　　　5位は_n-4C₁= n-4通りあります

　　　　　　　2本目の衝立がn-1番目に入ると

　　　　　　　　　5位は_n-4C_n-5= n-4通りあります

　　　　　　　2本目の衝立を立てた時の

　　　　　　　　　5位の現れ方は

2^n-4-2

　　・1本目の衝立がn-2番目に入る場合

　　　1位は_nC_n-2通りあります

　　　　　　　それに対し2本目の衝立がn-1番目に入る(しかないのですが)と

　　　　　　　　　n-1位は_n-(n-2)C_n-(n-1)=2通りあります

　　　　　　　2本目の衝立を立てた時の

　　　　　　　　　n-1位の現れ方は

2^n-(n-2)-2

これを整理すると衝立が2本の場合

_nC₁(2^n-1-2)+ _nC₂(2^n-2-2) + _nC₃(2^n-3-2) + _nC₄(2^n-4-2) + _nC₅(2^n-5-2)+・・・+ _nC_n-2(2^n-(n-2)-2)

= _nC₁・2^n-1+ _nC₂・2^n-2 + _nC₃・2^n-3 + _nC₄・2^n-4 + _nC₅・2^n-5+・・・+ _nC_n-2・2^n-(n-2) -2(_nC₁+ _nC₂ + _nC₃+ _nC₄ + _nC₅+・・・+ _nC_n-2)

= _nC₁・2^n-1+ _nC₂・2^n-2 + _nC₃・2^n-3 + _nC₄・2^n-4 + _nC₅・2^n-5+・・・+ _nC_n-2・2^n-(n-2) -2(_nC₀+_nC₁+ _nC₂ + _nC₃+ _nC₄ + _nC₅+・・・+ _nC_n-2 + _nC_n-1+ _nC_n- _nC₀- _nC_n-1- _nC_n)

= _nC₀・2ⁿ+ _nC₁・2^n-1+ _nC₂・2^n-2 + _nC₃・2^n-3 + _nC₄・2^n-4 + _nC₅・2^n-5+・・・+ _nC_n-2・2^n-(n-2) + _nC_n-1・2^n-(n-1) + _nC_n・2^n-(n-0)- _nC₀・2ⁿ - _nC_n-1・2^n-(n-1) - _nC_n・2^n-(n-0)-2(2ⁿ- n - 2)

=3ⁿ- 2ⁿ -2n - 1-2(2ⁿ- n - 2) ⁿ =3ⁿ-3・2ⁿ + 3・・・・（（2+1) ⁿの2項展開を利用）

・衝立が3本の場合(n>3)

　 衝立が2本の時と同様に考えると

_nC₁･_n-1C₁ (_n-2C₁+ _n-2C₂+ _n-2C₃+ _n-2C₄+ _n-2C₅+・・・+ _n-2C_n-3)                      ○｜○｜○｜○｜○｜○｜○｜○・・・・○｜○｜○（衝立｜は()内の各項）

+_nC₁･_n-1C₂ (_n-3C₁+ _n-3C₂+ _n-3C₃+ _n-3C₄+・・・+ _n-3C_n-4)　　 　　○｜○○｜○｜○｜○｜○｜○・・・・○｜○｜○

+_nC₁･_n-1C₃ (_n-4C₁+ _n-4C₂+ _n-4C₃+ +・・・+ _n-4C_n-5) 　　　　　 ○｜○○○｜○｜○｜○｜○・・・・○｜○｜○

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

+_nC₁･_n-1C_n-3(_n-(n-2)C_n-(n-1)) ○｜○○○○○○○・・・・○｜○｜○・・・・・・・（1）

+_nC₂･_n-2C₁ (_n-3C₁+ _n-3C₂+ _n-3C₃+ _n-3C₄+ _n-3C₅+・・・+ _n-3C_n-4)                    　○○｜○｜○｜○｜○｜○｜○・・・・○｜○｜○

+_nC₂･_n-2C₂ (_n-4C₁+ _n-4C₂+ _n-4C₃+ _n-4C₄+・・・+ _n-4C_n-5)　　 　　　 ○○｜○○｜○｜○｜○｜○・・・・○｜○｜○

+_nC₂･_n-2C₃ (_n-5C₁+ _n-5C₂+ _n-5C₃+ +・・・+ _n-5C_n-6) 　　　　　 ○○｜○○○｜○｜○｜○・・・・○｜○｜○

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

+_nC₂･_n-2C_n-4(_n-(n-2)C_n-(n-1)) 　○○｜○○○○○○・・・・○｜○｜○・・・・・・・・（2）

+_nC₃･_n-3C₁ (_n-4C₁+ _n-4C₂+ _n-4C₃+ _n-4C₄+ _n-4C₅+・・・+ _n-4C_n-5)                    　○○○｜○｜○｜○｜○｜○｜○・・・・○｜○｜○

+_nC₃･_n-3C₂ (_n-5C₁+ _n-5C₂+ _n-5C₃+ _n-5C₄+・・・+ _n-5C_n-6)　　 　　　 ○○○｜○○｜○｜○｜○｜○・・・・○｜○｜○

+_nC₃･_n-3C₃ (_n-6C₁+ _n-6C₂+ _n-6C₃+ +・・・+ _n-6C_n-7) 　　　　　 ○○○｜○○○｜○｜○｜○・・・・○｜○｜○

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

+_nC₃･_n-3C_n-5(_n-(n-2)C_n-(n-1)) ○○○｜○○○○○・・・・○｜○｜○・・・・・・・・（3）

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

　　　　　　　　　　　　　　・

+ _nC _n-3･_n-(n-3)C_n-(n-1) (_n-(n-2)C_n-(n-1)) ○○○○○○○○・・・・｜○｜○｜○・・・・・・・・（＊）

この式を簡単にするために先ず（）の中（3本目の衝立の左側の組み合わせ）を整理していきます

（1）の各項にの（）内を考えます。（1）1項目の（）内は次のように変形できます

_n-2C₁+ _n-2C₂+ _n-2C₃+ _n-2C₄+ _n-2C₅+・・・+ _n-2C_n-3

= _n-2C₀+_n-2C₁+ _n-2C₂+ _n-2C₃+ _n-2C₄+ _n-2C₅+・・・+ _n-2C_n-3+ _n-2C_n-2- _n-2C₀- _n-2C_n-2

=2^n-2-2

同様に（1）2項目以降の（）内も次のように変形できます

_n-3C₁+ _n-3C₂+ _n-3C₃+ _n-3C₄+・・・+ _n-3C_n-4

=2^n-3-2

_n-4C₁+ _n-4C₂+ _n-4C₃+ ・・・+ _n-4C_n-5

=2^n-4-2

（1）は、n-3項あるので最後は

=2^n-(n-2)-2=2²-2=2

従って（1）は次のように変形できます

_nC₁ (_n-1C₁(2^n-2-2)+ _n-1C₂(2^n-3-2)+ _n-1C₃(2^n-4-2)+ _n-1C₄(2^n-5-2)+ ・・・+_n-1C_n-3(2²-2))

= _nC₁ ( (_n-1C₁・2^n-2+ _n-1C₂・2^n-3+ _n-1C₃・2^n-4+ _n-1C₄・2^n-5+ ・・・+_n-1C_n-3・2²) -2 (_n-1C₁+ _n-1C₂+ _n-1C₃+ _n-1C₄+ ・・・+_n-1C_n-3) )

= _nC₁ ( (_n-1C₀・2^n-1+_n-1C₁・2^n-2+ _n-1C₂・2^n-3+ _n-1C₃・2^n-4+ _n-1C₄・2^n-5+ ・・・+_n-1C_n-3・2²+_n-1C_n-2・2¹+_n-1C_n-1・2⁰- _n-1C₀・2^n-1-_n-1C_n-2・2¹-_n-1C_n-1・2⁰) -2 (_n-1C₀+_n-1C₁+ _n-1C₂+ _n-1C₃+ _n-1C₄+ ・・・+_n-1C_n-3+_n-1C_n-2+_n-1C_n-1-_n-1C₀-_n-1C_n-2-_n-1C_n-1) )

= _nC₁ ( (3^n-1- 2^n-1-2n+1) -2 (2^n-1- n-1) )

= _nC₁ (3^n-1- 3･2^n-1+3)

上式（）内は、n-1の時の衝立2本と同じなので容易に理解できます

という事で（2）式以降は

　　_nC₂ (3^n-2- 3･2^n-2+3) ・・・・（2）

　　_nC₃ (3^n-3- 3･2^n-3+3) ・・・・（3）

　　　　・

　　　　・

　　　　・

　　_nC_n-3 (3^n-(n-3)- 3･2 ^n-(n-3)+3)・・・・（＊　_nC_n-3･6）

これらを足し合わせ変形すると

　　　_nC₁ (3^n-1- 3･2^n-1+3)+_nC₂ (3^n-2- 3･2^n-2+3)+_nC₃ (3^n-3- 3･2^n-3+3)+････+ _nC_n-3 (3 ^n-(n-3)- 3･2 ^n-(n-3)+3)

= (_nC₁･3^n-1+_nC₂･3^n-2+_nC₃･3^n-3+････+ _nC_n-3･3 ^n-(n-3) ) -3 (_nC₁･2^n-1+_nC₂･2^n-2+_nC₃･2^n-3+････+ _nC_n-3･2 ^n-(n-3) )+ 3 (_nC₁+_nC₂+_nC₃･2^n-3+････+ _nC_n-3)

= (_nC₀･3ⁿ+_nC₁･3^n-1+_nC₂･3^n-2+_nC₃･3^n-3+････+ _nC_n-3･3 ^n-(n-3) + _nC_n-2･3 ^n-(n-2) + _nC_n-1･3 ^n-(n-1)+ _nC_n･3 ^n-(n-0) - _nC₀･3ⁿ - _nC_n-2･3 ^n-(n-2)- _nC_n-1･3 ^n-(n-1) - _nC_n･3 ^n-(n-0))

-3 (_nC₀･2ⁿ+_nC₁･2^n-1+_nC₂･2^n-2+_nC₃･2^n-3+････+ _nC_n-3･2 ^n-(n-3) + _nC_n-2･2 ^n-(n-2) + _nC_n-1･2 ^n-(n-1)+ _nC_n･2 ^n-(n-0)-_nC₀･2ⁿ- _nC_n-2･2^n-(n-2)-_nC_n-1･2 ^n-(n-1)-_nC_n･2 ^n-(n-0))

+ 3 (_nC₁+_nC₁+_nC₂+_nC₃･2^n-3+････+ _nC_n-3+ _nC_n-2+ _nC_n-1+ _nC_n-_nC₀-_nC_n-2-_nC_n-1-_nC_n)

= (4ⁿ - 3ⁿ - 3² (n²-n)-3n -1)

-3 (3ⁿ- 2ⁿ- 2²(n²-n)-2n -1)

+ 3 (2ⁿ -1-(n²-n)- n -1)

= 4ⁿ - 4･3ⁿ +6･2ⁿ -4

とりあえずここで衝立3本までの結果を整理してみます

衝立0本　　1･1 ⁿ-1･0ⁿ　　　通り

衝立1本　　1･2ⁿ-2･1ⁿ+1･0ⁿ　　通り

衝立2本　　1･3ⁿ-3･2ⁿ + 3･1ⁿ-1･0ⁿ　　通り

衝立3本　　1･4ⁿ - 4･3ⁿ +6･2ⁿ -4･1ⁿ+1･0ⁿ　　通り

この結果を見ると人数をn人、衝立の本数をtとした時、順位の起こり方の数pには次の式が予想されます

p=Σ_i=-1→t((-1)ⁱ⁺¹(t-i)ⁿ( _t+1C_i+1))　　　　　　　　　　　　　　　　　

また、人数をn人、衝立の本数tを0からt’とした時、順位の起こり方の数Pには次の式が予想されます

P=Σ_t=0→t’ (Σ_i=-1→t((-1)ⁱ⁺¹(t-i)ⁿ( _t+1C_i+1)))

いま、題意からt’=n-1なので上式は次のようになります

P=Σ_t=0→n-1 (Σ_i=-1→t((-1)ⁱ⁺¹(t-i)ⁿ( _t+1C_i+1)))･･･�@

この式は（計算が間違っていなければ）とりあえずn=4までは真なので

3人の時

1+2³-2+3³-3･2³+3=13

13通り・・・問3回答

4人の時

1+2⁴-2+3⁴-3･2⁴+3+4⁴ - 4･3⁴ +6･2⁴ -4=75

75通り・・・問4回答

�@式をnだけの式にすることも、証明もできない(数学的帰納法で何とかと思ったのですが･･･)ので別の視点から眺めなおしてみます。

　・1本目の衝立がt₁番目(0< t₁<n-2)、 2本目の衝立がt₂番目(t₁< t₂<n-1)、 3本目の衝立がt₃番目(t₂<t₃<n)に入るとき

　　　1位はt₁人いて_nC _t1通りあります

　　　　　　t ₁+1位はt ₂- t ₁人いて_n-t1C _{t2- t1}通りあります

　　　　　　t ₂+1位はt ₃- t ₂人いて_{n- t2}C _{t 3- t2}通りあります

これらの組み合わせは

　　　　　_nC _t1・_{n- t1}C _{t2- t1}・_{n- t2}C _{t3- t2}

　　　=n!/(t₁!(t₂-t₁)!(t₃-t₂)!(n-t₃)!) ･･･�A

となり多項係数になります（∵t₁+(t₂-t₁)+(t₃-t₂)+(n-t₃)=n）

そこで多項係数の意味をこのケースに当てはめて考えてみます

いま、衝立に仕切られるグループの数をg(グループ数は衝立数より1つ多い)とし、各グループの人数を順位の高い方からk₁,k₂･･･,k_g（k₁+k₂+･･･+k_g =n）とします

g=t+1

t₁= k₁

t₂-t₁= k₂

t₃-t₂= k₃

　・

　・

　・

n-t_g-1= k_g

上記を代入し式を一般化すると式�Aは

　　　　　_nC _k1・_{n- k1}C _k2・_{n- (k1+ k2)}C _k3・_{n- (k1+ k2+ k3)}C _k4・･･･・_{n- (k1+ k2+ k3+････+ kg-1)}C _kg

　　　=n!/( k₁! k₂! k₃! k ₄!････k_g!)

上記多項係数は

(x₁+x₂+･･･+x_g)ⁿ･･･�B

を展開したときの係数で、かつグツープ数がgの時の組み合わせの数となります。

係数を問題にしているのでx₁=x₂=･･･=x_g=1とします

また、k_iの最小値は1でk_iの最大値はn-g+1

一般に多項係数の総和は（k₁+k₂+･･･+k_g =n； k_iが非負整数を満たせば）gⁿとなります（x₁=x₂=･･･=x_g=1と置いたときの�Bを展開したときの左右辺の比較）が上記最大最小の制約を考慮しなければなりません。

k_iが0の時の場合の数は

_gC₀+ _gC₁+ _gC₂+･･･

ここまで考えて時間切れとなってしまいました

整理していけば�@と同じ式が導けるような気がするのですが・・・。

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。