[求助] 想求一个数列的通项没求出来

原本是想求一个数列的和没求出来，转换了一下变成求另一个数列的通项问题，还是求不出来。诶，太后悔大学期间把数学都丢光了，这么简单的问题都解决不了。就像老爸说的，数学都没学好怎么写程序 T T

以nPr的形式来表示有从n个元素中取r个的排列。我需要求的是n个元素取1个、2个一直到取n个的排列的可能情况的和。也就是要求：
∑(i=1, n) nPi
因为nPr = n! / (n-r)!，所以这个式子基本上也应该是阶乘的和的某种形式。但我就是没想到如何化简……

反正也想不出来，干脆就写了段程序来观察这个和有什么特征。

irb(main):001:0> def fact(n)
irb(main):002:1>   case n
irb(main):003:2>   when 0: 1
irb(main):004:2>   else (1..n).inject {|product,i| product*i }
irb(main):005:2>   end
irb(main):006:1> end
=> nil
irb(main):007:0> def perm(n,r)
irb(main):008:1>   fact(n)/fact(n-r)
irb(main):009:1> end
=> nil
irb(main):010:0> def sum_perm(n)
irb(main):011:1>   (0..n).inject {|sum,i| sum+perm(n,i) }
irb(main):012:1> end
=> nil
irb(main):013:0> sum_perm 1
=> 1
irb(main):014:0> sum_perm 2
=> 4
irb(main):015:0> sum_perm 3
=> 15
irb(main):016:0> sum_perm 4
=> 64
irb(main):017:0> sum_perm 5
=> 325
irb(main):018:0> def sum_perm_1(n)
irb(main):019:1>   case n
irb(main):020:2>   when 1: 1
irb(main):021:2>   else n*(sum_perm_1(n-1)+1)
irb(main):022:2>   end
irb(main):023:1> end
=> nil
irb(main):024:0> sum_perm_1 5
=> 325

试到sum_perm 5的时候突然发觉这个和自身作为一个数列非常有规律。把这个数列称为S，则：
S(n) = n*(S(n-1)+1)，并且S(1) = 1
所以定义了sum_perm_1来实现这个递归，算出来的结果果然跟原先的求和函数一样。

展开证明了一下，发现
S(n) = n*S(n-1) + n
= n*(n-1)*S(n-2) + n!/(n-1)! + n!/(n-2)!
...
= n! + n!/(n-1)! + n!/(n-2)! + ... + n!/(n-(n-1))!
= nPn + nP1 + nP2 + ... + nPn-1
= ∑(i=1, n) nPi

于是这个S(n)就是我要求的和没错了。但是S(n) = n*(S(n-1)+1)这个递归关系到底要怎么化简才能得到一般的通项我真是想不出来了。该怎么凑出个等比或者等差的式子出来呢……呜呜 T T

总之先记下来吧，回头再想。

评论

2 楼 RednaxelaFX 2008-12-15  

lwwin 写道

为什么一定会是等比或者等差的式子^^？

没啦，如果能通过换元凑出等比或等差的式子就方便化简嘛。但这个问题或许就换不出这种形式……

1 楼 lwwin 2008-12-15  

为什么一定会是等比或者等差的式子^^？