cp's OEIS Frontend

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

%I A078678 #45 Jan 12 2025 12:31:57
%S A078678 1,2,4,8,18,42,100,242,592,1460,3624,9042,22656,56970,143688,363348,
%T A078678 920886,2338566,5949148,15157874,38674978,98803052,252701484,
%U A078678 646990518,1658066668,4252908542,10917422860,28046438252,72099983802,185469011130,477383400300
%N A078678 Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.
%C A078678 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
%H A078678 Vincenzo Librandi, <a href="/A078678/b078678.txt">Table of n, a(n) for n = 0..220</a>
%H A078678 Andrei Asinowski and Cyril Banderier, <a href="https://doi.org/10.4230/LIPIcs.AofA.2020.1">On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution</a>, 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.
%H A078678 T. Doslic, <a href="https://doi.org/10.1007/s10440-009-9515-4">Seven lattice paths to log-convexity</a>, Acta Appl. Mathem. 110 (3) (2010) 1373-139, eq 4.
%H A078678 Emanuele Munarini and N. Z. Salvi, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s49zagaglia.html">Binary strings without zigzags</a>, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.
%H A078678 R. Pemantle and M. C. Wilson, <a href="https://arxiv.org/abs/math/0512548">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions</a>, arXiv:math/0512548 [math.CO], 2007.
%F A078678 G.f.: sqrt( ( 1 + x + x^2 ) / ( 1 - 3*x + x^2 ) ).
%F A078678 a(n) = Sum_{k=0..n+floor(n/2)} binomial( n - k + 2*floor(k/3), floor(k/3) )^2.
%F A078678 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.
%F A078678 a(n) ~ 2 * ((3+sqrt(5))/2)^n / (5^(1/4)*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 21 2014
%F A078678 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
%F A078678 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
%e A078678 For n = 2 : 0011, 0110, 1001, 1100.
%e A078678 For n = 3 : 000111, 011001, 100011, 110001, 001110, 011100, 100110, 111000.
%p A078678 a:= proc(n) option remember; `if`(n<5, [1, 2, 4, 8, 18][n+1],
%p A078678      (2*n*a(n-1)+(n-2)*a(n-2)+(2*n-8)*a(n-3)-(n-4)*a(n-4))/n)
%p A078678     end:
%p A078678 seq(a(n), n=0..40);  # _Alois P. Heinz_, Feb 13 2020
%t A078678 Table[SeriesCoefficient[Series[Sqrt[(1 + x + x^2)/(1 - 3 x + x^2)], {x, 0, n}], n], {n, 0, 40}]
%o A078678 (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);
%o A078678 makelist(a(n),n,0,12); /* _Emanuele Munarini_, Jul 07 2011 */
%o A078678 (PARI) my(x='x+O('x^99)); Vec(((1+x+x^2)/(1-3*x+x^2))^(1/2)) \\ _Altug Alkan_, Jul 18 2016
%Y A078678 Cf. A078679, A128588.
%Y A078678 Cf. A003440.
%Y A078678 Main diagonal of array A099172.
%Y A078678 Related to diagonal of rational functions: A268545-A268555.
%K A078678 nonn
%O A078678 0,2
%A A078678 _Emanuele Munarini_, Dec 17 2002