一个排列组合的问题：有18位的二进制环形编码（18位连成一圈，只能有一个连续的4个1作为识别码），请问这种组合共有多少种？

有18位的二进制环形编码（18位连成一个圆圈，只能有一次连续的4个1作为识别码），请问这种组合共有多少种？

解决方案 »

  1.   

    先计算断开的排列数，需要考虑头尾连接后的情况
    然后除以18
      

  2.   

    147456？怎么算的，应该少于2的14次方才对呀。
      

  3.   

    因为是环形，所以还要乘以18.位不同也应算作一种方案。
      

  4.   

    其排列如下：（从第一位开始，数字表示此位的排列数）
    222212221222122211 ＝ 2^13 * 18 = 147456
      

  5.   

    只能有一次连续的4个1作为识别码，连续的4个1在哪呢？
      

  6.   

    51696种，因为有且只有4个连续的1的序列，所以这4个连续的1前后必须是0，也就是011110，这样就剩下12位了（18-4-2=12）因为是环形的，所以可以求出12位中不包含4个连续1的数字的个数，然后乘以18就是要求出的数。12位中不包含4个连续1的数字的个数，可以这样求出，用（（2^12）-（含有4个连续1的数字的个数））也就是说结果是18×（（2^12）-（12位中含有4个连续1的数字的个数））=18×（4096-1224）=18×2872=51696