假设有n=20,k=8   先看k，如果k是8，则说明string中的1至少有9个，因为只有连续的9个1才可能生成一个8，而如果存在不连续的1的话，那么1的个数必定大于9个，那么此时问题就如下：
如果只有9个1 那么所有1必定是连在一起的，即1 1 1 1 1 1 1 1 1 ，而此时的问题就转化为在1的间隙中插入11个0，求出其种数，由于1连续，所以只能在两旁插入，就只有C（12，1）*C（8，0）（组合数），
如果有10个1的话，那么在这10个1之间必定有一个空隙，即可能是1 1 1 1 1 0 1 1 1 1 1
也可能是 1 1 1 1 1 0 0 1 1 1 1 1，此时问题又转化为在10个1之间的九个空隙中，找出一个空隙，然后将其余的10个0放入到这3个空隙中（别忘了左右两个空隙总是存在的，即0可以随便放在string的最左边或最右边），那么问题又转化为C（11，2）*C（9，1）
接下去可以递推，11个1，12个1......的情况
其公式就为：
C（12，1）*C（8，0）+C（11，2）*C（9，1）+C（10，3）*C（10，2）+C（9，4）*C（11，3）+C（8，5）*C（12，4）+C（7，6）*C（13，5）
其中C（12，1）和C（11，2）..........：这个主要是用了插板法，当有11个0要插入到两个空隙时，可以转化为有11个相同的球，用一块板将其划分为两个部分，那么此时由于11个球，有12个空隙可以插入（包括左右空隙），所以是C（12，1），同样，C（11，2）即可转化为有10个球，中间有11个空隙，要用两块板将其划分为三个部分，那么就是C（11，2）

• Re:排列组合 (733) KISehomeFaNs 2016-02-23 13:52:02