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

あるいは 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

これを展開・整理すれば、あるいは全面的に考え直せばもっと
簡単になるかもしれないけど、とりあえず強引にプログラムして
みた限りでは大丈夫そうです。

（平賀＠筑波大）