|
%I #37 Aug 27 2020 19:33:02
%S 1,2,4,8,18,42,100,242,592,1460,3624,9042,22656,56970,143688,363348,
%T 920886,2338566,5949148,15157874,38674978,98803052,252701484,
%U 646990518,1658066668,4252908542,10917422860,28046438252,72099983802,185469011130,477383400300
%N Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010.
%C 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 Vincenzo Librandi, <a href="/A078678/b078678.txt">Table of n, a(n) for n = 0..220</a>
%H Andrei Asinowski, 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 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 E. 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 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 G.f.: sqrt( ( 1 + x + x^2 ) / ( 1 - 3*x + x^2 ) ).
%F a(n) = sum( binomial( n - k + 2*floor(k/3), floor(k/3) )^2, k=0..n+floor(n/2)).
%F 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) ).
%F a(n) ~ 2 * ((3+sqrt(5))/2)^n / (5^(1/4)*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 21 2014
%F 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 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 For n = 2 : 0011, 0110, 1001, 1100.
%e For n = 3 : 000111, 011001, 100011, 110001, 001110, 011100, 100110, 111000.
%p a:= proc(n) option remember; `if`(n<5, [1, 2, 4, 8, 18][n+1],
%p (2*n*a(n-1)+(n-2)*a(n-2)+(2*n-8)*a(n-3)-(n-4)*a(n-4))/n)
%p end:
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Feb 13 2020
%t Table[SeriesCoefficient[Series[Sqrt[(1 + x + x^2)/(1 - 3 x + x^2)], {x, 0, n}], n], {n, 0, 40}]
%o (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 makelist(a(n),n,0,12); [Emanuele Munarini, Jul 07 2011]
%o (PARI) x='x+O('x^99); Vec(((1+x+x^2)/(1-3*x+x^2))^(1/2)) \\ _Altug Alkan_, Jul 18 2016
%Y Cf. A078679, A128588.
%Y Cf. A003440.
%Y Main diagonal of array A099172.
%Y Related to diagonal of rational functions: A268545-A268555.
%K nonn
%O 0,2
%A _Emanuele Munarini_, Dec 17 2002
|
