N種類のデータをk個（重複を許して）並べた場合のデータの種類数の
平均を求めたいと考えています。

たとえば、2種類のデータを3個並べる場合
000
001
010
011
100
101
110
111
の8通りがあり、その中でデータ種類数が1のものが2つ、2のものが6つあります。
すなわち、(1*2+2*6)/8=14/8 となります。

この場合から考えるとデータ種類数がtのものの個数m_tは
m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
と考えられます。
N=2 k=3ならば
m_1={(1^3)*2C1}-0=1*2=2
m_2={(2^3)*2C2}-{(1^3)*2C1}=8*1-1*2=6
となり、前記のものと一致します。
これは、データt種類をk個適当に並べる方法がt^kであり、
そのt種類をN個の中から選ぶ方法が_N C_tであるところから、
きています。(t-1の分を引いてるのはt-1種類しか選んでいないものを排除するため)
Σt*m_t / N^k
が種類数の平均となるはずです。


さて、k=36 N=32でやってみました。するとt=19あたりで、
本来の全数すなわちN^kを超えます。
とすると、上の仮定は間違えていることになります。
どうやって考えればよいのでしょうか。

-- 
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp