Yuzuru Hiragaさんの<401643FD.4020405@ulis.ac.jp>から
>
>
>Yoshitaka Ikeda wrote:
>> N種類のデータをk個（重複を許して）並べた場合のデータの種類数の
>> 平均を求めたいと考えています。
> ...
>> この場合から考えるとデータ種類数がtのものの個数m_tは
>> m_t={(t^k)*_N C_t}-{((t-1)^k)*_N C_(t-1)}
>> と考えられます。
>
>まず t>k なら m_t は 0 にならなければならないけど、
>上の式ではそれが現れていませんよね。

なんか、うまくまとめられるかなと思ってまとめちゃったんですが
まとめる前の式が間違っていたのでした。

># 以下２項係数 _N C_t は C(N, t) のように書きます。
>
>> これは、データt種類をk個適当に並べる方法がt^kであり、
>> そのt種類をN個の中から選ぶ方法が_N C_tであるところから、
>> きています。
>
>これがすでに間違っていることは N=3 ぐらいを
>見てもわかりますね。（それぐらいチェックしようよ）
>
>これだと３色以下で２個並べる方法は：
>　2^2 * C(3, 2) = 12 通り
>あることになるけど、実際には 3^2 = 9 通りしかない。
>同じものを重複して数えているからです。
>具体的には、下のように aa, bb, cc が２度数えられている：
>　aa ab ba bb
>　bb bc cb cc
>　cc ca ac aa

そうですね。1種類しか使っていないものが、3^1とおりと数えてしまったので
すが、ここはC(3,2)*(C2,1)=6と数えるべきだったのでした。

>あるいは N=3, k=3 だと、m_3 は 3! = 6 でなければならないのに、
>上の式だと 3 になってしまう。今度は重複分の引きすぎですね。
>
>=====
>きれいな形で表せるかはまだわからないんだけど、力技でやるなら、
>とりあえず漸化式は作れる。
>
>M(t) を、ちょうど t 種類のデータを使って作れる長さ k の
>データ列の個数とします（k は文脈で決まる）。
>すると池田さんの m_t は：
>　m_t = C(N, t)*M(t)
>になります。
>ここで M(t) は、t 種類（以内）のデータで作れる総数 t^k から
>t 種類未満のデータしか使っていないものを引けばいいから：
>　M(t) = t^k - C(t, 1)M(t-1) - C(t,2)M(t-2) - ... - C(t,t-1)M(1)
>　　　　= t^k - Σ_{i=1...t-1} C(t,i)M(t-i)
>　M(1) = 1
>
>これを展開・整理すれば、あるいは全面的に考え直せばもっと
>簡単になるかもしれないけど、とりあえず強引にプログラムして
>みた限りでは大丈夫そうです。

とりあえず、何かきれいな式を出そうという目的ではなく、確率計算をした
かったので、このとおりにプログラムを作ってみたところ、大きな値でもほぼ
予想通りの矛盾のない結果がでました。
#ちなみに、ほしかったのは、N=32,k=36だったのでした。

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