Weekend Mathematics／コロキウム室／テーマ別 ／2.プレゼントの問題



コロキウム室(プレゼントの問題)


NO.72　　　　 4/2 　　MK142857 プレゼントの問題（１）

僕は、数学オリンピックに出てみようと思って、 この前、英才セミナーを受けてみました。 その時に出た問題の中で、面白い問題があったので送ります。

問題　

あるパーティーに参加する６人の友達が各自１つずつ 用意したプレゼントを交換し合うことになりました。 このとき、自分自身の用意したプレゼントをもらう人が １人もいないようなプレゼント交換のし方は、 何通りあるでしょうか。



NO.74　　　　 4/3 　　Junko　 プレゼントの問題（２）

Ｎ人でプレゼントを交換し合うとします。
自分自身の用意したプレゼントをもらう人が １人もいないようなプレゼント交換のし方が、 ｆ(Ｎ)通りあるとします。
ｆ(６)の値を求めればいいわけです。
Ｎ＝２から順番に考えてみました。
それぞれの人数で単独の仲間はずれが出ないように チェ−ンを作る（手をつないで輪を作る）にはどうしたらよいか と考えました。





　　　　　　　　　　

NO.75　　　　 4/3 　　みかん　 プレゼントの問題（３）

べつかい、別かい？　別解

６人がプレゼントをする全ての場合は６！＝７２０通り

ゆえに　自分のプレゼントを受け取らない方法は
７２０−（１＋１５＋４０＋１３５＋２６４）＝２６５
であるから、２６５通りとなる。
円順列というようなしゃれたものは使いませんでしたが 同じ結果となりました。
この方法は結局ランクを一つ下げて計算をする方法なので、 数式上の表現が面倒である。
この問題は「５人が交換する方法」を求めることであり、 そして「４人が交換する方法」を求めること・・ ・・。
　 しかし、計算は前のことを使えるので案外簡単でした。



　　　　　　　　　

NO.76　　　　 4/4 　　水の流れ　 プレゼントの問題（４）

ＭＫ１４２８５７さんのプレゼント問題ですが、 これは「完全順列」または、モンモール問題と 言いまして、一般にｎ人の場合のときまで、考えられます。
ご存じとは思いますが、ｎ人について、 １人も自分自身の用意したプレゼントをもらわない方法を、 f(n)とすると、
f(1)=0,f(2)=1で、
漸化式：f(n)=(n-1){f(n-2)+f(n-1)}で、表現できています。
私自身教員７年目のとき、知ってそれ以来、 機会あることに教えています。
だから、f(3)=2(0+1)=2,f(4)=3(1+2)=9,f(5)=4(3+9)=44
f(6)=5(9+44)=265通りです。

また、ｊ人だけが自分のプレゼントをもらう場合も、 考えられます。 (j=0,1,2,3,・・・,n)　だから、 n=6,j=0のときが出題されたことになります。

さらに、ｎ人とも自分自身のプレゼントをもらわない確率 は１／ｅ（ｅは超越数）約３６．８％位（訂正）です。
これは、関数ｅのx乗のマクロニー展開で証明されます。
私の場合は、席替えのとき、少なくとも１人以上の人が、 前と同じ席になる確率は約６３％くらいあるのだから、 我慢しなさい。と言って生徒にはよく話します。



　　　　　　

NO.77　　　　 4/4 　　みかん　 プレゼントの問題（５）

NO.76に、 「また、ｊ人だけが自分のプレゼントをもらう場合も、 考えられます。(j=0,1,2,3,・・・,n) だから、n=6 ,j=0のときが出題されたことになります。」
　 とありますが、それではn とj の入った場合はどうなるのでしょうか。




　　　　　　

NO.78　　　　 4/4 　　Junko　 プレゼントの問題（６）

ｎ人でプレゼントを交換し合うとします。
自分自身の用意したプレゼントをもらう人が １人もいないようなプレゼント交換の仕方が、 ｆ(ｎ)通りあるとします。

またｎ人のうち、ｊ人だけが自分自身のプレゼントを もらう場合の交換の仕方が、ｇ(ｎ，ｊ)通りあるとします。
このｇ(ｎ，ｊ)について考えます。
ｎ人のうち、自分自身のプレゼントを もらうｊ人を選びます。
これが、ｎＣｊ通り。
残った(ｎ−ｊ)人については、 自分自身の用意したプレゼントをもらう人が １人もいないような交換の仕方をするわけですから、
ｆ(ｎ−ｊ)通り
従って、
ｇ(ｎ，ｊ)＝ｎＣｊ×ｆ(ｎ−ｊ) ではないでしょうか。

特に、ｇ(ｎ，０)＝ｎＣ０×ｆ(ｎ−０)
　　　　　　　　＝ｆ(ｎ)
となります。



　　　　　　

NO.79　　　　 4/6 　　Junko　 プレゼントの問題（７）

ところで、
漸化式：f(n)=(n-1){f(n-2)+f(n-1)} で表現できるのはなぜなのでしょうか？
さらに、これを解いて一般項を求められるのでしょうか？



NO.81　　　　 4/8 　　水の流れ　 プレゼントの問題（８）

小島先生　こんにちわ
ｇ（ｎ、ｊ）の値を表にしました。 ２０年前、この表を作って、有頂天になって、 黒板に書いた思いでがあります。

モンモールの三角形
ｎ＼ｊ０１２３４５６７計
１０１      １
２１０１     ２
３２３０１    ６
４９８６０１   ２４
５４４４５２０１００１  １２０
６２６５２６４１３５４０１５０１ ７２０
７１８５４１８５５９２４３１５７０２１０１５０４０
８         

ｇ（ｎ，０）とｇ（ｎ，１） との差が ご覧のように常に１のように思います。
さらに、その大小が交互にきています。 ｇ（ｎ，ｎ）＝１ ，ｇ（ｎ，ｎ−１）＝０，ｇ（ｎ，ｊ）＝ｎＣｊ×ｇ（ｎ−ｊ，０）
などの性質があるよと言ってあります。
だから、パスカルの三角形にちなんで、 モンモールの三角形と言ったものです。 実に、懐かしい。



　　　　　　

NO.82　　　　 4/9 　　MK142857　 プレゼントの問題（９）

今晩は。僕の解き方を紹介します。

友達の人数がｎ人のときのプレゼント交換のし方の数をｆ(ｎ)で表します。
ｎ＝１のときには、題意を満たすプレゼント交換はできないので、ｆ(１)＝０。
また、ｎ＝２のときには、２人の友達が互いに他のプレゼントをもらう場合しかないので、ｆ(２)＝１。

次に友達の人数が(ｎ＋２)人のときについて考えます。
(ｎ＋２)人の友達をそれぞれ
Ａ１、Ａ２、Ａ３・・・・ Ａｎ＋２で表します。
Ａ１がＡ２のプレゼントをもらう場合の数の ｎ＋１倍がｆ(ｎ＋２)となるので Ａ１がＡ２のプレゼントをもらう場合を考えます。

１、２より、
ｆ(ｎ＋２)＝（ｎ＋1）{ ｆ(ｎ＋１)+ ｆ(ｎ)｝・・・・（１）
が成り立ちます。
（１）と、ｆ(１)＝０, ｆ(２)＝１を用いてｆ(６)を求めることもできますが、 もう少し計算を簡単にすることを考えます。

（１）の両辺から（ｎ＋２）ｆ(ｎ＋１)引くと、
ｆ(ｎ＋２)−（ｎ＋２）ｆ(ｎ＋１)＝−｛ｆ(ｎ＋１)−（ｎ＋1）ｆ(ｎ)｝
また、ｆ(２)−２ｆ(１)＝１
これより、数列｛ ｆ(ｎ＋１)−（ｎ＋1）ｆ(ｎ)｝は、
初項が１、項比が−１の等比数列となり、
ｆ(ｎ＋１)−（ｎ＋1）ｆ(ｎ)＝（−１）（ｎ−１）
即ち、 ｆ(ｎ＋１)＝（ｎ＋1）ｆ(ｎ)＋（−1）（ｎ−１）
従って、数列はｆ(ｎ)漸化式
ｆ(１)＝０、ｆ(ｎ＋１)＝（ｎ＋1）ｆ(ｎ)＋（−1）（ｎ−１）・・・（２）
によって定まる数列とも言えるわけで、 この式を利用した方が、計算が簡単になります。
また、最近分かったことですが、ｎの値を限りなく大きくしていくと、 ｎ人がプレゼント交換をしたときに全員が 他の人のプレゼントをもらう確率は限りなく １／e＝0,367879441・・・に近づきます。

完全順列に関する面白い問題をもう一つ作ったので紹介します。

問題

A君は、あるテストの問題を考えています。 その問題は、５つの空欄のあ る文章の空欄に入る語句を５つの選択肢の中から選んで答える問題です。 問題には、同じ語句を二度以上用いてはならない、 と書いてあるため、５つの空欄には、 全て異なる語句が入ることになります。 A君は、ちっとも勉強していなかったため、 直感で答えを書くしかありませんが、次の２つの方法のうち、 どちらの書き方をした方が得でしょうか。

  1. ５つの空欄に全て同じ選択肢を書く。
  2. ５つの空欄に全て異なる選択肢を書く。
　



　　　　　　

NO.83　　　　 4/12 　　水の流れ　 プレゼントの問題（１０）

ｆ(ｎ)の一般項です。
数列はｆ(ｎ)漸化式
ｆ(１)＝０、ｆ(ｎ＋１)＝（ｎ＋1）ｆ(ｎ)＋（−1）（ｎ−１）
で定まります。 NO.82で、「MK142857」さんが示してくれています。（２）の式です。
これより、
ｆ(ｎ＋１)−（ｎ＋1）ｆ(ｎ)＝（−1）（ｎ−１）

ここで、ａｎ＝ｆ(ｎ)／ｎ！とおくと、

ａｎ＋１−ａｎ＝ｆ(ｎ＋１)／(ｎ＋1)！−ｆ(ｎ)／ｎ！
　　　　　　＝１／(ｎ＋1)！×{ｆ(ｎ＋１)−(ｎ＋１)×ｆ(ｎ)}
　　　　　　＝１／(ｎ＋1)！×（−1）（ｎ−１）

従って、階差数列の公式により。
ａ１＝ｆ(１)／１！＝０

ｎ≧２にたいしては、
ａｎ＝ａ１＋Σ(k=1..n-1)(−１)ｋ−１×｛１／(ｋ＋1)！｝
　　＝Σ(k=1..n-1)(−１)ｋ−１×｛１／(ｋ＋1)！｝
（Σの書き方が不自然でごめんなさい・・・junko）
つまり、
ｆ(１)＝０

ｎ≧２にたいしては、
ｆ(ｎ)＝ｎ！×ａｎ
　　　＝ｎ！×Σ(k=1..n-1)(−１)ｋ−１×｛１／(ｋ＋1)！｝
というわけです。


次にｎがだんだん大きくなると、ｆ(ｎ)が１／ｅに近づくことです。

ａｎ＝ｆ(ｎ)／ｎ！
　＝Σ(k=1..n-1)(−１)ｋ−１×｛１／(ｋ＋1)！｝
　＝１／２！−１／３！＋１／４！−１／５！＋・・・＋(−１)ｎ×１／ｎ！（訂正4/16）
一方、ｅｘのマクロ−リン展開によれば、
ｅｘ＝１＋ｘ＋ｘ２／２！＋ｘ３／３！＋ｘ４／４！＋・・・＋ｘｎ／ｎ！＋・・・
なので、ｘ＝−１とすれば、
ｅｘ＝１／２！−１／３！＋１／４！−１／５！＋・・・＋(−１)ｎ×１／ｎ！＋・・・（訂正4/16）

（これは、大学の１年で勉強します。・・・junko注）


従って、


lim(n→∽)ｆ(ｎ)／ｎ！＝lim(n→∽){１／２！−１／３！＋１／４！−１／５！＋・・・＋(−１)ｎ×１／ｎ！＋・・・}（訂正4/16）
　　　　　　　　　　　＝１／ｅ



となります。


これは、手元にあったある研究冊子にありました。














  

NO.84　　　　 4/12      　　Junko　   プレゼントの問題（１１）

NO.82で、「MK142857」さんから出題された
問題について考えてみました。

高校生らしい現実的な問題ですね。

期待値で比較をします。


    

  1. ５つの空欄に全て同じ選択肢を書く。
    
この解答の仕方では、必ず１題は正解となりますが、
それ以外は確実に得点できません。
    
従って、こちらの期待値をＥ１(n=5)とすると、
    
Ｅ１(n=5)＝１となります。
    


  2. ５つの空欄に全て異なる選択肢を書く。
    
こちらの期待値をＥ２(n=5)とします。
    
５つの選択肢をでたらめに並べるとその並べ方は、
    
５！＝１２０通りあります。
    
ｎ個のうちｊ個だけが正解で、
それ以外は不正解な場合がｇ(ｎ，ｊ)通りあるとします。
    
NO.81で、「水の流れ」さんが作ってくださった、
モンモールの三角形
を利用しました。
    


    Ｅ２(n=5)＝５×ｇ(５，５)／１２０＋４×ｇ(５，４)／１２０＋３×ｇ(５，３)／１２０
　　　　　＋２×ｇ(５，２)／１２０＋１×ｇ(５，１)／１２０＋０×ｇ(５，０)／１２０
　　
　　　　＝５×１／１２０＋４×０／１２０＋３×１０／１２０＋２×２０／１２０＋１×４５／１２０＋０×４４／１２０
　　　
　　　　＝(５＋３０＋４０＋４５)／１２０

　　　　＝１

    



というわけで、Ｅ１(n=5)＝Ｅ２(n=5)＝１という結果になりました。

ただし、「２」の解答の仕方の方がギャンブル性が高いということはいえますね。

　　

ところで、Ｅ２(n=5)＝１というのことですが、
これはｎ＝５の場合に限った話しではないのではないかと思います。

NO.81で、「水の流れ」さんが作ってくださった、
モンモールの三角形
でｎ＝７まで確認してみました。

一般に、


Ｅ２(n)＝Σ(k=0..n)ｋ×ｇ(ｎ，ｋ)／ｎ！

　　　＝Σ(k=1..n)ｋ×ｇ(ｎ，ｋ)／ｎ！
　
　　　＝１


が言えるのではないかと思い、その証明を試みました。



まず、NO.81で、「水の流れ」さんが作ってくださった、
モンモールの三角形の
一番右の合計をみてください。

これは結局ｎ個のものの並べ方ですから、ｎ！になっています。

つまり、

　ｇ(ｎ，０)＋ｇ(ｎ，１)＋ｇ(ｎ，２)＋・・・＋ｇ(ｎ，ｎ)

＝Σ(k=0..n)ｇ(ｎ，ｋ)

＝Σ(k=0..n)ｎＣｋｆ(ｎ−ｋ)

　(NO.78のｇ(ｎ，ｋ)＝ｎＣｋｆ(ｎ−ｋ)より)

＝ｎ！・・・（３）


ということです。これを証明で使います。



さて、

Ｅ２(n)＝０×ｇ(ｎ，０)／ｎ！＋１×ｇ(ｎ，１)／ｎ！＋２×ｇ(ｎ，２)／ｎ！＋・・・＋ｎ×ｇ(ｎ，ｎ)／ｎ！
　　
　　　＝Σ(k=0..n)ｋ×ｇ(ｎ，ｋ)／ｎ！

　　　＝Σ(k=1..n)ｋ×ｇ(ｎ，ｋ)／ｎ！

　　　＝Σ(k=1..n)ｋ×ｎＣｋｆ(ｎ−ｋ)／ｎ！

　　　＝Σ(k=1..n)ｋ×ｎ！／{ｋ！×(ｎ−ｋ)！}×ｆ(ｎ−ｋ)／ｎ！

　　　＝Σ(k=1..n)１／{(ｋ−１)！×(ｎ−ｋ)！}×ｆ(ｎ−ｋ)

　　　＝Σ(k=1..n)(ｎ−１)！／{(ｋ−１)！×(ｎ−ｋ)！}×ｆ(ｎ−ｋ)／(ｎ−１)！

　　　＝Σ(k=1..n)ｎ−１Ｃｋ−１×ｆ(ｎ−ｋ)／(ｎ−１)！

　　　＝１／(ｎ−１)！×Σ(k=1..n)ｎ−１Ｃｋ−１×ｆ(ｎ−ｋ)

　　　　ここで、Σの変数ｋを１つずらします。

　　　＝１／(ｎ−１)！×Σ(k=0..n-1)ｎ−１Ｃｋ×ｆ(ｎ−１−ｋ)

　　　　さらに、（３）の式　

　　　　Σ(k=0..n)ｎＣｋｆ(ｎ−ｋ)＝ｎ！

　　　　のｎを(ｎ−１)で置き換えると
、
　　　　Σ(k=0..n-1)ｎ−１Ｃｋｆ(ｎ−１−ｋ)＝(ｎ−１)！

　　　　となるので、　

　　　＝１／(ｎ−１)！×(ｎ−１)！

　　　＝１


となります。












  

NO.85　　　　 4/13      　　Junko　   プレゼントの問題（１２）

NO.81で、
「水の流れ」さんが ｇ(ｎ，ｊ)の表に関して、

「ｇ（ｎ，０）とｇ（ｎ，１）  との差が
常に１のように思います。
さらに、その大小が交互にきています。」
とかいていらっしゃいます。
これの裏付けをしました。




　ｇ(ｎ，０)−ｇ(ｎ，１)

＝ｎＣ０×ｆ(ｎ)−ｎＣ１×ｆ(ｎ−１)

＝ｆ(ｎ)−ｎ×ｆ(ｎ−１)



ここで、NO.82で、
「MK142857」さんが示してくださった

ｆ(ｎ＋１)＝（ｎ＋1）ｆ(ｎ)＋（−1）（ｎ−１）・・・（２）

この式において、ｎ＋１をｎで置き換えると、

ｆ(ｎ)＝ｎ×ｆ(ｎ−１)＋（−1）（ｎ−２）となります。

従って、

　ｇ(ｎ，０)−ｇ(ｎ，１)

＝(−1）（ｎ−２）

＝(−1）ｎ


よって、ｎの偶奇により１または−１となるわけです。













  

NO.94　　　　 4/21      　　水の流れ　   プレゼントの問題（１３）

Ｅ２(n)＝１の証明を書きます。

集合｛1,2,3,・・・,n}(n≧1)上の置換を考えます。
ちょうどｊ（ｊ＝0,1,2,・・・,ｎ）個の不動点を
もつものの個数をｇ(ｎ，ｊ)で表すことにする。

（注：集合｛1,2,3,・・・,n}上の置換を
（ａ１，ａ２，・・・，ａｎ）とするとき、
ａｉ＝ｉを満たす要素ｉをその置換の
不動点と言う。）

このとき、Σ（j=0...j=n)ｊ× ｇ(ｎ，ｊ) ＝ｎ！　　　を証明します。

ｊ× ｇ(ｎ，ｊ) は、不動点の総数を表しています。


       

証明

 集合｛1,2,3,・・・,n}上の置換は全部でｎ！通りああります。

それらをｆ１，ｆ２，ｆ３、・・・、ｆｎ！  とします。

写像 ｆｋ(i)で置換ｆｋ による
ｉの像を下記のように並べます。


                　　　　　　　　　　　　　　　　　 例　ｎ＝３のとき
          
         1列 　 2列  ・・・  　 ｎ列               　　　１,２,３
ｆ１　：（ａ１１ ａ１２　・・・　ａ１ｎ)　　　　  ｆ１：　(@,A,B)
ｆ２　：（ａ２１ ａ２２  ・・・　ａ２ｎ)　    　  ｆ２：　(@,３,２,)
 　   ・                                   　　  ｆ３：  (２,１,B)
      ・                           　　　　　　  ｆ４：　(２,３,１)
      ・                                   　　  ｆ５：　(３,１,２)
ｆｎ！：(ａｎ！１ａｎ！２　　・・・　ａｎ！ｎ )   　ｆ６：　(３,A,１)
            ↑    ↑            　　↑                　　↑ ↑ ↑  
          (n-1)! (n-1)! ・・・  　 (n-1)!            　  2個2個2個
                                                 



ここで、１列を考えると、像が@である個数は
１以外の(n−1)個を並べた個数、
すなわち、（ｎ−１）！に等しい。

２列を考えると、像がAである個数は
２以外の(n−1)個を並べた個数、(ｎ−１）！に等しい。
・・・・

ｎ列を考えると、像がｎであるのは
ｎ以外の(n−1)個を並べた個数、(ｎ−１）！に等しい。

よって、不動点の総数は、ｎ×(ｎ−１)！＝ｎ！

すなわち、 Σ（j=0...j=n)ｊ× ｇ(ｎ，ｊ) ＝ｎ！

　
したがって、

Ｅ２(n)＝ Σ（j=0...j=n)ｊ× ｇ(ｎ，ｊ) ／ｎ！
       ＝１　
　　　　　　　　　　　　　　　　　　　証明終

　

＊不動点の総数を今までは、横で数えていましたが、
この証明は縦方向で数えました。













  

NO.100　　　　 5/9      　　水の流れ　   プレゼントの問題（１４）

 集合｛1,2,3,・・・,n}(n≧1)上の置換を考えます。
ちょうどｋ（ｋ＝0,1,2,・・・,ｎ）個の不動点をもつものの
個数をｇ(ｎ，ｋ)で表すことにする。

（注：集合｛1,2,3,・・・,n}上の置換を
（ａ１，ａ２，・・・，ａｎ）とするとき、
  ａｉ＝ｉを満たす要素ｉをその置換の不動点と言う。）

このとき、Σ（k=0...k=n)ｋ２× ｇ(ｎ，k) ＝２ｎ！　　をまず証明します。




　Σ（k=0...k=n)ｋ２× ｇ(ｎ，k)  
＝Σ（k=1...k=n)ｋ２× ｇ(ｎ，k)
＝Σ（k=1...k=n)ｋ×ｋ× ｎＣｋ×ｆ(ｎ−k)
　　　　　　　　　　　　注１　
＝Σ（k=1...k=n)ｋ×ｋ× ｎ！／｛ｋ！×(ｎ−ｋ)！｝×ｆ(ｎ−k)
＝Σ（k=1...k=n)ｋ×ｎ×( ｎ−１)！／｛(ｋ−１)！×(ｎ−ｋ)！｝×ｆ(ｎ−k)
＝Σ（k=1...k=n)ｋ×ｎ× ｎ−１Ｃｋ−１×ｆ(ｎ−k)　　　　　　　　　　
＝Σ（k=1...k=n)ｋ×ｎ× ｇ(ｎ−１，k−１)
＝ｎΣ（k=1...k=n)ｋ× ｇ(ｎ−１，k−１)　
＝ｎ｛Σ（k=1...k=n)（ｋ−１）×ｇ(n−1，k−1)＋ Σ（k=1...k=n)ｇ(n−1，k−1)}
＝ｎ｛Σ（k=0...k=n-1)ｋ×ｇ(n−1，k)＋ Σ（k=0...k=n-1)ｇ(n−1，k)}
　　注２　　　　　　　　　　　　　　　　　　注３
＝ｎ｛(ｎ−１)！＋(ｎ−１)！｝
＝２ｎ！ 





注１：NO.78のｇ(ｎ，ｋ)＝ｎＣｋｆ(ｎ−ｋ)より)




注２：NO.94のΣ（k=0...k=n)ｋ×ｇ(n，k)＝ｎ！より




注３：不動点の総数Σ（k=0...k=n)×ｇ(n，k)＝ｎ！より




そして、不動点の個数をＸ（Ｘ＝０，１，２，・・・，ｎ）とし、
Ｘを確率変数とみると、
期待値Ｅ（Ｘ）＝１・・・＜NO.94ですでに証明済み ＞

さらに、 標準偏差σ（Ｘ），分散Ｖ（Ｘ）とすると

Ｖ（Ｘ）＝Ｅ（Ｘ２）−｛Ｅ（Ｘ）｝２  で　

σ（Ｘ）＝√ V(X)　の公式から


 Ｅ（Ｘ２）＝ Σ（k=0...k=n)ｋ２× ｇ(ｎ，k)／ｎ！
　　＝２ｎ！／ｎ！＝２


よって、

 Ｖ（Ｘ）＝Ｅ（Ｘ２）−｛Ｅ（Ｘ）｝２ 
　　　　 ＝２−１２＝１ 

 σ（Ｘ）＝√ V(X) ＝１




 感想：この確率変数Ｘは 期待値と標準偏差がともに１となった。
これには何か意味があるのだろうか。
他にまだ、調査研究することがあるのだろうか。
解明していない。

更に、

Σ（k=0...k=n)ｋ３× ｇ(ｎ，k)＝５ｎ！  

Σ（k=0...k=n)ｋ４× ｇ(ｎ，k)＝１５ｎ！ 
 
 と、予想できます。証明はまだやっていません。

この証明は時間があれば、挑戦したいです。
これは何を意味するか分かりませんが。











　
  

NO.106　　　　 5/29      　　ヴァ−　　　　プレゼントの問題（１５）


このまえの水の流れさんの結果から次のような関係があると予想できます。

	Σ(k=0...n)km×g(n,k)=h(m)×n!

ここで、h(m)に関して次の漸化式が成立することを証明します。





[証明]

m=0のときは、不動点の総数を考えることになりますが、

これは、すでに証明済みです。


m＞0のときは、





h(k)×n!=Σ(k=0...n)km×g(n,k)


        =Σ(k=1...n)km×g(n,k)


        =Σ(k=1...n)km×nCk×f(n-k)


        =Σ(k=1...n)km×n!/{k!(n-k)!}×f(n-k)


        =Σ(k=1...n)km-1×n×(n-1)!/{(k-1)!(n-k)!}×f(n-k)


        =Σ(k=1...n)km-1×n×n-1Ck-1×f(n-k)


        =Σ(k=1...n)km-1×n×g(n-1,k-1)


        =n×Σ(k=1...n)km-1×g(n-1,k-1)


        =n×Σ(k=0...n-1)(k+1)m-1×g(n-1,k)


        =n×Σ(k=0...n-1){g(n-1,k)×Σ(i=0...m-1)m-1Ci×ki}


	 =n×Σ(i=0...m-1){m-1Ci×Σ(k=0...n-1)ki×g(n-1,k)}


	 =n×Σ(i=0...m-1){m-1Ci×h(i)×(n-1)!}


        =n!×Σ(i=0...m-1)h(i)×m-1Ci





両辺をn!で割れば証明したい式が得られます。


ところで、このh(m)は統計学で言う「(原点のまわりの)m次のモーメント」です。

このモーメントを先の式を使ってmの値に応じて順番に計算すると

次のように変化します。




  m            h(m)


  0	       1


  1	       1


  2	       2


  3	       5


  4	      15


  5	      52


  6	     203


  7	     877


  8	    4140


  9	   21147


 10	  115975
















  



NO.644
'99  11/1水の流れプレゼントの問題（１６）



皆さんは、プレゼントの問題（９）
の中にある次のような問題をご存じでしたか。



問題

A君は、あるテストの問題を考えています。
その問題は、５つの空欄のある文章の空欄に入る語句を５つの選択肢の中から選んで答える問題です。
問題には、同じ語句を二度以上用いてはならない、と書いてあるため、
５つの空欄には、全て異なる語句が入ることになります。
 A君は、ちっとも勉強していなかったため、直感で答えを書くしかありませんが、
次の５つの方法のうち、どちらの書き方をした方が得でしょうか。





いわゆる正解数の期待値を求めてください。









  



NO.923
2001.1.10.qthumanプレゼントの問題（１７） 



(一部訂正1/12)


プレゼント交換の問題で少し加わった問題がありました。


円卓に８人座っています。この８人でプレゼント交換するのです
が、自分のプレゼントはもらうことはできず、しかも右隣の人に渡す事ができないとします。
このとき何通りの交換の仕方があ
るでしょう。

また一般的にｎ人の場合についてはどうでしょう。













戻る