二項係数の入った数列

質問

「Ａ，Ｂ，…のｎ人がそれぞれ a,b,… という
異なるカードを持っていたとする。
カードをシャッフルして再び配ったとき
始め持っていたカードと同じカードを持っている人が
一人もいないときの場合の数はいくつか？」
という問題を最近考えています。

ｎ人のときの場合の数を 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),(2)式は同じものでしょうか？
■質問２■この数列の一般項はどのようになりますか？

また、a[n] を n! で割ったものは
誰一人もとと同じカードを持っていない確率になりますが、
これが n→∞ で 1/e に収束しているようなのです。
■質問３■この命題は正しいでしょうか？

暇なときで構いませんので、よろしくお願いします。

回答No.2

sokamone · ベストアンサー

すでに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についての和）
と書くと意味がよくわかります。その意味は、
１からｎまでの自然数の並び替えの総数はn!だが、
これは、ｎ個の中からｋ個の数字を選んで、それらのみを完全に並び替えるような並び替えの総数 nCk*a[k] を、ｋが０からｎまですべてについて和をとったものと同じである、ということです。この等式をE(n)と書くことにします。
　n!=ΣnCk*a[k]・・・E(n)

質問１の回答：
(１)、(２)の式はまとめると、
a[n]=n*a[n-1]+(-1)^n
と書けることに注意してください。それを計算の都合上、
a[n]-n*a[n-1]=(-1)^n・・・(３)
と書いておきます。
E(n) から（３）が導かれることを示します。
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])
を得ます。和はｋ=0～ｎです。ここで、簡単のため、x[k]=a[k]-k*a[k-1] とおきますと、この式は、
　0 = Σ^{n}nCk*x[k]
となります。これをｎが０からｎまでに渡って考えて、次のように全部で 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]、の連立１次方程式で、上から順に未知数の数が１個、２個、３個、…と増えて行ってます。係数はすべて０ではないので、この連立方程式は、ただ一つの解しか持ちません。さて、ここで、２項展開の公式から次の式が成り立つのはご存知だと思います。
　Σ^{n}nCk*(-1)^k = (1-1)^n = 0
これはどんなｎについても成り立ちますから、(-1)^kが上の連立方程式の解であることがわかります。よって、
　x[k]=(-1)^k、すなわち、a[k]-k*a[k-1]=(-1)^k
が成り立ちます。これで(３)が導かれました。

質問２の回答：
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}のべき級数展開のｎ次の項までの式にｘ＝－１を代入したものになっています。したがって、ｎが無限に大きくなると、e^{-1}=1/e に近づきます。

あとは、No.1の参考URLに出てきた漸化式a[n]=(n-1)*(a[n-1]+a[n-2])がどうして出てくるのかがわかれば完璧なのですが、ちょっとすぐにはわからなかったので、No.１の方教えてください＾＾；。ちなみに、a[n]=(n-1)*(a[n-1]+a*[n-2])から、(３)の漸化式はつぎのように導きます。
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

kony0

すでにみなさん解釈が終わっているそうですが、漸化式の導き方は以下のとおり。

数列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

sokamone

a[n]=(n-1)(a[n-1]+a[n-2]) の解釈やっとできました。もう理解されているということなので、もう書かないことにします＾＾。

なかなかおもしろい問題ですね。また、おもしろい問題があれば投稿してください。すごく勉強になりました＾＾。

お礼

先ほど回答を拝見させていただきました。
(n+1)本の連立方程式との比較に持ち込むあたり
全く思いつきませんでした。

kony0 さん、sokamone さんどうもありがとうございました。

補足

この問題関連で、ｎ人がカードをシャッフルした後
何人がもとと同じカードを持ってるかの期待値はｎにはよらず１人という結果になりました。
なかなか面白いですね。

ということは、全く勉強せずに臨んだテストで
ｎ個の空欄にｎ個の選択肢の中から選んで答える問題があって、
同じ選択肢は１度しか使えないようなときは
　・全ての空欄に同じ選択肢を書く
　・全ての空欄に異なる選択肢を書く
の２つは期待値としては同じになりますね。

この数列は収束が早くて n = 5 くらいであれば 0点の確率はほぼ 1/e なので
６割のギャンブルに乗れる人は2点以上を目指すのもいいかも＾＾

回答No.3

sokamone

すみません。ひとつ書き間違えしてました。

No.2の文章中の
Σ^{n}nCk*x[k] = 0
は、ｎ＞０の場合で、ｎ＝０のときは、
Σ^{0}0Ck*x[k] = １
にしないといけません。

回答No.1

kony0

私も同じ問題を質問したことがあります。^^

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=158149

お礼

回答ありがとうございます。

一応検索をかけてみたのですが、
見つからずに質問してしまいました。
名刺順列とかいう名前があったんですね。