现在有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 }