现在的位置: 首页 > 综合 > 正文

序关系计数问题

2017年12月23日 ⁄ 综合 ⁄ 共 364字 ⁄ 字号 评论关闭

现在有N个字母代表N个变量,请用'<' 或者'='号将这些字幕连接起来成为一个序,比如对于三个字母A,B,C ,有13种序的关系。

A<B<C. A<B=C,A<C<B等等。

现在编程求出对N个字母可以排出多少种序的关系?

 

首先注意=号跟<号还不一样,因为A=B与B=A是一样的,只能算一个。

而<号却可以将一个连接分为两个独立的部分,也就是根据乘法原理,最后的关系数是左边和右边的相乘。

现在我们枚举第一个小于号出现的位置,N个字母有N-1个空,所以第一个小于号出现的位置k 满足  1<=k<=N-1,在这个位置左边都是=号,所以根据乘法原理,左边的关系数就是从N个选出K个字母放在左边全相等,而右边则变成一个(N-K)大小的子问题,可以递归求解。

因此可以得出通项公式:

F[n] = Sum{ C(k,n) * F[n-k]  ,  1<=k<=n-1 }

 

抱歉!评论已关闭.