|
uchinyan |
|
#24254及び#24259
残念ながら、次の漸化式の一般項は、今のところ求められていません。 A(n,k) = ��(i=0,k) [C(n-1,k-i) * (k-i)! * A(n-k+i-1,i)] ただ、少しまとめておきます。 まず、あきらかに、A(n.0) = 1 です。さらに、意味より、A(k+1,k) = k! もいえます。 さらに、 A(n,k) = A(n-1,k) + ��(i=0,k-1) [C(n-1,k-i) * (k-i)! * A(n-k+i-1,i)] なので、A(n,k-1) が分かれば、A(n,k) は n に関して足しあげることで原理的には求まります。 したがって、A(n,1), A(n,2), ... と順番に計算可能です。 なお、A(n,1) は、今回の問題の一番単純な拡張になっています。 これは、#24230及び#24240のロジックがそのまま使えて、A(n,1) = C(n,2) と求まりますが、 次のようにして漸化式からも求まります。 A(n,1) = A(n-1,1) + C(n-1,1) * 1! * A(n-2,0) = A(n-1,1) + C(n-1,1) = ... = A(2,1) + C(2,1) + C(3,1) + ... + C(n-2,1) + C(n-1,1) = 1 + C(2,1) + C(3,1) + ... + C(n-2,1) + C(n-1,1) ここでちょっとトリッキーですが、C(2,2) = 1 であることと、C(n,r) = C(n-1,r-1) + C(n-1,r) であることを使うと、 A(n,1) = C(2,2) + C(2,1) + C(3,1) + ... + C(n-2,1) + C(n-1,1) = C(3,2) + C(3,1) + ... + C(n-2,1) + C(n-1,1) = ... = C(n-1,2) + C(n-1,1) = C(n,2) 同様にして、A(n,2) は、 A(n,2) = A(n-1,2) + C(n-1,2) * 2! * A(n-3,0) + C(n-1,1) * 1! * A(n-2,1) = A(n-1,2) + C(n-1,2) * 2 + (n-1) * C(n-2,2) これから求まりますが、省略します。 |
|
ネコの住む家
12月18日（土） 13:50:25
MAIL:uchi@sco.bekkoame.ne.jp 24260 |