「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確率問題 二項定理

確率問題 二項定理

予備校で二項定理を使えば、例えば4人でジャンケンする場合のそれぞれの組あわせの確率は
(1/3+1/3+1/3)の2乗ですべて求めらあれるということを習いました

でもいざ他の問題を解こうとすると、2項定理が使えないように思われるものもありました。
二項定理を使えるものと使えないものがあるのでしょうか?
あるのなら、その見分けをご説明願います。

Aベストアンサー

二項定理が必要なもの……二項分布

Q(再投稿)R^n∋A_1,A_2,…はΣ[k=1..∞]λ^*(A_k)<∞を満たす.∩[n=1..∞]∪[k=n..∞]A_kはLebesgue外測度0?

すいません。
http://okwave.jp/qa4327195.html
について再投稿です。


A:=∩[n=1..∞]∪[k=n..∞]A_kと置いて
今,AがLegesgue可測集合である事を示したい訳ですよね。
Lebesgue可測集合とはλをLebesgue外測度とする時,
{E;Eはn次元区間塊,E⊂∀S⊂R^n,λ(S)≧λ(S∩E)+λ(S∩E^c)}の元の事ですよね。
そこで疑問なのですがλはn次元区間塊全体に対して定義された写像ですよね。なのでλ(S∩E)とλ(S∩E^c)はそれぞれλ(E)+λ(E^c)で(∵E⊂∀S⊂R^n),一応は定義されているのですがλ(S)はSの採りようによってはλ(S)自体が定義されないという状況に陥ってしまいます(∵必ずしもSはn次元区間塊とは限らない)。
するとλ(S)≧λ(S∩E)+λ(S∩E^c)という不等式は意味を成さなくなります。
従って,AがLebesgue可測集合である事が示せなくなってしまいます。
Lebesgue可測集合の定義を勘違いしてますでしょうか?

すいません。
http://okwave.jp/qa4327195.html
について再投稿です。


A:=∩[n=1..∞]∪[k=n..∞]A_kと置いて
今,AがLegesgue可測集合である事を示したい訳ですよね。
Lebesgue可測集合とはλをLebesgue外測度とする時,
{E;Eはn次元区間塊,E⊂∀S⊂R^n,λ(S)≧λ(S∩E)+λ(S∩E^c)}の元の事ですよね。
そこで疑問なのですがλはn次元区間塊全体に対して定義された写像ですよね。なのでλ(S∩E)とλ(S∩E^c)はそれぞれλ(E)+λ(E^c)で(∵E⊂∀S⊂R^n),一応は定義されているのですがλ(S)はSの採りようによってはλ(S)自体が定義され...続きを読む

Aベストアンサー

とりあえず教科書を読む.
定義が分かってなければ何もできない.

>Lebesgue可測集合とはλをLebesgue外測度とする時,
>{E;Eはn次元区間塊,E⊂∀S⊂R^n,λ(S)≧λ(S∩E)+λ(S∩E^c)}の元の事ですよね。

こんなこと本当に書いてある?なんか読み落としているとか
説明の途中の何かだとか,勝手に創作してるとか?

>Lebesgue可測集合の定義を勘違いしてますでしょうか?
してる.
だって,それだったら「円」ですらルベーク可測じゃなくなる.

Q二項定理の問題を教えてください

二項定理の問題がわかりません。詳しく簡単におしえてください。おねがいします。

nは2以上の整数とする。二項定理を利用して、次のことを示せ。

(1) a>0のとき (1+a)^n>1+na

(2) (1+1/n)^n>2

よろしくおねがいします。

Aベストアンサー

(1)
 二項定理より、
 (1+a)^n
= 1 + nC1*a + …… + a^n
= 1 + na + …… + a^n
>1+na

(2)
 (1)の結果から、
 (1+1/n)^n >1+1/n*n=2

・・・とまあこんな感じでしょうか。

QR^n∋A_1,A_2,…はΣ[k=1..∞]λ^*(A_k)<∞を満たす.∩[n=1..∞]∪[k=n..∞]A_kはLebesgue外測度0?

よろしくお願い致します。

A_1,A_2,…をΣ[k=1..∞]λ^*(A_k)<∞を満たすR^nの部分集合とせよ。
(ア) ∩[n=1..∞]∪[k=n..∞]A_kがLebesgue外測度0を持つ事を示せ。
(イ) これはLebesgue測度0を持つか? 持つなら理由を述べよ。

という問題です。

(ア)について
Lebesgue外測度の定義からλ^*(A_k)=inf{Σ[i=1..∞]|I_i|;A_k⊂∪[i=1..∞]I_i}…(1)
(但しI_iはn次元区間塊[a_1,b_1]×[a_2,b_2]×…×[a_n,b_n])と書け,
題意よりΣ[k=1..∞]λ^*(A_k)<∞なのでλ^*(A_k)<∞と分かる。
それでλ^*(∩[n=1..∞]∪[k=n..∞]A_k)=inf{Σ[i=1..∞]|I_i|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i}
から先に進めません。
λ^*(∩[n=1..∞]∪[k=n..∞]A_k)=Σ[n=1..∞]λ(∪[k=n..∞]A_k)なんて変形もできませんよね。
どのすれば=0にたどり着けますでしょうか?

(イ)について
答えは多分Yesだと思います。
Lebesgue可測集合はL:={E∈R^n;E⊂Uでinf{λ^*(U\E);Uは開集合}=0}の元の事ですよね。
なのでLebesgue測度は制限写像λ^*|L:=μと書けますよね。
それで∩[n=1..∞]∪[k=n..∞]A_k∈Lを示せば(ア)からLebesgue測度0が言えると思います。
今,(ア)より
inf{Σ[i=1..∞]|I_i|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i}=0
と分かったので
0=inf{Σ[i=1..∞]|I_i|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i}
=inf{Σ[i=1..∞]|I_i\Bd(I_i)∪Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)∪Bd(I_i)}
(但しBd(I_i)は境界点)
=inf{Σ[i=1..∞]|I_i\Bd(I_i)|+|Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)∪Bd(I_i)}
(∵||の定義)
からinf{Σ[i=1..∞]|I_i\Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)}
となればI_i\Bd(I_i)は開集合になので
inf{Σ[i=1..∞]|I_i\Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)}=0が言え,
∩[n=1..∞]∪[k=n..∞]A_k∈Lも言え,
μ(∩[n=1..∞]∪[k=n..∞]A_k)=λ^*(∩[n=1..∞]∪[k=n..∞]A_k)=0(∵(ア))
となりおしまいなのですが

inf{Σ[i=1..∞]|I_i\Bd(I_i)|+|Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)∪Bd(I_i)}
から
inf{Σ[i=1..∞]|I_i\Bd(I_i)|;∩[n=1..∞]∪[k=n..∞]A_k⊂∪[i=1..∞]I_i\Bd(I_i)}
となる事がどうしても言えません。どうすれば言えますでしょうか?

よろしくお願い致します。

A_1,A_2,…をΣ[k=1..∞]λ^*(A_k)<∞を満たすR^nの部分集合とせよ。
(ア) ∩[n=1..∞]∪[k=n..∞]A_kがLebesgue外測度0を持つ事を示せ。
(イ) これはLebesgue測度0を持つか? 持つなら理由を述べよ。

という問題です。

(ア)について
Lebesgue外測度の定義からλ^*(A_k)=inf{Σ[i=1..∞]|I_i|;A_k⊂∪[i=1..∞]I_i}…(1)
(但しI_iはn次元区間塊[a_1,b_1]×[a_2,b_2]×…×[a_n,b_n])と書け,
題意よりΣ[k=1..∞]λ^*(A_k)<∞なのでλ^*(A_k)<∞と分かる。
それでλ^*(∩[n=1..∞]∪[k=n..∞]A_k)=inf{Σ[i=...続きを読む

Aベストアンサー

数列の部分和の定義と∩∪の定義からすぐだと思いますよ。
面倒なので外測度を単にλで表します。
仮定はΣλ(A_k)<∞です。これは級数の収束の定義から部分和
S_N=Σ[k=1,..,N] λ(A_k)
がコーシー列、よって
任意のε>0に対してNが存在し、n≧Nならば
Σ[k=n,...,∞] λ(A_k)<ε
ということを言っているわけです。
問題は、∩[n=1,..,∞]∪[k=n,..∞] A_kの外測度を求めることですが上の事実を利用できることが分かると思います。上で示したNをとってきます。このとき
λ(∩[n=1,..,∞]∪[k=n,..∞] A_k)≦Σ[k=N,..,∞] λ(A_k)<ε
となるのはほとんど明らかですね。任意のεに対してもっと大きい番号N'をとっても問題の集合はN'から先の和集合に含まれるわけですからこれは結局λ(∩[n=1,..,∞]∪[k=n,..∞] A_k)=0でなければならないことを示しています。

Q二項定理の問題なんですが…

すいません、今ちょっとノートを見ていて、分からないのですが、(1-0.01a)^5を二項定理を利用すると、(1-0.01a)^5={1-5a*(10^-2)}という風になっているんですけど、この等式は合っているのでしょうか?二項定理を利用した場合、a^2,a^3,a^4,a^5なども出てくる気がするんですが…。ただの間違いなんでしょうか。どなたかお願いします。

Aベストアンサー

これは二項定理ではなく近似式ですね。

x << 1(xが1に比べて無視できるほど小さい…要するにほぼゼロ)のときに、
(1+x)^n ≒ 1+nx
です。
ここではx=-0.01aとしてますね。

二項定理を用いるのならば、お考えの通り他のa^2 ~a^5の項も出てきます。

Q漸化式a[n]=a[0]*a[1]*…*a[n-1]+p

漸化式
a[n]=a[0]*a[1]*…*a[n-1]+p
を解きたいのです。pは定数とします。

p=0であれば、
a[n]=a[0]*a[1]*…*a[n-3]*a[n-2]*a[n-1]
=a[0]^2*a[1]^2*…*a[n-3]^2*a[n-2]^2
=a[0]^4*a[1]^4*…*a[n-3]^4
=…
=a[0]^2^(n-1)
と解けます。

p=2、またa[0]=3としたりすると、
a[n]=2^2^n +1
が解であることは代入すればわかります。

一般のp(定数)、初期値も一般に与えて、その漸化式は解けますでしょか。
一般解でなくても、pがなにか具体的な数のときの解でもいいです。よろしくお願いします。

Aベストアンサー

また思い出してちょっと見てみました。

p=1,a0=2としてエクセルでanを計算してみると、anは爆発的に増加
して、nが10を超えると計算できなくなってしまいますが、nが5を
過ぎるとlog(log(an))はほぼ直線になって、傾きがlog2になります。
なので、an=A^(2^n)+Bのような格好になるかと思います。

また、この漸化式はユークリッドの原論にある素数が無限にあること
の証明にあるものと似てるし、素数の逆数和が大体loglogの速さで
無限大に発散することとも関係してるのかも。
でも(2)のS[n]=1-1/P[n]からS[n]<1だから、anは素数に比べると
ものすごく少ないようだし、結局よくわからない・・・

そもそもこれ出典は何なんですか?

Q二項定理…

二項定理の解き方は、公式を暗記するしかなぃのでしょうか。。

Aベストアンサー

二項定理
(a+b)^nの解き方の問題ですが
展開後の各項の係数について便利なツールがあります
パスカルの三角形と呼ばれる物です
参考URLでご確認下さい

なおn=2,3の場合は暗記したほうが便利です

参考URL:http://www.kjps.net/user/kakuritsu/pascal.html

Q数列a[n+1]=a[n]/(1+a[n])^2,a[1]=1/2

数列a[n+1]=a[n]/(1+a[n])^2,a[1]=1/2
のとき、
lim[n->∞](a[1]+・・・・+a[n])/n の値を求めよ。
(小問で、1/a[n]>2nは解決済み。)

はさみうちをするのだとは思うのであるが、その前のひと工夫がわからない。
よろしくお願いします。

Aベストアンサー

>はさみうちをするのだとは思うのであるが、その前のひと工夫がわからない。

ひと工夫ってこんなこと?小問の利用?

0<(1/n)Σ[k=1,n]a[n]/n<(1/n)Σ(1/2k)=(1/2n)(∫[1,n]dx/x+1)
これで、n→∞ とすればよい。

Q数学の二項定理が全くわかりません。 どうすればいいですか?

数学の二項定理が全くわかりません。
どうすればいいですか?

Aベストアンサー

公式にある、コンビネーションの意味は、例えば、(a+b)^3だと、(a+b)(a+b)(a+b)と分解して考えます。すると、公式でのコンビネーションは3つの()の中から1つはaで、残りがbだよということを意味しています。あとは、交互にaとbを機械的にやれば良いのです。n乗の時は、ゼロ個選ぶときとか、順に考えれば大したこと無いです。深く考えなくても、機械的にできます。安心して下さい。

Qa[1]=3,4a[n+1]=12a[n]-2×{3^(n-1)}×n

a[1]=3,4a[n+1]=12a[n]-2×{3^(n-1)}×n+3^(n-1)
で、
Σa[k](k=1~n)を最大にするnの最小を求めよ。

まず、一般項a[n]=-3^(n-2){n^2-2n-3)/4 を求めました。
このあとΣの値を求められません。
よろしくお願いします。

Aベストアンサー

a[n] が正だったら,足せば合計は大きくなります.
a[n] の符号変化を見て,負になる前まで足せば,
そこが合計が最大になる場所の候補です.


人気Q&Aランキング

おすすめ情報