Ｎ個の値の大小関係の組み合わせ数

質問

Ｎ個の値の大小関係の組み合わせ数を求めるプログラムのアルゴリズムを考えていますがうまくいきません。（３個の値の場合は１３通り）
スマートに求める式をご存知の方、教えていただけないでしょうか

回答No.1

nag0720 · ベストアンサー

区別できるn個のものをk個の箱に、どの箱も少なくとも１つ入っているように分ける分け方の数をF(n,k)とすると、求める数は、
Σ[k=1…n]F(n,k)
で表せます。
また、F(n,k)は次の式で表せます。
F(n,k)=Σ[i=0…k-1]((-1)^i*(k-i)^n*kCi)

n=10まで計算してみたら下記のようになりました。
1,3,13,75,541,4683,47293,545835,7087261,102247563

お礼

迅速な回答ありがとうございました。
助かりました。