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

Author

Emanuele Munarini, Dec 17 2002

Keywords

• nonn

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

Examples

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..220
• Andrei Asinowski and 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.
• Emanuele 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.

Crossrefs

Cf. A078679, A128588.

Cf. A003440.

Main diagonal of array A099172.

Related to diagonal of rational functions: A268545-A268555.

Programs

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}]

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

my(x='x+O('x^99)); Vec(((1+x+x^2)/(1-3*x+x^2))^(1/2)) \\ Altug Alkan, Jul 18 2016

Formula

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

a(n) = Sum_{k=0..n+floor(n/2)} binomial( n - k + 2*floor(k/3), floor(k/3) )^2.

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)^2*( 2*n^2 - 6*n*k + 6*k^2 )/(n-k)^2, n > 0.

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