"Yuzuru Hiraga" <hiraga@ulis.ac.jp> wrote in message news:401643FD.4020405@ulis.ac.jp...
> きれいな形で表せるかはまだわからないんだけど、力技でやるなら、
> とりあえず漸化式は作れる。
> 
> 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

ここでのM(t)はkにも依存しますからM(t,k)と書いて
もうちょっと簡単にしてみます。

C(t,i)=C(t,t-i)の性質とt-i⇒iの変数変換を行えば

M(t,k) = t^k - Σ_{i=1...t-1} C(t,i)M(i,k)

和を左辺へ移行してC(t,t)=1とM(i,0)=0を使って

Σ_{i=0...t} C(t,i)M(i,k) = t^k

と結構きれいにまとまります。ここに何らかの反転公式か
何かが使えればM(i,k)について解けそうなんですが
私はこれ以上わかりません。

ご存知の方、フォローお願いします。