ラ・サール高校入試の問題を大学入試レベルに魔改造

こんにちは。萃聚(すいじゅ)です。
ラ・サール高校の2013年の問題に、こんなのがありました。

問題

$a$ ,$b$ ,$c$ の3種類の文字をそれぞれ少なくとも1回ずつ使って文字列を作る。次の問に答えよ。
(1)4文字の文字列は全部で何通りできるか。
(2)5文字の文字列は全部で何通りできるか。

発想を転換した解法

この問題、普通なら、$a$, $b$, $c$ の3文字に加えて残りは何の文字を使うかで場合分けするじゃないですか。それが確かに一番速いんですよ。
でも僕は思いました。$a$, $b$, $c$ の3種をそれぞれ、グー、チョキ、パーに当てはめてみると、(1)の場合、4人でじゃんけんをして、3種の手が出たときという風に言い換えられます。
そういえば、じゃんけん問題では場合の数が計算で求められたなぁということを思い出して、じゃんけん問題と同じ考えでやってみようと思ったわけです。
まず、(1)で4文字連ねる時、1番目、2番目、3番目、4番目にそれぞれ $a$, $b$, $c$ のどの文字を選択してもいいと考えると、$3×3×3×3＝3^4$ 通りです。でも実際は、$a$, $a$, $b$, $a$みたいなのはダメなので、2文字しか使わないときと1文字しか使わないときを考えて、引いてみます。
まず2文字しか使わないときですが、3文字の中からどの2文字を使うか選ぶ選び方は ${}_3 C_2=3$ 通りです。仮にそれが$a$ と $b$ だとすると、先ほどと同様に、1番目、2番目、3番目、4番目にそれぞれ $a$ と $b$ のどちらの文字を入れてもいいと考えて24通りですが、$a.a.a,a$ と $b,b,b,b$ はダメなので２を引きます。
そして、1文字しか使わないときは、どの１文字かで３通りですから３を引きます。
以上より、(1)の答えは、
\[3^4-3\left(2^4-2\right)-3=81-3\times14-3=36\] \[\small3^4-3\left(2^4-2\right)-3=81-3\times14-3=36\] です。

(2)で5文字連ねる時は全く同様の考え方なので、指数を５にチェンジするだけです。
\[3^5-3\left(2^5-2\right)-3=243-3\times30-3=150\] \[\small3^5-3\left(2^5-2\right)-3=243-3\times30-3=150\] です。
場合分けをせずにあっという間に答えが求まります。

では、$a,b,c,d$ の4文字を少なくとも１つずつ使って5文字の列、6文字の列を作るというパターンならどうでしょう。文字数を増やしてます。
まず5文字の列の場合だと、
どの文字を選択してもいいとすると→$4^5$
そこから3文字しか使わない時、2文字しか使わない時、1文字しか使わない時を引きます。
3文字しか使わない→3文字の選び方は${}_4 C_3=4$。並び方は先ほどのを流用して、$3^5-3\left(2^5-2\right)-3$
2文字しか使わない→2文字の選び方は${}_4 C_2=6$。並び方は同様に、$2^5-2$ 通り
1文字しか使わない→４通り
以上より、5つ並べる時は \[4^5-4\left\{3^5-3\left(2^5-2\right)-3\right\}-6\left(2^5-2\right)-4=1024-4\times150-6\times30-4=00240\] \[\small 4^5-4\left\{3^5-3\left(2^5-2\right)-3\right\}-6\left(2^5-2\right)-4\\ =1024-4\times150-6\times30-4\\ =240\] 6つのときは \[4^6-4\left\{3^6-3\left(2^6-2\right)-3\right\}-6\left(2^6-2\right)-4=4096-4\times540-6\times62-4=1560\]

始まる魔改造と一般化

さあ、ここからが本番です。
この流れを見て、うまくいけば一般化できるんじゃね？と思ったわけです。だって、指数入れ替えたりするだけじゃないですか。
例えば3種類を最低１つ使って $n$ 個並べる列なら、$ 3^n-3\left(2^n-2\right)-3$ みたいな感じになります。
目標は、$m$ 種類の文字を最低１つずつ使って $n$ 文字の列を作るときの場合の数を求める式を作ること。
さて、ここからサイト主が実際やっていった通りに追っていきましょう。
まず、具体例のサンプルを集めました。
途中式省略です。
２種類を $n$ 個→ $2^n-2=2\left(2^{n-1}-1\right)$
３種類を $n$ 個→
$3^n-3\left(2^n-2\right)-3=3^n{-3\times2}^n+3=3\left(3^{n-1}-2\times2^{n-1}+1\right)$ ３種類を $n$ 個→
$3^n-3\left(2^n-2\right)-3\\ =3^n{-3\times2}^n+3\\ =3\left(3^{n-1}-2\times2^{n-1}+1\right)$
４種類を $n$ 個→ $4\left(4^{n-1}-{3\times3}^{n-1}+3\times2^{n-1}-1\right)$
５種類を $n$ 個→ $5\left(5^{n-1}-{4\times4}^{n-1}+{6\times3}^{n-1}-4\times2^{n-1}+1\right)$
６種類を $n$ 個→ $6\left(6^{n-1}-{5\times5}^{n-1}+{10\times4}^{n-1}-{10\times3}^{n-1}+5\times2^n-1\right)$ ６種類を $n$ 個→ $\scriptsize6\left(6^{n-1}-{5\times5}^{n-1}+{10\times4}^{n-1}-{10\times3}^{n-1}+5\times2^n-1\right)$
この段階で、ふと見えてくるものがあります。$□^{n-1}$ の係数を見てみると、 $1^{n-1}$ の係数 , $2^{n-1}$ の係数. $3^{n-1}$ の係数, $4^{n-1}$ の係数. $5^{n-1}$ の係数の順に、
２種類のとき→　-1 +1
３種類のとき→　+1 -2 +1
４種類のとき→　-1 +3 -3 +1
５種類のとき→　+1 -4 +6 -4 +1
６種類のとき→　-1 +5 -10 +10 -5
正負の符号が変わっていますが、数字の部分にのみ注目して、角度をずらすとパスカルの三角形です。 さてさて、ここからが肝です。パスカルの三角形というのは実は場合の数と非常に仲が良いです。
例えば $ {}_4 C_2$ というのを求めたいとしましょう。すると、4+1=5段目の、2+1=３番目の数を見れば「6」と、あっという間に導き出せます。これを逆に利用したいなぁと思うわけです。 例えば５種類の場合で考えると…
\[ 5\left({}_4 C_0\times 5^{n-1}-{}_4 C_1\times4^{n-1}+{}_4 C_2\times3^{n-1}-{}_4 C_3\times2^{n-1}+{}_4 C_4\times1^{n-1} \right) \] のような感じです。ということで、$m$ 種類の文字を最低１つずつ使って $n$ 文字の列を作るときの場合の数は、 \[ m\left({}_{m-1} C_0\times m^{n-1}-{}_{m-1} C_1\times\left(m-1\right)^{n-1}+{}_{m-1} C_2\times\left(m-2\right)^{n-1}\ldots\right)\] となるわけです。
※終わりの方も書かなきゃいけないんですが、この段階では符号が確定しないので書けないです。
で、これを変形していくと、 \[ \sum_{i=1}^{m}{\left(-1\right)^{m-i}{}_m C_i i^n} \] となります。

動画

式変形の途中を見たい方のために。3分程度のゆっくり？実況です。(26MB)
ここをクリック

備考

調べてみるとどうやらこれは大学受験レベルのようです。あと、これはあくまで規則性で導き出したものなので僕にはこれを証明することはまだ無理です…。他力本願になりますが、もっと知りたい方は「高校数学の美しい物語」さんのサイトへ…
https://mathtrain.jp/zensya