14:47:48

「 図形・数の不思議」 　　　　　　　平成１０年５月８日

＜最短シュタイナー問題とモンモール問題＝完全順列＝攪乱順列＞

『１』

　ある市内の４つの高校Ａ，Ｂ，Ｃ，Ｄ校はちょうど４�qの正方形の各頂点にあります。この４つの高校を

　インターネットでネットワークを結ぶ計画であります。もっとも短い結び方で、何�qの線が必要でしょうか。

　また、その設計図も書いてください。

さあー、みんなで考えよう。誰が一番短いネットワークを設計するかな。

『２』

　集合｛1,2,3,・・・,n}(n≧1)上の置換を考えます。

　ちょうどｋ（ｋ＝0,1,2,・・・,ｎ）個の不動点をもつものの個数をＭ(ｎ，ｋ)で表すことにする。

（注：集合｛1,2,3,・・・,n}上の置換を（ａ１，ａ２，・・・，ａｎ）とするとき、

ａｉ＝ｉを満たす要素ｉをその置換の不動点と言う。）

このとき、不動点の個数Ｍ(ｎ，ｋ)の値を表にします。

注： この表をモンモールの三角形と名づます。

ただし、ｎは自然数で、 ｋ＝０，１，２，３，・・・、ｎ とする。

すると、次の性質があります。一度証明にチャレンジしてみてください。

【１】Ｍ(ｎ，ｎ)＝１
【２】Ｍ(ｎ，ｎ−１)＝０
【３】Ｍ(ｎ，ｋ)＝Ｃ(ｎ，ｋ)× Ｍ(ｎ−ｋ,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×（１）＝１

ここで、不動点の個数ｋを確率変数Ｘとするとき、

【12】Ｘの期待値 Ｅ（Ｘ）＝１
【13】Ｘの２乗の期待値 Ｅ（Ｘの２乗）＝２
【14】Ｘの分散 Ｖ（Ｘ）＝１ ，標準偏差σ（Ｘ）＝１

以上のことが証明されています。このととを知っていると随分解くのに楽な問題があります。

具体的で身近な出題内容を教えてください。＜近年表現が変わっているだけで、よくこの種の入試問題があります。 これも調べて教えてください。＞

皆さん！！　　どしどし問題を送ってください。
自宅：mizuryu@aqua.ocn.ne.jp

Ｂａｃｋ