『ややこしい順列』

『ややこしい順列』解答

◆愛知県　Y.M.Ojisan さんからの解答。

色、数字、筆記具の並びは互いに干渉しないので、独立に組み合わせ数を考え、掛け合わせればよい。
よって、ｍ種のものをｎ桁並べたとき、ｐ種については必ず１個以上含まれるものの組み合わせ数が一般に分かればよい。

ｍ種のうちのI番目が含まれないものの集合をX_Iで表し、
含まれるべきｐ種はI=1～ｐであるとする。
また「１」は全ての集合を　Ｎ(Ａ)は集合Ａの要素数を表すとする。

ｐ種については必ず１個以上含まれるものの集合＝ｐ
∩
I=1 （１－Ｘ_I）

であるが、これを展開したとき、各項におけるX_Iは重複しないので

∩Ｘ_I
I∈ｋ種＝Ｘ^ｋと形式的にあらわせる。

ここでＸ^ｋはｍ種のうちｋ種を含まないものの集合の１つ。

よって
Ｎ(ｐ種については必ず１個以上含まれるものの集合)＝Ｎ(（１－Ｘ）^ｐ)

Ｎ（Ｘ^ｋ）＝（ｍ－ｋ）^ｎを用いれば

(A) 色　ｍ＝７ｐ＝４

Ｃ＝ N（（１－X）⁴）
＝N（１）-４N（X）＋６N（X²）－４(Ｘ³)+Ｎ(Ｘ⁴)
=７ⁿ-４*６ⁿ+６*５ⁿ-４*４ⁿ+３ⁿ

(B) 数字　ｍ＝５ｐ＝３

Ｄ＝ N（（１－X）³）
＝N（１）-３N（X）＋３N（X²）－Ｎ(Ｘ³)
=５ⁿ-３*４ⁿ+３*３ⁿ-２ⁿ

Ｔ＝ N（（１－X）²）
＝N（１）-２N（X）＋Ｎ(Ｘ²)
=３ⁿ-２*２ⁿ+１

●答え

　Ｃ*Ｄ*Ｔ
＝（７ⁿ-４*６ⁿ+６*５ⁿ-４*４ⁿ+３ⁿ）（５ⁿ-３*４ⁿ+３*３ⁿ-２ⁿ）（３ⁿ-２*２ⁿ+１）

◆出題者のコメント

Y.M.Ojisanさん、解答ありがとうございます。
みごと正解です。

おっしゃるとおり、色,数字,筆記具は互いに他の２つの選択には拘束されずに独立して選択できます。

それに、色,数字,筆記具のそれぞれは、ｐ種類だけが許されるｎ個の順列(ｐⁿ通り)の内で、ｑ(≦ｐ)種類は必ず含む順列です。

ですから、示されたように包除原理より

_qＣ₀・ｐⁿ－_qＣ₁・(ｐ－１)ⁿ＋…＋(－１)^q・_qＣ_q・(ｐ－ｑ)ⁿ
＝ q
Σ
k=0 (－１)^k・_qＣ_k・(ｐ－ｋ)ⁿ
通りになります。

余談ですが、ここでｐ＝ｑ＝ｎとすると、明らかにｎ個の順列(_nＰ_n)です。
ですから、ｐ＝ｎ , ｑ＝ｎを上の式に代入すると、

ｎ！＝_nＣ₀・ｎⁿ－_nＣ₁・(ｎ－１)ⁿ＋…＋(－１)^n-1・_nＣ_n-1・１ⁿ
　　＝ n-1
Σ
k=0 (－１)^k・_nＣ_k・(ｎ－ｋ)ⁿ

と、なります。

ここのサイトにも、この証明を求めた問題が、『ｎ！』にありましたね。