- ベストアンサー
名刺順列の個数と導出方法
Umadaの回答
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になるわけですね。 *計算間違いをしているかも知れません、ご自分で式をチェックしながら読んで頂ければ幸いです。
関連するQ&A
- 完全順列の問題
完全順列についての漸化式D ( n ) = ( n - 1 ) { D ( n - 2 ) + D ( n - 1 ) }がありますが、その証明方法がわかりません。(1)一番目がkでｋ番目が位置の場合(2)一番目がｋで、ｋ番目が１以外の場合 の二つに場合分けして解く方法は理解しました。 今回質問したいのは、「ｎ枚の完全順列の個数をａnとします。 (1)ここへn+1枚目の札をn+1番目に追加します。 n+1番目の札を１～ｎ番目の札のどれか１枚と交換すれば、 ｎ＋１枚とも順番が一致しなくなります。よって、ａn個ある完全順列からｎ＋１番目へはそれぞれｎ個ずつの完全順列が作れます。 (2)また、ｎ個のうちｋ番目だけが揃ってしまっているものからも、 ｋ番目の数とｎ＋１番目の札を入れ替えれば、これも完全順列の１つとなります。ｎ個のうちｋ番目だけが揃っている札の並べ方をｂnとすると、 １～ｎまでのｎ個のｂnから、それぞれ１通りずつの完全順列(の１部)が作れます。 以上のことより、次の漸化式が作れます。 ａn+1＝ｎａn＋ｎｂn ……(i) ｋ番目以外はｎ－１個の完全順列となっているため、 ｂn＝ａn-1 (ｎ≧２)が成り立ちます。これを（i）II代入して上の漸化式が求まります。」 という解説が理解できないということです。具体的な疑問点は、(1)、(2)のせれぞれの操作は各々理解しているものの、なぜこれを足し合わせればすべて網羅したことになるのかということです。他に数えもれがありそうのように思えます。そもそもなぜこのようなやり方なのでしょうか。 ご教授のほどよろしくお願いします。
- 締切済み
- 数学・算数
- 完全順列の漸化式
完全順列をウィキペディアで調べると以下のように漸化式について解説していました。 モンモール数Ａnを与える漸化式を考える。 n番目に置く数の選び方は1からn-1までの(n-1)通りである。ここで選んだ数をiとする。 次にi番目がnかどうかで場合分けをする。 ｉ番目がnであれば、i番目に置かれたnとn番目に置かれたiを除く（n-2）個の数の並べ方の 総数は、(n-2)個の数による完全順列の数、すなわちA(n-2)に等しい。 i番目がnでない場合は、n番目に置かれたiを除く(n-1)個の数の並べ方の総数は、(n-1)個 の数による完全順列の数、すなわちA(n-1)となる。 以上をまとめると下の漸化式が得られる。 An=(n-1)・{A(n-1)＋A(n-2)｝ n>=3 これでは訳が解らないのでn=4の場合を考えます。 4番目に置く数の選び方は1から(4-1)までの3通りである。ここで選んだ数ｉは3である。 次に3番目(i番目)が4(n)かどうかで場合分けをする。 3番目(i番目)が4（n）であれば3(i)番目に置かれた4（n）と4(n)番目に置かれた3(i)を除く(4-2）個 の数の並べ方の総数は、(4-2)個の数による完全順列の数、すなわちA(4-2)に等しい。 3(i)番目が4(n)でない場合は4(n)番目に置かれた3(i)を除く(4-1)個の数の並べ方の総数は (4-1)個の数による完全順列の数、すなわちA(4-1)となる。 A4=(4-1)・{A(4-1)＋A(4-2)}=3×(A3＋A2) 両辺をそれぞれ自力で強引に調べると確かに両辺とも9になっていて この漸化式は正しいようですが、n=4の場合に簡単化してもいまひとつ ピンときません。 平たく云って、この漸化式はどのような考え方に基づいて成り立って いるのでしょうか。
- ベストアンサー
- 数学・算数
- 完全順列の証明
赤チャートに完全順列の証明が載っていました ＜証明＞ n個の数の順列1,2,・・・,nの完全順列の個数をW(n)で表す。 1,2,・・・,nの完全順列をf(1),f(2),・・・f(n)とする。 f(1)=k とするとこの完全順列は[1],[2]のどちらかである。 [1]f(k)=1 であるもの 1,k を除いた 2,・・・,k-1,k+1,・・・,n のn-2個について完全順 列であるからその個数はW(n-2)個 [2]f=(k) ではないもの f(h)=1とするとh=kではないから,f(1)=1,f(h)=kと置き換えると,1を 除いた 2,・・・,n のn-1個について完全順列であるから,その個数 はW(n-2)個 2≦k≦nであるから,kのとりうる値は n-1通り したがってW(n)=(n-1){W(N-1)+W(N-2)} ＜終＞ いくつか理解できない点があります (1)なぜf(k)=1と、f(k)=1でないものに分けて考えているのでしょうか？ (2)[2]で、f(1)=1,f(h)=kと置き換えるとはどういう事なのでしょうか？ 何のために置き換えるのですか？
- ベストアンサー
- 数学・算数
- 完全順列(モンモール数)の2項間漸化式の組合せ論的解釈
http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97 より、 完全順列とは、整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のことであり、その総数をモンモール数という。 その総数をa[n]とすると、上記のサイトに、3項間漸化式 a[n]=(n-1)(a[n-1]+a[n-2]) の組合せ論的解釈が書かれています。 また、2項間漸化式 a[n]=n*a[n-1]+(-1)^n が成り立つのですが、普通は3項間漸化式を元に代数的に変形して示します。 しかし、これを直接に組合せ論的解釈したいのです。 いろいろ考えても、いろいろ調べてもわかりません。 興味ある方はどうか教えてください。
- 締切済み
- 数学・算数
- 攪乱順列とは・・・
攪乱順列とはなんでしょうか。またその個数の求め方の公式（包含と排除の原理）が解りません。 なんとなく「順列で動かないものが1つもないもの」のようなことはわかります。 包含と排除の原理 n(U)-n(P1∪P2∪P3∪・・・・∪Pn) =n(U)-Σn(Pi)+Σn(Pi∩Pj)-Σn(Pi∩Pj∩Pk)+・・・・+(-1)^n*n(P1∩P2∩P3∩・・・・∩Pn) =n!*(1-1/1!+1/2!+1/3!+・・・・・+(-1)^n*1/n!) 結論として上の最後の行だけ覚えればいいのでしょうか。i,j,kが何かもよくわかりません。1-Pバーのようなことも書いてありますがちょっと理解できません。
- ベストアンサー
- 数学・算数
- 完全順列が分かりません
完全順列を青チャートで学んでいるんですが、 公式Ｗ（ｎ）＝（n-1）{W(n-1)+W(n-2)}の意味がさっぱりわかりません。 ご説明できる方、助けてください。よろしくお願いします。
- 締切済み
- 数学・算数
- I_(n)=∫x^n/√(x^2+a^2)dxの漸化式の求め方
I_(n)=∫x^n/√(x^2+a^2)dxの漸化式の求め方 この積分の漸化式は I_(n)=x^(n-1)√(x^2+a^2)/n - a^2(n-1)I_(n-2)/n となります この式の求め方がわかりません 誰か教えてください お願いします
- ベストアンサー
- 数学・算数
- モンモール問題、完全順列、攪乱順列の拡張
モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。 1，2，3，・・・，n の数を並び替えたとき、先頭から数えた順番と数が一致するものが1つもない並べ方 n人がプレゼントをもちよって、バラバラに交換したとき、1人も自分自身の用意したプレゼントをもらわない方法 写像f:{1,2,…,n}→{1,2,…,n}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 これらの場合の数は、n!Σ[k=0,n]{(-1)^k}/k!であることはよく知られています。 そこで、拡張として次の総数を考えるとどうなるのでしょうか？ n≦mとする。 写像f:{1,2,…,n}→{1,2,…,m}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 たとえば、n=3,m=4のとき、 (f(1),f(2),f(3))=(2,1,4),(2,3,1),(2,3,4),(3,1,2),(3,1,4),(3,4,1),(3,4,2),(4,1,2),(4,3,1),(4,3,2)
- ベストアンサー
- 数学・算数
- シグマの公式
Σ[k=1からnまで]k^2=n(n+1)(2n+1)/6の導出方法を教えてほしいです googleで検索してみたのですが、なかなかいいサイトがなくて、教えてgooに 質問させていただきました。 Σ[k=1からnまで]k=n(n+1)/2は、1+2+3+4+5+6+.....+nなので初項1 公差1を 等差数列の和の公式S=｛2a+(n-1)d｝/2...(1)に代入して（この公式は導けます）, n(n+1)/2を得ましたが、 Σ[k=1からnまで]k^2も同様に、1^2+2^2+3^2+4^2+5^2+6^2+......+n^2 =1+4+9+16+25+36+49+.....+n^2 漸化式、a_(n+1)=a_(n)+2n+1と表した場合の公差は2n+1と考えて、 初公1,公差2n+1を(1)に代入したのですがn(n+1)(2n+1)/6を得られませんでした。 どこが間違えているのでしょうか？ またどのようにn(n+1)(2n+1)/6を導出すればいいのでしょうか。 pc上での記号の表記の仕方がわからないもので、 わかりづらい箇所があるかと思います。すみません。
- ベストアンサー
- 数学・算数
お礼
ご回答ありがとうございます。その文字置きはまったく思いつきませんでした。 本当に文字置きだけできてしまえば、あとは綺麗に解けるんですね～。 B(n)ってn個の順列のうち名刺順列になるものの確率を表しているので、立式の段階で(4)式がたてられる考え方がきっとあるはずと思います。そちらのほうは暇なときに考えてみます。この式から出発だと簡単ですしね。 ありがとうございました。