How many 12-digit binary sequences exist with no two ones(11) neighboring each other?.
How many 12-digit binary sequences exist with no 3 ones(111) neighboring each other?.
Leading zeros allowed.

Part 1:

A given sequence can contain zero to six 1's.

Any sequence that does not begin with a 1 can be seen as a combination of "01" groups and "0" digits. The number of such combinations containing n "01" groups is C(12-n,n).

That leaves, though, those that begin with a 1. The remaining 11 digits can then contain up to five "01" groups with the remainder as 0's. This is C(11-n,n) for n's less than 6.

 n   C(12-n,n) C(11-n,n)
 0       1       1
 1       11      10
 2       45      36
 3       84      56
 4       70      35
 5       21      6
 6       1

The total adds up to 377.

This program merely facilitated the calculations:

list
   10        for N1s=0 to 6
   20         Pieces=12-N1s
   30         Tot=Tot+combi(Pieces,N1s)
   40         print N1s,combi(Pieces,N1s),
   50         Pieces=11-N1s
   55         if Pieces>=N1s then
   60          :Tot=Tot+combi(Pieces,N1s)
   70          :print combi(Pieces,N1s)
   75         :else print
   80        next
  200   print Tot
OK

Verification:

DECLARE SUB choose (w!)
DIM SHARED d(12), ct

choose 1
PRINT ct

SUB choose (w)
  IF w = 1 THEN
   stp = 1
  ELSE
   stp = 1 - d(w - 1)
  END IF
  FOR c = 0 TO stp
    d(w) = c
    IF w = 12 THEN
      ct = ct + 1
     ELSE
      choose w + 1
    END IF
  NEXT
END SUB

resulting in 377.

Part 2:

This is harder. I don't have an analytic solution, just this exhaustive search:

DECLARE SUB choose (w!)
DIM SHARED d(12), ct

choose 1
PRINT ct

SUB choose (w)
  IF w = 1 OR w = 2 THEN
   stp = 1
  ELSE
   stp = 1 - INT((d(w - 1) + d(w - 2)) / 2)
  END IF
  FOR c = 0 TO stp
    d(w) = c
    IF w = 12 THEN
      ct = ct + 1
     ELSE
      choose w + 1
    END IF
  NEXT
END SUB

finds 1705 sequences without "111".

Posted by Charlie on 2010-04-23 14:06:46