|
Search: id:A078678
|
|
|
| A078678 |
|
Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010. |
|
+0
4
|
|
| 1, 2, 4, 8, 18, 42, 100, 242, 592, 1460, 3624, 9042, 22656, 56970, 143688, 363348, 920886, 2338566, 5949148, 15157874, 38674978, 98803052, 252701484, 646990518, 1658066668, 4252908542, 10917422860, 28046438252, 72099983802, 185469011130
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
REFERENCES
|
E. Munarini and N. Zagaglia Salvi, Binary strings without zigzags, preprint.
|
|
LINKS
|
E. Munarini and N. Z. Salvi, Binary strings without zigzags
|
|
FORMULA
|
a(n) = sum( binomial( n - k + 2 floor(k/3), floor(k/3) )^2, k=0..n+floor(n/2)); a(n) = sum( binomial( n - k, k )^2 ( 2 n^2 - 6 n k + 6 k^2 )/( n - k )^2 ), k=0..floor(n/2) ). Recurrence: (n+6) a(n+6) - (n+7) a(n+5) - 2(n+5) a(n+4) - 5(n+3) a(n+3) - 2(n+1) a(n+2) - (n-1) a(n+1) + n a(n) = 0. G.f.: A(x) = sqrt( ( 1 + x + x^2 ) / ( 1 - 3 x + x^2 ) )
|
|
EXAMPLE
|
For n = 2 : 0011, 0110, 1001, 1100. For n = 3 : 000111, 011001, 100011, 110001, 001110, 011100, 100110, 111000.
|
|
MATHEMATICA
|
Table[SeriesCoefficient[Series[Sqrt[(1 + x + x^2)/(1 - 3 x + x^2)], {x, 0, n}], n], {n, 0, 40}]
|
|
CROSSREFS
|
Cf. A078679.
Cf. A003440.
Main diagonal of array A099172.
Adjacent sequences: A078675 A078676 A078677 this_sequence A078679 A078680 A078681
Sequence in context: A112483 A057151 A026699 this_sequence A027056 A024428 A049075
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Emanuele Munarini (munarini(AT)mate.polimi.it), Dec 17 2002
|
|
|
Search completed in 0.002 seconds
|
