A078678 Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.

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, 477383400300

Offset

0,2

Comments

Also number of Grand Dyck paths of length 2*n with no zigzags, that is, with no factors UDU or DUD. [Emanuele Munarini, Jul 07 2011]

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..220

Andrei Asinowski, Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.

T. Doslic, Seven lattice paths to log-convexity, Acta Appl. Mathem. 110 (3) (2010) 1373-139, eq 4.

E. Munarini and N. Z. Salvi, Binary strings without zigzags, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.

R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, arXiv:math/0512548 [math.CO], 2007.

Formula

G.f.: sqrt( ( 1 + x + x^2 ) / ( 1 - 3*x + x^2 ) ).

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) ).

a(n) ~ 2 * ((3+sqrt(5))/2)^n / (5^(1/4)*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 21 2014

a(n) = [x^n y^n](1+x*y+x^2*y^2)/(1-x-y+x*y-x^2*y^2). - Gheorghe Coserea, Jul 18 2016

D-finite with recurrence: n*a(n) -2*n*a(n-1) +(-n+2)*a(n-2) +2*(-n+4)*a(n-3) +(n-4)*a(n-4)=0. [Doslic] - R. J. Mathar, Jun 21 2018

Example

For n = 2 : 0011, 0110, 1001, 1100.
For n = 3 : 000111, 011001, 100011, 110001, 001110, 011100, 100110, 111000.

Maple

a:= proc(n) option remember; `if`(n<5, [1, 2, 4, 8, 18][n+1],
     (2*n*a(n-1)+(n-2)*a(n-2)+(2*n-8)*a(n-3)-(n-4)*a(n-4))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 13 2020

Mathematica

Table[SeriesCoefficient[Series[Sqrt[(1 + x + x^2)/(1 - 3 x + x^2)], {x, 0, n}], n], {n, 0, 40}]

Prog

(Maxima) a(n):=coeff(taylor((1+x+x^2)/sqrt(1-2*x-x^2-2*x^3+x^4), x, 0, n), x, n);
makelist(a(n), n, 0, 12); [Emanuele Munarini, Jul 07 2011]
(PARI) x='x+O('x^99); Vec(((1+x+x^2)/(1-3*x+x^2))^(1/2)) \\ Altug Alkan, Jul 18 2016

Crossrefs

Cf. A078679, A128588.

Cf. A003440.

Main diagonal of array A099172.

Related to diagonal of rational functions: A268545-A268555.

Sequence in context: A057151 A026699 A182780 * A261492 A027056 A024428

Adjacent sequences: A078675 A078676 A078677 * A078679 A078680 A078681

Keyword

nonn

Author

Emanuele Munarini, Dec 17 2002

Status

approved