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 回答 (1件)

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になるわけですね。

*計算間違いをしているかも知れません、ご自分で式をチェックしながら読んで頂ければ幸いです。
    • good
    • 0
この回答へのお礼

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

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

ありがとうございました。

お礼日時:2001/10/27 16:23

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

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

Q英語で「個数」「件数」は?

質問は単純です。
英語で「個数」や「件数」をなんというか、です。

とりあえず、思いついたのは、numberでした。
たとえば、「りんごの個数」は"a number of apples"ですか?
でも、"a number of"は「いくつかの」という意味ですよね。

「データの件数」は"a number of data"でしょうか?

私は英語はほとんど出来ませんが、numberは「個数」というよりも「番号」という意味であるような気がしてなりません。

Aベストアンサー

>「個数」や「件数」をなんというか、です。
>とりあえず、思いついたのは、numberでした。
意外に思われるかもしれまんせんが、語の選択はnumberであっています、と思います。

>「りんごの個数」
the number of (the) apples

>「データの件数」
the number of (the) data

>numberは「個数」というよりも「番号」という意味であるような気がしてなりません。
実は、昔、私も、「個数や件数はなんていうのかな、え、number? え、本当?」と、奇異に感じたことを、思い出しました。

QA={Φ,{{a,b},{a,c}}} B={Φ,{a,b},{a,c

A={Φ,{{a,b},{a,c}}} B={Φ,{a,b},{a,c}}のとき、A∩Bは{Φ}なのかそれとも{a,b}などを含むのかどうかがわかりません。 わかる人がいらっしゃるなら教えてください。お願いします。

Aベストアンサー

落ち着いて考えれば分かるはず。
ただ、若干の慣れは必要かも・・・。

・考え方
Aの元は、Φと{{a,b},{a,c}}}の2個。
Bの元は、Φと{a,b}と{a,c}の3個。
共通するのは、Φだけ。

よって、A∩Bの元はΦだけ。
つまり、A∩B={Φ}。

Q個数 を英語で表現

ホームページ作成中です。
入荷状況ページにかっこよく英語で表記しようと思うのですが、いい表現が思いつきません。

大きさ=Size
型番=Model
価格=Price
までは、わかったのですが、
入荷個数ってのがわからないです。
何かいい表現方法は無いでしょうか?
デザインをあまり崩したくないので、上記語句とそんなに文字数が変わらないのがうれしいのですが…
よろしくお願いします。

Aベストアンサー

アメリカに35年ほど住んでいる者です。

簡単に数個を示すのであれば、Quantityで済ます事ができます。 一番妥当と思います。 (unit, number等のほかの言い方は、ここでは残念ながらつかわ内方がいいと思います。)

ただ、単位として、Quantity: 50 units, Quantity: 10 piecesとして使う事はできますね

なぜ、quantityだけでいいかと言うと、他に数量のことを言わないからなんですね。 例えば、最少/最大購買数、入庫予定数、等があれば、quantityだけでは不親切となるので、Quantity in stock, Inventory (Quanaity), Available Quantity, Quantity on hand, Quantity in store, 等が使えますね。

なお、QTY, Qtyをすることは全く問題ありませんが、大文字にするかで、その業のイメージバランスが壊れる事がありますので、Qtyとすることもできることを知っておいて下さいね。

なお、在庫している数量ということで、書かせいただきました。

これでいいでしょうか。 分からない点がありましたら、補足質問してください。

アメリカに35年ほど住んでいる者です。

簡単に数個を示すのであれば、Quantityで済ます事ができます。 一番妥当と思います。 (unit, number等のほかの言い方は、ここでは残念ながらつかわ内方がいいと思います。)

ただ、単位として、Quantity: 50 units, Quantity: 10 piecesとして使う事はできますね

なぜ、quantityだけでいいかと言うと、他に数量のことを言わないからなんですね。 例えば、最少/最大購買数、入庫予定数、等があれば、quantityだけでは不親切となるので、Quantity in stock, Inven...続きを読む

Q数列{a_n}、{b_n}が、a_n=s^n, b_n=r^n(n=1

数列{a_n}、{b_n}が、a_n=s^n, b_n=r^n(n=1,2,3,,) 0<s<r<1 で与えられている時、
Σ∞_(n=1) a_(n)b_(n) = 1/3 , Σ∞_(n=1) a_(n)/b_(n) = 3
を満たすとする。この時、s+rの値を求めよ

Aベストアンサー

  a[n] = s^n
  b[n] = r^n
より、
  a[n]*b[n] = (s*r)^n
  a[n]/b[n] = (s/r)^n
もまた等比数列となる。

等比数列の和の極限は公式により求められるから、
  Σ[n=1~∞]{a[n]*b[n]} = 1/3
より
  s*r = 1/2
が分かり、
同様に
  Σ[n=1~∞]{a[n]/b[n]} = 3
より
  s/r = 3/4
が分かる。

二つの未知数s,rに対して、二式
  s*r = 1/2
  s/r = 3/4
が得られたから、あとはs<rという条件を加え、連立方程式を解くことでs,rの値が求まる。

Q変数が個数の時の英文

数学の文章問題のように変数(記号)を何かの個数としたいのですが、
英語ではなんと書けば良いのではでしょうか?
例えば、x個のリンゴがあります、n冊の本を読みました、などです

Aベストアンサー

だぶん
The 'X' number of apples.
The 'N' number of books.

補足として
Either X or N is the number variable.
とでも書けばよいかも。

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英語に訳して頂けないでしょうか?

相手に通じてないようなので、以下を英語に訳して下さい。お願いいたします。

「私は○○を2個注文しました。
別々に届きましたがどちらのインボイスにも2個と記載されていました。
インボイスの個数を訂正して下さい。」

Aベストアンサー

I ordered two ○○s.

They arrived separately, each with an invoice stating "two",

Could you correct the invoice number to "one"?

訂正は、「~に訂正」と言うのが自然でもあり間違いを防ぐことにもなると思いましたので、終わりに原文に無い「1」に訂正してください、を入れました、不要なら最後の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の英語の学習範囲でもある、I の次に記入する a と an の違いがわかりません。

aは1つの個数を示すものだとわかるんですが、
anがわかりません。

わかる方がいれば、教えてください。

Aベストアンサー

a と一緒です。
ただし対象物の頭文字が母音(a,i,u,e,o) の場合は an を使います。
例 an apple

Q{A_n}をA_n∩A_n+1≠φであるような連結なXの部分空間なら∪[n=1..∞]A_nは連結である事を示せ

たびたびすいません。

{A_n}をA_n∩A_n+1≠φであるような連結なXの部分空間の列とする。
∪[n=1..∞]A_nは連結である事を示せ。

という問題が多分解けてません。


Xの位相をTとするとA_nは部分空間なのだからA_nの位相はT_n:={A_n∩t;t∈T}と書ける。
∪[n=1..∞]A_nの位相として∪[n=1..∞]T_nが採れる。
そして各A_nが連結なのだから
∀U,V∈T_nに対し,A_n=U∪VでU∩V≠φ
よって
∀U,V∈∪[n=1..∞]T_nに対し,∪[n=1..∞]A_n=U∪VでU∩V≠φ
と結論づいたのですが自信がありません。

どのようにして示せますでしょうか? すいません。お力をお貸しください。

Aベストアンサー

>、、となって矛盾になりませんが、、何処を間違ったのでしょうか?

なんで矛盾する必要が?
「連結ではない」
を仮定して
「連結ではない」
がでてきてるでしょう?

U∪V⊃A,A∩U∩V=φ

A∩(U∪V)=A,A∩U∩V=φ
が同じってことです.


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング