OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

名刺順列の個数

  • 暇なときにでも
  • 質問No.158149
  • 閲覧数218
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 57% (24/42)

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%もあることがわかり、なかなか神秘的なのですが。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル14

ベストアンサー率 83% (1169/1405)

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

お礼率 57% (24/42)

ご回答ありがとうございます。その文字置きはまったく思いつきませんでした。
本当に文字置きだけできてしまえば、あとは綺麗に解けるんですね~。

B(n)ってn個の順列のうち名刺順列になるものの確率を表しているので、立式の段階で(4)式がたてられる考え方がきっとあるはずと思います。そちらのほうは暇なときに考えてみます。この式から出発だと簡単ですしね。

ありがとうございました。
投稿日時 - 2001-10-27 16:23:30
-PR-
-PR-
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ