工繊大の塚本です.

In article <bvavbu$2mqd$1@news2.rim.or.jp>
KUROSAWA Takashi <tabby@yk.rim.or.jp> writes:
> 50 種類を集めるのに掛かる回数は 225 回ではないですか?
> サイコロだと 15 回。
> 　n/n + n/(n-1) + n/(n-2) + … n/1
> 
> サイコロで考えると…
> 　○1 番目の目
> 　　どれが出てもイイから確率 6/6、出るまでに掛かる回数はその
> 　　逆数の 6/6 回。
> 　○2 番目の目
> 　　最初に出た 1 つを避けるから確率 5/6、出るまでの回数は逆数
> 　　の 6/5 回。
> 　〜(snip)〜
> 　○6 番目の目
> 　　既出の 5 つを避けるから確率 1/6、出るまでの回数は逆数の
> 　　6/1 回。
> …という、個々の理想の試行回数を足し合わせて…
> 　6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1
> 　　= 147/10
> 　　= 14.7、切り上げて 15 回
> …となります。コンピュータで乱数を廻して検証しました。

良い考え方だと思います.

 k 種類の文字が random に出現するとき, n 回目にちょうど k 種類出揃う
というのは, n-1 回までが k-1 種類の文字がちょうど現れるような列に
なっていて, n 回目に残りの文字が出るという場合ですから, その確率は

  (Σ_{i=0}^{k-1} (-1)^i C(k-1, i) (k-1-i)^{n-1})/k^{n-1}

その回数の期待値 E は

  E = Σ_{n=k}^∞ n (Σ_{i=0}^{k-1} (-1)^i C(k-1, i) (k-1-i)^{n-1})/k^{n-1}
    = Σ_{i=0}^{k-1} (-1)^i C(k-1, i) Σ_{n=k}^∞ n ((k-1-i)/k)^{n-1}.

ここで S(X) = Σ_{n=k}^∞ n X^{n-1} とおくと,

  S(X) = (d/dX) Σ_{n=k}^∞ X^n
       = (d/dX) (X^k/(1-X))
       = k X^{k-1}/(1-X) + X^k/(1-X)^2.

よって, 1 - (k-1-i)/k = (i+1)/k, C(k-1, i)*(k/(i+1)) = C(k, i+1) ゆえ,

  E = Σ_{i=0}^{k-1} (-1)^i C(k-1, i)
                            (k^2/(i+1) + k(k-1-i)/(i+1)^2)
                            ((k-1-i)/k)^{k-1}.
    = Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k + k/(i+1) - 1) ((k-1-i)/k)^{k-1}

さて, m < k なら m 文字の列に k 種類の文字が現れることはないので,

  Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k-1-i)^m
  = k^m - Σ_{i=0}^k (-1)^i C(k, i) (k-i)^m
  = k^m

となることに注意すると,

  E = k - 1 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1)) ((k-1-i)/k)^{k-1}
    = k - 1 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1) - 1) ((k-1-i)/k)^{k-2}
    = k - 2 + Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1)) ((k-1-i)/k)^{k-2}
    = …
    = Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (k/(i+1))

です.

  Σ_{i=0}^{k-1} (-1)^i C(k, i+1) (1/(i+1))
  = Σ_{i=0}^{k-1} (-1)^i C(k, i+1) ∫_0^1 x^i dx
  = ∫_0^1 (Σ_{i=0}^{k-1} (-1)^i C(k, i+1) x^i) dx
  = ∫_0^1 (1 - (Σ_{i=0}^k (-1)^i C(k, i) x^i))/x dx
  = ∫_0^1 (1 - (1-x)^k)/x dx
  = ∫_0^1 (1 - t^k)/(1-t) dt
  = ∫_0^1 Σ_{i=0}^{k-1} t^i dt
  = Σ_{i=0}^{k-1} 1/(i+1) 

を代入して,

  E = k Σ_{i=0}^{k-1} 1/(i+1) 
  
が直接計算でも分かります. 面白い.
-- 
塚本千秋@応用数学.高分子学科.繊維学部.京都工芸繊維大学
Tsukamoto, C. : chiaki@ipc.kit.ac.jp