|
Search: id:A143281
|
|
|
| A143281 |
|
Number of binary words of length n containing at least one subword 101 and no subword 11. |
|
+0
2
|
|
| 0, 0, 0, 1, 2, 4, 8, 15, 27, 48, 84, 145, 248, 421, 710, 1191, 1989, 3309, 5487, 9073, 14966, 24634, 40472, 66384, 108729, 177858, 290610, 474364, 773615, 1260643, 2052818, 3340662, 5433345, 8832432, 14351403, 23309326, 37844645, 61423513
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
FORMULA
|
G.f.: x^3/((x^2+x-1)(x^3+x-1)). a(n)=A000045(n+2)-A000930(n+2).
|
|
EXAMPLE
|
a(6)=8 because 8 binary words of length 6 have at least one substring 101 and no substring 11: 000101, 001010, 010100, 101000, 010101, 101010, 101001, 100101.
|
|
MAPLE
|
a := proc (m) option remember; local M; M := Matrix (2*m+3, (i, j)-> if m=0 and i=1 and j=1 then 2 elif (i=j-1 and i <> m+1) or (j=1 and member (i, [1, m+1])) or (j=m+2 and member(i, [m+2, 2*m+3])) then 1 else 0 fi); if m=0 then RETURN (proc(n) local K; K := M^(n+m+1); K[m+1, 1]/2-K[m+2, m+2] end) else RETURN (proc(n) local K; K := M^(n+m+1); K[m+1, 1]-K[m+2, m+2] end) fi end(1); seq (a(n), n=0..50);
|
|
CROSSREFS
|
Cf. A000045, A000930, 1st column of A143291.
Sequence in context: A054174 A001523 A000126 this_sequence A098057 A074029 A138653
Adjacent sequences: A143278 A143279 A143280 this_sequence A143282 A143283 A143284
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 04 2008
|
|
|
Search completed in 0.002 seconds
|
