「 図形・数の不思議」 平成１０年５月８日
＜最短シュタイナー問題とモンモール問題＝完全順列＝攪乱順列＞
- 『１』
- ある市内の４つの高校Ａ，Ｂ，Ｃ，Ｄ校はちょうど４qの正方形の各頂点にあります。この４つの高校を
- インターネットでネットワークを結ぶ計画であります。もっとも短い結び方で、何qの線が必要でしょうか。
- また、その設計図も書いてください。
- さあー、みんなで考えよう。誰が一番短いネットワークを設計するかな。
- 『２』
集合｛1,2,3,・・・,n}(n≧1)上の置換を考えます。
- ちょうどｋ（ｋ＝0,1,2,・・・,ｎ）個の不動点をもつものの個数をＭ(ｎ，ｋ)で表すことにする。
- （注：集合｛1,2,3,・・・,n}上の置換を（ａ１，ａ２，・・・，ａｎ）とするとき、
- ａｉ＝ｉを満たす要素ｉをその置換の不動点と言う。）
このとき、不動点の個数Ｍ(ｎ，ｋ)の値を表にします。
- 注： この表をモンモールの三角形と名づます。
ただし、ｎは自然数で、 ｋ＝０，１，２，３，・・・、ｎ とする。
| ｎ＼ｋ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
８ |
計 |
| １ |
0 |
1 |
|
|
|
|
|
|
|
１ |
| ２ |
1 |
0 |
1 |
|
|
|
|
|
|
２ |
| ３ | 2 | 3 | 0 | 1 | | | | | | ６ |
| ４ | 9 | 8 | 6 | 0 | 1 | | | | | 24 |
| ５ | 44 | 45 | 20 | 10 | 0 | 1 | | | | 120 |
| ６ | 265 | 264 | 135 | 40 | 15 | 0 | 1 | | | 720 |
| ７ | 1854 | 1855 | 924 | 315 | 70 | 21 | 0 | 1 | | 5040 |
| ８ | 14833 | 14832 | 7420 | 2464 | 630 | 112 | 28 | 0 | 1 | 40320 |
- すると、次の性質があります。一度証明にチャレンジしてみてください。
【１】Ｍ(ｎ，ｎ)＝１
【２】Ｍ(ｎ，ｎ−１)＝０
【３】Ｍ(ｎ，ｋ)＝Ｃ(ｎ，ｋ)× Ｍ(ｎ−ｋ,0) 、１≦ｋ≦ｎ−１
ただし、 Ｃ(ｎ，ｋ)は２項係数＜組み合わせの記号＞とする。
【４】漸化式 Ｍ(ｎ，0)＝(ｎ−１)｛ Ｍ(ｎ−１，0)＋ Ｍ(ｎ−２，0)｝、ｎ≧２
- ただし、Ｍ(1，0)=０, Ｍ(２，0)=1とする。
【５】横の行の和 (k=0,…,k=n)Ｍ(ｎ，ｋ) ＝ｎ！
【６】一般項 Ｍ(ｎ，0)＝ｎ！(k=0,…,k=n)（−１）のｋ乗÷ｋ！ <オイラーが発見>
- ただし、ｎ≧２
【７】絶対値 ｜Ｍ(ｎ，0)−Ｍ(ｎ，１)｜＝１ ・・・大小は交互
【８】一般項の確率極限 ｎ→∞のとき、 Ｍ(ｎ，0)÷ｎ！ → １÷ｅ≒０．３６７８
【９】一般項 Ｍ(ｎ，ｋ)＝ｎ！÷ｋ！(k=0,…,k=n-k)（−１）の(ｎ-ｋ)乗÷(n-ｋ)！
平成11年11月11日に、(k=0,…,k=n-k) に訂正しました。（読者の:「Tsubouchi」さんからのご指摘です。感謝！）
- ただし、ｎ≧２
ここで、ｎ＝５のとき 計算の具体例
- Ｍ(５，０) ＝120（１÷２−１÷６＋１÷24−１÷120）＝４４
- Ｍ(５，１) ＝120（１÷２−１÷６＋１÷24）＝４５
- Ｍ(５，２) ＝120÷２×（１÷２−１÷６）＝２０
- Ｍ(５，３) ＝120÷６×（１÷２）＝１０
- Ｍ(５，４) ＝120÷24×（１−１）＝０
- Ｍ(５，５) ＝120÷120×（１）＝１
【10】(k=0,…,k=n)k×Ｍ(ｎ，ｋ) ＝ｎ！
【11】(k=0,…,k=n)k×k×Ｍ(ｎ，ｋ) ＝２ｎ！
- ここで、不動点の個数ｋを確率変数Ｘとするとき、
【12】Ｘの期待値 Ｅ（Ｘ）＝１
【13】Ｘの２乗の期待値 Ｅ（Ｘの２乗）＝２
【14】Ｘの分散 Ｖ（Ｘ）＝１ ，標準偏差σ（Ｘ）＝１
- 以上のことが証明されています。このととを知っていると随分解くのに楽な問題があります。
具体的で身近な出題内容を教えてください。＜近年表現が変わっているだけで、よくこの種の入試問題があります。
これも調べて教えてください。＞
皆さん！！
自宅：mizuryu@aqua.ocn.ne.jp
Ｂａｃｋ