「A,B,…のn人がそれぞれ a,b,… という
異なるカードを持っていたとする。
カードをシャッフルして再び配ったとき
始め持っていたカードと同じカードを持っている人が
一人もいないときの場合の数はいくつか?」
という問題を最近考えています。

n人のときの場合の数を a[n] としたとき
 a[1] = 0、a[2] = 1、a[3] = 2、…
といった具合で、自分なりに漸化式
 a[n] = (n!) - ( Σa[k]*nC(n-k) ) - 1  …(※)
   (Σは k=1 から k = n-1 までの和、nC(n-k) はCombination)
にたどり着きました。

そこで、一般項を求めようとしましたがうまくいかず、
(※)からの類推で
 a[n] = n*a[n-1] - 1  n:odd  …(1)
 a[n] = n*a[n-1] + 1  n:even  …(2)
らしいことがわかりました。
■質問1■(※)式と(1),(2)式は同じものでしょうか?
■質問2■この数列の一般項はどのようになりますか?

また、a[n] を n! で割ったものは
誰一人もとと同じカードを持っていない確率になりますが、
これが n→∞ で 1/e に収束しているようなのです。
■質問3■この命題は正しいでしょうか?

暇なときで構いませんので、よろしくお願いします。

A 回答 (5件)

すでにNo.1で参考URLが出ているのですが、おもしろい問題だなと思ったので、自分でも考えてみました。

参考URLに載っていた漸化式a[n]=(n-1)(a[n-1]+a[n-2])についてはいまのところよくわからないのですが、rynさんのやり方ならわかったので回答してみます。

まず(※)の式ですが、便宜上a[0]=1としますと、
n!=ΣnCk*a[k] (Σはk=0~nについての和)
と書くと意味がよくわかります。その意味は、
1からnまでの自然数の並び替えの総数はn!だが、
これは、n個の中からk個の数字を選んで、それらのみを完全に並び替えるような並び替えの総数 nCk*a[k] を、kが0からnまですべてについて和をとったものと同じである、ということです。この等式をE(n)と書くことにします。
 n!=ΣnCk*a[k]・・・E(n)


質問1の回答:
(1)、(2)の式はまとめると、
a[n]=n*a[n-1]+(-1)^n
と書けることに注意してください。それを計算の都合上、
a[n]-n*a[n-1]=(-1)^n・・・(3)
と書いておきます。
E(n) から(3)が導かれることを示します。
E(n)-n*E(n-1) を辺々計算すると、
n!-n*(n-1)!=Σ^{n}nCk*a[k]-n(Σ^{n-1}(n-1)Ck*a[k])
0 = Σ^{n}nCk*a[k]-Σ^{n-1}(n*(n-1)Ck)*a[k]
0 = Σ^{n}nCk*a[k]-Σ^{n-1}(nC(k+1))*(k+1)*a[k]
0 = Σ^{n}nCk*a[k]-Σ^{n}(nCk)*k*a[k-1]
0 = Σ^{n}nCk*(a[k]-k*a[k-1])
を得ます。和はk=0~nです。ここで、簡単のため、x[k]=a[k]-k*a[k-1] とおきますと、この式は、
 0 = Σ^{n}nCk*x[k]
となります。これをnが0からnまでに渡って考えて、次のように全部で n+1個の等式を用意する。
 Σ^{0}0Ck*x[k] = 0
 Σ^{1}1Ck*x[k] = 0
 ・・・・・・・
 ・・・・・・・
 Σ^{n}nCk*x[k] = 0
これは、未知数が、x[0],x[1],x[2],...,x[n]、の連立1次方程式で、上から順に未知数の数が1個、2個、3個、…と増えて行ってます。係数はすべて0ではないので、この連立方程式は、ただ一つの解しか持ちません。さて、ここで、2項展開の公式から次の式が成り立つのはご存知だと思います。
 Σ^{n}nCk*(-1)^k = (1-1)^n = 0
これはどんなnについても成り立ちますから、(-1)^kが上の連立方程式の解であることがわかります。よって、
 x[k]=(-1)^k、すなわち、a[k]-k*a[k-1]=(-1)^k
が成り立ちます。これで(3)が導かれました。


質問2の回答:
a[n]-n*a[n-1]=(-1)^n の両辺を n! で割ります。
(a[n]/n!)-(a[n-1]/(n-1)!) = ((-1)^n)/n!
が得られます。これは階差数列の形なので、
a[n]/n! = a[0]/0! + Σ_{1}^{n}(-1)^k/k!
a[0]=1 だったので、
a[n]/n! = Σ_{0}^{n}(-1)^k/k!
と書き直せます。よって、求める一般項は、
a[n]=n!Σ_{0}^{n}(-1)^k/k!
となります。

No.1の参考URLでも書いてあるように、a[n]/n!は、指数関数e^{x}のべき級数展開のn次の項までの式にx=-1を代入したものになっています。したがって、nが無限に大きくなると、e^{-1}=1/e に近づきます。

あとは、No.1の参考URLに出てきた漸化式a[n]=(n-1)*(a[n-1]+a[n-2])がどうして出てくるのかがわかれば完璧なのですが、ちょっとすぐにはわからなかったので、No.1の方教えてください^^;。ちなみに、a[n]=(n-1)*(a[n-1]+a*[n-2])から、(3)の漸化式はつぎのように導きます。
a[n]=(n-1)*(a[n-1]+a[n-2])
a[n]-n*a[n-1]=-a[n-1]+(n-1)*a[n-2]
a[n]-n*a[n-1]=-{a[n-1]-(n-1)*a[n-2]}
=・・・・・・=(-1)^{n-1}(a[1]-a[0])=(-1)^n
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

今、時間がありませんので後でじっくり読ませていただきますね。
それから、
 a[n]=(n-1)*(a[n-1]+a*[n-2])
のほうの解釈も何とか理解できましたので、
あとで補足にでも書かせていただきます。
kony0 さんのほうが早いかな?

お礼日時:2003/10/14 15:59

すでにみなさん解釈が終わっているそうですが、漸化式の導き方は以下のとおり。



数列x[i]: i=1~nは、1~nまでの数字を“a[i]≠i for all i”として並べたものとします。(=「完全順列」という)

x[1]=jとします。(j=2~n)
各jに対して
1) x[j]=1の場合→x[1],x[j]を除いたn-2個が完全順列をなす。
2) x[j]≠1の場合→x[k]=1となるkを考える(当然k≠j)
→x[1]とx[k]を置換すると、x[1]=1, x[k]=j
→x[1]を除いたn-1個が完全順列をなす。

という考え方です。
    • good
    • 0
この回答へのお礼

再度回答ありがとうございます。

少し悩みましたがこの考え方にも何とかたどり着きました。
それにしても、自然対数がこんなとこに出てくるとは面白いですね^^

お礼日時:2003/10/15 00:50

a[n]=(n-1)(a[n-1]+a[n-2]) の解釈やっとできました。

もう理解されているということなので、もう書かないことにします^^。

なかなかおもしろい問題ですね。また、おもしろい問題があれば投稿してください。すごく勉強になりました^^。

この回答への補足

この問題関連で、n人がカードをシャッフルした後
何人がもとと同じカードを持ってるかの期待値はnにはよらず1人という結果になりました。
なかなか面白いですね。

ということは、全く勉強せずに臨んだテストで
n個の空欄にn個の選択肢の中から選んで答える問題があって、
同じ選択肢は1度しか使えないようなときは
 ・全ての空欄に同じ選択肢を書く
 ・全ての空欄に異なる選択肢を書く
の2つは期待値としては同じになりますね。

この数列は収束が早くて n = 5 くらいであれば 0点の確率はほぼ 1/e なので
6割のギャンブルに乗れる人は2点以上を目指すのもいいかも^^

補足日時:2003/10/15 00:46
    • good
    • 0
この回答へのお礼

先ほど回答を拝見させていただきました。
(n+1)本の連立方程式との比較に持ち込むあたり
全く思いつきませんでした。

kony0 さん、sokamone さんどうもありがとうございました。

お礼日時:2003/10/15 00:35

すみません。

ひとつ書き間違えしてました。

No.2の文章中の
Σ^{n}nCk*x[k] = 0
は、n>0の場合で、n=0のときは、
Σ^{0}0Ck*x[k] = 1
にしないといけません。
    • good
    • 0

私も同じ問題を質問したことがあります。

^^

参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?q=158149
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

一応検索をかけてみたのですが、
見つからずに質問してしまいました。
名刺順列とかいう名前があったんですね。

お礼日時:2003/10/13 16:44

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q確率の問題です。

5人の人がクリスマスプレゼントを持ち寄りました。それを5人の子どもに配布します。どお子どもも自分の持ってきたプレゼントが当たらない確率を求めなさい。
これを書き出さないで、計算でやる方法はなかったですか?撹乱なんとかっていう題がついていたような…。教えてください!

Aベストアンサー

◆Naka◆
正解は44通りでOKです。
よって確率は11/30ですね。

こんな考え方はどうでしょう??
例えばここにABCの3つの文字があります。
これをどれも、同じものが同じ場所に来ないように並べる(攪乱順列、または完全順列と言います)方法は、仮に
A B C
B C A
と、攪乱順列を作ったときの、3文字の巡回置換になりますので、3つのものの円順列と同じで、
(3-1)!
つまり2通りになりますね。

これを応用しましょう。
下の並べ方を見てください。
A B C D E
B A D E C
これは、A,Bの2つの文字のグループと、C,D,Eの3つの文字のグループに分かれていると考えられます。
下記のような場合も同様です。
A B C D E
D E A C B
この場合は、A,C,Dの3文字と、B,Eの2文字のグループになります。

では、このようなグループの作り方は何通りありますか??
答えはもちろん、5C2(または5C3)で、10通りですね。
上の例にならい、この場合それぞれのグループ内での巡回置換は、2文字の方が
(2-1)!
3文字の方が、
(3-1)!
になります。
また、2文字と3文字が入れ替わることはできませんので、そのままかけて全部で、
5C2*(2-1)!*(3-1)!=20 ---[1]
このように、20通りあることになります。

次に、
A B C D E
B D A E C
のように、5つ全部がグループなしでバラバラの場合が考えられます。
これも同様に、
(5-1)!=24 ---[2]
と、24通りありますので、[1]+[2]で、
20+24=44
合計44通りになります。

このように、2文字グループ+3文字グループ、または5文字バラバラの場合以外はありません。
例えば4文字グループ+1文字グループということになると、その1文字は同じ文字になってしまいますから。

今回は5つの文字の攪乱順列でしたから、上記の計算で簡単に出せましたが、例えば4文字だった場合は、ちょっと注意しなければならない点もあります。
4文字ですと、2文字グループ+2文字グループ、または4文字バラバラしかありませんが、この2文字+2文字の計算のときに、その2グループの入れ替わりを考えなければなりません。
興味がありましたら計算してみてください。
答えが「9通り」になれば、正解です。

◆Naka◆
正解は44通りでOKです。
よって確率は11/30ですね。

こんな考え方はどうでしょう??
例えばここにABCの3つの文字があります。
これをどれも、同じものが同じ場所に来ないように並べる(攪乱順列、または完全順列と言います)方法は、仮に
A B C
B C A
と、攪乱順列を作ったときの、3文字の巡回置換になりますので、3つのものの円順列と同じで、
(3-1)!
つまり2通りになりますね。

これを応用しましょう。
下の並べ方を見てください。
A B C D E
B A D E C
これは、A,Bの2つの文字...続きを読む

Qn個の箱とn個の球を全部異なるように入れる総数

n個の箱とn個の球がある。n個の箱には、1,2,・・・nと通し番号がついている。n個の球にも1,2,・・・nと通し番号がついている。いま、n個の箱に1つずつ球を入れるとき、箱の番号と球の番号が全部異なっているような入れ方の総数をU_nとする。
(1)U_1、U_2、U_3、U_4を求めよ
(2)U_n+1、U_n、U_n-1の間の関係を表す式を求めよ
(3)U_n+1、U_nとの間の関係を表す式を求めよ。

この問題を考えています。(1)はU_1=0、U_2=1、U_3=6、U_4=9 数え上げていったのですがあっているでしょうか?
(2)(3)は「漸化式」を求める問題だと思うのですが、
うまく立てられません。予想して帰納法はうまくいきませんでした。ほかにいい方法はないでしょうか?
回答いただければ幸いです。よろしくお願いします

Aベストアンサー

U[1]=0, U[2]=1までは良いけれど、ご質問のU[3],U[4]は違ってますね。漸化式は、まず小さいnについて調べてみることが重要です。でも、調べた僅かな例からカンで式を予想するってのは、確信が持てませんし、あんまり旨く行きません。それよりも、「U[n+1]で表されるもの(この場合、ボールの入れ方)」を「U[n]で表されるもの」と「U[n-1]で表されるもの」から作り出す手順を具体化してみることがポイントです。

「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」を数えてみましょう。

 まず、「n個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」をひとつ決めたとしましょう。
 そして、これらの箱の中からひとつ選んで箱jとしましょう。(この選び方はn通りあります。)箱jに入っている球を球kとしましょう。球kを箱jから取り除き、そこに、n+1番の箱と球を持ってきます。
球kを箱(n+1)に入れ、空いた箱jに球(n+1)を入れれば、「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」がひとつ出来上がります。
 だから、このやりかたでn×U[n]通りが作れます。

 しかしそれだけではありません。
 「n個の箱と球について、箱の番号と球の番号が一箇所を除いて全部異なっているような入れ方」を一つ決めたとしましょう。箱の番号と球の番号が一致しているところがひとつだけあるので、その番号をjとします。で、n+1番の箱と球を持ってきます。そして、球jを箱(n+1)に入れ、空いた箱jに球(n+1)を入れれば、「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」がひとつ出来上がります。

 ここで「n個の箱と球について、箱の番号と球の番号が一箇所を除いて全部異なっているような入れ方」は何通りあるでしょうか。一致している番号を何にするかの選び方がn通りあります。そして、残りの「(n-1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」をすれば良いのだから、n×U[n-1]通りあります。

 以上から、
U[n+1] = nU[n] + nU[n-1]
と分かります。これは線形漸化式なので、機械的に一般項を出すことも可能です。

U[1]=0, U[2]=1までは良いけれど、ご質問のU[3],U[4]は違ってますね。漸化式は、まず小さいnについて調べてみることが重要です。でも、調べた僅かな例からカンで式を予想するってのは、確信が持てませんし、あんまり旨く行きません。それよりも、「U[n+1]で表されるもの(この場合、ボールの入れ方)」を「U[n]で表されるもの」と「U[n-1]で表されるもの」から作り出す手順を具体化してみることがポイントです。

「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」を数えてみまし...続きを読む

Q名刺順列の個数

1~nまでの数を1列に並べるときに、i番目にiという数字が来ない順列を名刺順列とか完全順列とか言います。
このような順列の個数をA(n)とすると、
A(n)=n! * Σ_{k=0}^{n} (-1)^k / k!
であるそうです。この導出の仕方を教えて下さい。
ちなみに、A(n)に関する漸化式 A(n)=(n-1)*{A(n-1)+A(n-2)}, A(1)=0, A(2)=1は既に理解していますので、この漸化式の解き方でもいいです。
(この漸化式は1世代前の青チャートで見ました^^;)

この式を用いると、全世界の人が名刺を1枚ずつ持ち寄ってシャッフルしたとき、自分のところに自分の名刺が戻ってくる人が1人もいない確率が1/e=36.8%もあることがわかり、なかなか神秘的なのですが。

Aベストアンサー

kony0さん、こんにちは。自然対数の底がこんなところで出てくるなんて不思議ですよね。

漸化式まで立てられているのならあとは簡単です。
 A(n)=(n-1){A(n-1)+A(n-2)}  (1)
について、A(n)=n! B(n)なる新たな数列B(n)を考えます。
 n! B(n)=(n-1){(n-1)! B(n-1)+(n-2)! B(n-2)}  (2)
整理すると
 n(n-1) B(n)=(n-1)^2 B(n-1)+(n-1) B(n-2)  (3)
から
 n B(n)-(n-1) B(n-1)-B(n-2)=0  (4)
を得ます。これを2項間漸化式に持込むことを考えます。
2項間漸化式に直すと
 B(n)-B(n-1)=(-1/n){B(n-1)-B(n-2)}  (5)
を得ます。順次、式変形すると
 B(n)-B(n-1)=(-1/n){B(n-1)-B(n-2)}=.....=(-1)^(n-2) ((2×1))/n!){B(2)-B(1)}  (6)
となります。
また、(5)式の左辺は幸運なことに階差数列になっています。となると、単純に両辺のΣをとる一手です。
 B(k)-B(1)=Σ(-1)^(n-2) ((2×1))/n!){B(2)-B(1)}  (7)
(両辺の和はn=2からn=kまで取る)
ここにB(2)=1/2, B(1)=0ですから
 B(k)=Σ(-1)^(n-2) (1/n!)
   =Σ(-1)^n (1/n!)  (8)
と求められます。(和はn=2からn=kまで取る)

ここで(-1)^0 (1/0!)+(-1)^1 (1/1!)=0であることを使えば
 B(k)=Σ(-1)^n (1/n!)  *和は今度は、n=0からn=kまで取る  (9)
というスッキリした形に整理できます。
A(n)に直した式はなくてもいいですよね。

関数f(x)=exp(x)のテーラー展開を考え、x=-1を代入すると(8)と同じになります。
ですからご質問の最後の「全世界の人が名刺を・・・」の確率は1/eになるわけですね。

*計算間違いをしているかも知れません、ご自分で式をチェックしながら読んで頂ければ幸いです。

kony0さん、こんにちは。自然対数の底がこんなところで出てくるなんて不思議ですよね。

漸化式まで立てられているのならあとは簡単です。
 A(n)=(n-1){A(n-1)+A(n-2)}  (1)
について、A(n)=n! B(n)なる新たな数列B(n)を考えます。
 n! B(n)=(n-1){(n-1)! B(n-1)+(n-2)! B(n-2)}  (2)
整理すると
 n(n-1) B(n)=(n-1)^2 B(n-1)+(n-1) B(n-2)  (3)
から
 n B(n)-(n-1) B(n-1)-B(n-2)=0  (4)
を得ます。これを2項間漸化式に持込むことを考えます。
2項間漸化式に直すと
 B(n)-B(n-1)=(-1/n)...続きを読む


人気Q&Aランキング

おすすめ情報