平成１８年９月３０日

[流れ星]

　　　　　第1７８回数学的な応募問題解答

　　　　　　＜解答募集期間：９月１０日〜９月３０日

［完全順列］

皆さん、日常生活の出来事で完全順列という考え方はよくあります。

　

１からｎまでの番号のついている箱と球があって、１つの箱に１個の球を入れていきます。
箱の番号と球の番号がすべて異なるような場合の数を数列｛ａ_ｎ｝とするとき、次の問に答えよ。

＜水の流れ：上の青のように１０日午後９時訂正しました。＞

＜ご指摘頂いた「uchinyan」さんに最大の感謝をします。ありがとうございました。＞

問１：数列｛ａ_ｎ｝の初項から第４項まで求めてください。

問２：ａ_ｎをn　，ａ_ｎ―１，ａ_ｎ―２を用いて関係式を求めてください。

問３：数列｛ａ_ｎ―ｎａ_ｎ―１｝の一般項をｎで求めてください。

問４：箱の番号と球の番号がすべて異なる確率をPnとする。

ｎ→∞のとき、Pnの極限値求めてください。

ＮＯ１「uchinyan」9/10　14時19分受信 更新9/30
第１７８回数学的な応募問題
［完全順列］

9/10 14:00 時点での問題は、少しおかしいようです。
＞１からｎまでの番号のついている箱と球があって、１つの箱に１個の球を入れていきます。
＞箱の番号と球の番号がすべて異なる球の個数を数列｛ａｎ｝とするとき、次の問に答えよ。
「箱の番号と球の番号がすべて異なる球の個数」は、「すべて」を強調すれば a(n) = n です。
そうでない場合には、0 <= k <= n として a(n) = k でよく、決定しません。
いずれにせよ、題意が不明確で、問題として成立しません。
「箱の番号と球の番号がすべて異なるような場合の数」ならば、意味が通ります。
そこで、この解答では、
１からｎまでの番号のついている箱と球があって、１つの箱に１個の球を入れていきます。
箱の番号と球の番号がすべて異なるような場合の数を数列｛ａｎ｝とするとき、次の問に答えよ。
だと思って、以下を示します。

＜水の流れ：作成の意図は問題４を解いて、eが出てくることを知ってもらうのがねらいでした。

で、これを設問形式したところで、ご指摘のような文章になり、お詫びします。また、「uchinyan」さんに深く感謝します。＞

問１：
具体的に調べて、
a(1) = 0, a(2) = 1, a(3) = 2, a(4) = 9

問２：
a(n) は、箱 1 〜 n の番号が球 1 〜 n ｎ番号とすべて異なる場合です。
これを実現するためには、球 n を k ≠ n となる番号の箱に入れなければなりません。
これは、n-1 通りです。このとき、
残っている球は 1, 2, ..., n-1
残っている箱は 1, 2, ..., k-1, k+1, ..., n
です。これを、少し並べ替えて、
残っている球は 1, 2, ..., k-1, k+1, ..., n-1, k
残っている箱は 1, 2, ..., k-1, k+1, ..., n-1, n
と書いてみます。こうすると、球 k が箱 n に対応するようにできます。
そこで、
a) 球 k を箱 n に入れないとき
b) 球 k を箱 n に入れるとき
の二つに分けて考えることができます。
a) 球 k を箱 n に入れないとき
この場合には、一時的に、箱の番号 n を改めて k と振り直す、と考えると、
残っている球は 1, 2, ..., k-1, k+1, ..., n-1, k
残っている箱は 1, 2, ..., k-1, k+1, ..., n-1, k(実は n)
となって、箱 1 〜 n-1、球 1 〜 n-1 の場合に帰着します。これは、定義より a(n-1) 通りです。
b) 球 k を箱 n に入れるとき
この場合には、
残っている球は 1, 2, ..., k-1, k+1, ..., n-1
残っている箱は 1, 2, ..., k-1, k+1, ..., n-1
となって、一時的に、k+1 以降の番号を一つ少なく振り直すと考えると、
箱 1 〜 n-2、球 1 〜 n-2 の場合に帰着します。これは、定義より a(n-2) 通りです。
以上ですべてです。したがって、
a(n) = (n-1) * (a(n-1) + a(n-2))
になります。

問３：
a(n) = (n-1) * (a(n-1) + a(n-2))
a(1) = 0, a(2) = 1
を解くだけです。最初の式を変形して、
a(n) - n * a(n-1) = (-1) * (a(n-1) - (n-1) * a(n-2))
a(n) - n * a(n-1) = (-1)^(n-2) * (a(2) - 2 * a(1)) = (-1)^(n-2) = (-1)^n
つまり、
a(n) - n * a(n-1) = (-1)^n

問４：
箱の番号と球の番号のすべての順列の場合の数は n! です。そこで、
P(n) = a(n)/n!, P(1) = 0
です。問３：から
a(n) - n * a(n-1) = (-1)^n
なので、
a(n)/n! - n * a(n-1)/n! = (-1)^n * 1/n!
a(n)/n! - a(n-1)/(n-1)! = (-1)^n * 1/n!
P(n) - P(n-1) = (-1)^n * 1/n!
P(n) = P(1) + �納k=2,n]{(-1)^k * 1/k!}
P(n) = �納k=2,n]{(-1)^k * 1/k!} = �納k=0,n]{(-1)^k * 1/k!}
最後のところは、(-1)^0 * 1/0! + (-1)^1 * 1/1! = 0 を使っています。
�狽�具体的に書くと、
P(n) = (-1)^0 * 1/0! + (-1)^1 * 1/1! + (-1)^2 * 1/2! + ... + (-1)^n * 1/n!
ここで、天下り的ですが、右辺は、次の e^x のマクローリン展開
e^x = 1 + x/1! + x^2/2! + ... + x^n/n! + ...
の弟 n 項までになっています。証明は省略しますが、多分、この問題の趣旨でもないでしょう、
e^x の展開式はすべての実数で収束することが知られており、
e^(-1) = 1 + (-1)/1! + (-1)^2/2! + ... + (-1)^n/n! + ...
となります。この式の右辺は、lim[n->∞] P(n) なので、結局、
lim[n->∞] P(n) = e^(-1) = 1/e
になります。

(考察)
P(n)の式から明らかですが、
a(n) = n! * �納k=0,n]{(-1)^k * 1/k!} = �納k=0,n]{(-1)^k * n!/k!}
と書けます。
これは、やや直感的ですが、次のようにして、直接的にも求められます。
なお、以下では、組み合わせの数を C(n,k) などと書きます。
まず、n 個を並べるすべての順列 n! から、箱 i に球 i が入った場合、
C(n,1) * (n-1)! を除きます。
n! - C(n,1) * (n-1)!
ところがこれでは、箱 i に球 i が入り、箱 j に球 j が入った場合、
C(n,2) * (n-2)! を引き過ぎているので、これを補うために加えます。
n! - C(n,1) * (n-1)! + C(n.2) * (n-2)!
ところが今度は、箱 i に球 i が入り、箱 j に球 j が入り、箱 k に球 k が入った場合
C(n,3) * (n-3)! を足し過ぎているので、これを補うために引きます。
n! - C(n,1) * (n-1)! + C(n.2) * (n-2)! - C(n.3) * (n-3)!
．．．以下同様にして、結局、
n! - C(n,1) * (n-1)! + C(n.2) * (n-2)! - C(n.3) * (n-3)! + ... + (-1)^n * C(n,n) * 0!
つまり、
a(n) = �納k=0,n]{(-1)^k * C(n,k) * (n-k)!}
= �納k=0,n]{(-1)^k * n!/k!(n-k)! * (n-k)!}
= �納k=0,n]{(-1)^k * n!/k!}
になります。
この、「引いて足して」の繰り返しは、一般に、包除の原理というらしいのですが、
要するに、和集合で要素を数える際の計算、
n(A∪B∪C) = n(A) + n(B) + n(C) - n(A∩B) - n(B∩C) - n(A∩C) + n(A∩B∩C)
の一般化ですね。

(感想)
問題を解釈し直して解きました。これでよかったのでしょうか？
一応、解いた後で、Webで「完全順列」を検索してみたところ、私の解釈のものが出てきたので、
いいと思うのですが．．．
なお、「完全順列」は、「モントール数」、「かく乱(攪乱)順列」などともいうようですね。

＜水の流れ：学校の生活では「席替え問題」として、扱っています。
くじ引きをして、前回と同じ席に着く生徒が少なくとも１人以上いる確率は１−1/e＝０．６３　（約）いまして、数学的な確率は話してみると、何とか妥協してくれます。また、日常の中では「人間と靴」、「人間と帽子」、「手紙と宛名封筒」、「パーテイのときのお互いに行うプレゼント交換」
「テストのときボックスに異なる数字を１つずつ当てはめる問題」等生徒には話しています。＞

ＮＯ２「πP」　 9/10　16時34分受信 更新9/30
問１：初項はn=1の時？0

       第2項はn=2の時1

　　　第3項はn=3の時2

　　　第4項はn=4の時9

全て樹形図で書きました　もっと数が多いとまずは最初が１でないものを全て並べてそこから2番目が2　三番目が3・・・であるものを引けばよいのですが・・・　数が少ない時は（特に解りにくいものは）やはり樹形図ですね

 問2：どうも解りにくい　ですからとりあえず樹形図を描いて考えて見ます

 　さっき使ったn=3の時を考えて見ます　すると以下のようになります

 ２−３−１

 ３−１−２

 この２通りだけとなります　　　さてこれから解ることは・・・

まずは最初は１でないから最初の数のとり方は3-1=2通り

 また最後の数は最初の数が決まればわかるので最後の数の取り方は1通り

 よって考えるのは間の数の完全順列となりますから結局は（3-1）×（A3-2）　となるはず・・・ですがっ！どうやら問題一より不適になるようです

ですから何かが抜けてるということになります　問題文より恐らくそれはA3-1なのでしょう　試しに足してみると（3-1）×（A3-1+A3-2）＝２となりますからこれが答えとなり適当であります

しかしこれでは数学的な解き方は一切してません！　これは国語的解法です

では数を増やしてn=4の時を考えて見ます

 2-1-4-3    3-1-4-2    4-1-2-3

  -3-4-1     -4-1-2        3-1-2

 -4-1-3          2-1           -2-1

これで解るようにどうやら完全順列にはパターンが二つあって・・・

 （�@）　最初から最後までで分かれるのが一番目の時

　　　　　　これは一体いくつあるかといいますと・・・　

 　　　　　最初の数は何通りあるかは不明　しかし最初が決まれば最後も絶対その数（すなわちこの場合は4）は除かれますから結局この場合の完全順列の個数は抽象的になりますが・・・An-2通り　（この例の一つとして最初が2の順列と最初が3の順列の4−の場合を除いたものと最初が4の3-の場合を除いたもので最初と最後を除いた場合のことになります・・・タブン）

（�A）最初から最後の中で途中の分かれ方が一番目でないもの

 　　これの数はというと・・・

　　とりあえずは分かれるところを一番目としましてその完全順列の個数というのは結局は最初の数を除いたAn-1個の完全順列であります

　　この例では3を除いた3個の完全順列といえますね

 さて・・・これらは互いに背反ですから和の法則より完全順列の個数というのは結局　Aｎ＝An-2+Aｎ-1

 ではなくて・・・これに最初の数の選び方を掛けた　An＝(n-1)×（An-1+An-2)

 これが答えかな　　　この形はどうやら最初の数がわかればどんどんわかっていくというもののようですね

一応検算もしておくと・・・

 A4＝（4-1）×（A4-1+A4-2）

　　＝３×（A3＝2+A2＝1）

　　＝９

 となり適　これだけではまだ不十分（これを使って推論してきたから） A5＝４×（９+２）＝44

 一応樹形図も描いて確かめましたこれ以上は疲れましたが３　４　５　の場合が適当なのだから他もきっと・・・

＜水の流れ：「πP」さんの解き方は、最初、帰納的に調べて、そこから、規則性を発見していく考え方です。また、樹形図を書いて実際に確かめています。数学的な考えの基本です。＞

ＮＯ３「Toru」　 9/12　15時16分受信 更新9/30

問１　a1=0, a2=1, a3=2 (231,312)
　　 ,a4=9 (2143,2341,2413,3142,3412,3421,4123,4312,4321)

問２　箱nにはいっている球をk　（kは1,2,---,n-1のいずれか）とする。
　球n が箱kにはいっている場合の数は、1,2,--,k-1,k+1,--n-1　のn-2個が完全順列
の場合の数でa(n-2)
　球nが箱k以外に入っている場合の数は、球nを球kと思えば、1,2,----,n-1のn-1個
の完全順列場合の数で　a(n-1)
　k=1,2,----,n-1のいずれでも同様であるから
　an=(n-1)(a(n-1)+a(n-2))

問３　問２の漸化式を変形して、
　an-n a(n-1)=-(a(n-1)-(n-1) a(n-2))=--
-=(-1)^(n-2) (a2-2a1)=(-1)^(n-2)=(-1)^n

問４　問３の両辺をn!で割って
Pn-P(n-1) =(-1)^n/n!  , P1=0とから　n=2,3,4,----,nとして辺辺をたせば
Pn=1/2!-1/3!+1/4!-1/5!+------+(-1)^n/n!
n→∞とするとこれはe^xのテーラー展開
e^x=1+x+x^2/2!+x^3/3!+--------
においてx=-1としたものに一致するから　n→∞　の時　Pn→1/e

第１７８回問題の解答を送ります。なかなか美しい問題ですね。特に問４は解いた後
でスカッとします。　　　

＜水の流れ：「Toru」さんの解法は、綺麗で優雅さを感じます。解けた後、感想に「やったー」という充実感が表れています。＞

ＮＯ４「kashiwagi｣9/12　21時33分受信 更新9/30
178回問題

問1.一つ一つ書き出してみると、となることが分かる。

問2.上の値より試行錯誤の結果、となることが分かる。

問3.上記式を変形すると、

　　　　　　　＝

　　　　　　　＝　　となる。

問4.！であるから、上記式を！で割って全ての項を加えると、

　　　　となる。ここで　、1！＝０！＝1であるから　　　　即ち、は

　　　　であるから　　となる。

＜モメント：今回の問題は非常に面白いですね。題意に沿って計算して いくと何と自然対数のeがでてくるとは、しかしながら本当に頭の良い人がいたもんですね。凡人には発想もできません・・・・＞

＜水の流れ：解法の醍醐味を味わうことができましたか。光栄に感じます。とにかく、e　がでてきますからね。

　すっきりしたお見事な解法です。＞

ＮＯ５「三角定規｣9/18　21時４２分受信 更新9/30
＜コメント：今回の 「モンモールの問題」 は，忘れ得ぬ思い出があります。

初めての出会いは，私自身が高校3年のとき，『大学への数学』 の中の竹之内脩教授の記事においてでした。

そこには漸化式に至る一般論の記述はありませんでしたが，その神秘的な魅力は深い印象となって残りました。

大学の図書館で離散数学の本を拾い読みしたとき，偶然見つけた漸化式とその解がさらに深く印象に刻まれました。

解の詳細まで覚えている問題はそう多くはありませんが，本問はその中のひとつです。」

＜水の流れ：今回は思い出深い問題のようでして、光栄に感じます。

私の場合は教員生活６年目でして、全部違い場合の数が漸化式で表されることを

生徒に説明しながら、モンモール問題として歴史的に有名なことを話していました。＞

ＮＯ６「kasama｣　さん　9/30　00時36分受信 更新9/30

＜コメント：今回は完全順列の問題ですね。設問通りにやっていくと、うまく確率に辿り着けますが、極限値が０ではなく、ある値(1/e)に収束するところが興味深いですね。＞

問１
a₁ 0通り
a₂ (2,1) 1通り
a₃ (2,3,1),(3,1,2) 2通り
a₄ (2,1,4,3),(2,3,4,1),(2,4,1,3),(3,1,2,4),(3,4,1,2),(3,4,2,1),(4,1,2,3),(4,3,1,2),(4,3,2,1) 9通り

問２
n番目の文字は1〜n-1のn-1通りです。そこで、n番目にiを置いたものについて考えます。
�@i番目にnを並べた場合
　i番目にn、n番目にiがあるのだから、残りのn-2個所の並びは完全順列なので、a_n-2通りです。
�Ai番目にnを並べない場合
　i番目にnを並べないので、nをiと読み替えても構いません。すると、1〜n-1番目の並びは完全順列なので、a_n-1通りです。
�@、�Aとn番目の文字の並べ方がn-1通りあることより、
　a_n = (n-1)(a_n-2+a_n-1) ･･･(1)
となります。

問３
(1)式を次のように変形します。
　a_n = (n-1)(a_n-2+a_n-1)⇒a_n = (n-1)a_n-2+na_n-1-a_n-1⇒a_n-na_n-1 = -{a_n-1-(n-1)a_n-2}
すると、
　a_n-na_n-1 = (-1)¹{a_n-1-(n-1)a_n-2} = (-1)²{a_n-2-(n-2)a_n-3} = ･･･ = (-1)^n-2(a₂-2a₁) = (-1)ⁿ
よって、
　a_n-na_n-1 = (-1)ⁿ ･･･(2)
です。

問４
n個の数字の順列はn!通りなので、P_n = a_n/n!です。問３の(2)式を利用するため、Pの差分をとって、
　P_n-P_n-1 = (-1)/n･(P_n-1-P_n-2) = (-1)²/n(n-1)･(P_n-1-P_n-2) = ･･･
　= (-1)^n-2/n(n-1)･･･3･(P₂-P₁) = (-1)^n-2/n(n-1)･･･3･(1/2-0) = (-1)ⁿ/n!
となるので、
　P_n = (-1)ⁿ/n!-P_n-1 = (-1)ⁿ/n!+(-1)^n-1/(n-1)!-P_n-2 = ･･･
　= (-1)ⁿ/n!+(-1)^n-1/(n-1)!+･･･+(-1)²/2!-P₁ = {(-1)^k/k!} = {(-1)^k/k!}
となります。これは自然対数の底e^xを第n項までTaylor展開して、x=-1を代入したものですから、n→∞のとき1/e=0.367879･･･です。