「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■この命題は正しいでしょうか?
暇なときで構いませんので、よろしくお願いします。
No.2ベストアンサー
- 回答日時:
すでに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
回答ありがとうございます。
今、時間がありませんので後でじっくり読ませていただきますね。
それから、
a[n]=(n-1)*(a[n-1]+a*[n-2])
のほうの解釈も何とか理解できましたので、
あとで補足にでも書かせていただきます。
kony0 さんのほうが早いかな?
No.5
- 回答日時:
すでにみなさん解釈が終わっているそうですが、漸化式の導き方は以下のとおり。
数列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個が完全順列をなす。
という考え方です。
再度回答ありがとうございます。
少し悩みましたがこの考え方にも何とかたどり着きました。
それにしても、自然対数がこんなとこに出てくるとは面白いですね^^
No.4
- 回答日時:
a[n]=(n-1)(a[n-1]+a[n-2]) の解釈やっとできました。
もう理解されているということなので、もう書かないことにします^^。なかなかおもしろい問題ですね。また、おもしろい問題があれば投稿してください。すごく勉強になりました^^。
この回答への補足
この問題関連で、n人がカードをシャッフルした後
何人がもとと同じカードを持ってるかの期待値はnにはよらず1人という結果になりました。
なかなか面白いですね。
ということは、全く勉強せずに臨んだテストで
n個の空欄にn個の選択肢の中から選んで答える問題があって、
同じ選択肢は1度しか使えないようなときは
・全ての空欄に同じ選択肢を書く
・全ての空欄に異なる選択肢を書く
の2つは期待値としては同じになりますね。
この数列は収束が早くて n = 5 くらいであれば 0点の確率はほぼ 1/e なので
6割のギャンブルに乗れる人は2点以上を目指すのもいいかも^^
先ほど回答を拝見させていただきました。
(n+1)本の連立方程式との比較に持ち込むあたり
全く思いつきませんでした。
kony0 さん、sokamone さんどうもありがとうございました。
No.3
- 回答日時:
すみません。
ひとつ書き間違えしてました。No.2の文章中の
Σ^{n}nCk*x[k] = 0
は、n>0の場合で、n=0のときは、
Σ^{0}0Ck*x[k] = 1
にしないといけません。
No.1
- 回答日時:
回答ありがとうございます。
一応検索をかけてみたのですが、
見つからずに質問してしまいました。
名刺順列とかいう名前があったんですね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
誕生日にもらった意外なもの
みなさんがもらった誕生日プレゼントで面白いものがあったらぜひ教えてください!
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
確率の問題です。
数学
-
n個の箱とn個の球を全部異なるように入れる総数
数学
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報