青龙问题

来源:百度知道 编辑:UC知道 时间:2024/05/28 11:31:22
将若干个0与1排成一行(如00101,11111,10100等)叫做“龙”,龙中数字0和1的总个数叫做龙的长度。没有两个1相连的龙叫做“青龙”(如10100,00101)。请问,长度为10的青龙共有多少个?
答案是144,但是为什么?告诉一下组合公式行吗?

没有1,1种
有1个1,相当于把1插在9个0中(边上也可以),有10种C(1,10)
有2个1,相当于把2插在8个0中(边上也可以),C(2,9)-------2是上标,9是下标.
有3个1,相当于把3插在7个0中(边上也可以),C(3,8)
有4个1,相当于把4插在6个0中(边上也可以),C(4,7)
有5个1,相当于把5插在5个0中(边上也可以),C(5,6)
再多就不可能了
所以一共1+C(1,10)+C(2,9)+C(3,8)+C(4,7)+C(5,6)=144

用枚举法作出如下,供你参考。
因长度为10,所以0和1共10个。不能有6个1,最多5个1,否则有2个1相连。
(1)1个1:只有10种;
(2)2个1:101型,把101看作一个整体,与7个0作组合,有C(81)=8(种);随着两个1中间的0的个数增加,依次为:1001型, 10001型,100001型,……,1000000001型,分别有7,6,5,4,3,2,1种。因此,2个1的一共有8+7+…+2+1=36(种)。
(3)3个1:10101型,有C(61)=6(种);随着后两个1中间的0的个数的增加,依次为:101001型,1010001型,……,1010000001型,分别有5,4,3,2,1种;由对称性知,前两个1中间的0的个数增加时,也有5,4,3,2,1种;因此,这种1个0与多个0的组合类型的总数=(5+4+3+2+1)*2=30(种)。
还有,1001001型,有C(41)=4(种);与上述方法相同,这种两个0与多个(两个以上)0的组合类型的总数=(3+2+1)*2=12(种);
还有,100010001型,有C(21)=2(种);与上述方法相同,这种三个0与4个0的组合类型共有2种。这种类型的计有2+2=4(种)。
总之,3个1的一共有6+30+4+12+4=56(种)。
(4)4个1:1010101型,有C(41)=4(种);两个1中间有1个是两个0,共有三种情形,每种情形都有3种,共有3*3=9(种);两个1中间有1个是三个0,共有三种情形,每种情形都有2种,共有2*3=6(种);两个1中间有1个是四个0,共有三