login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078678 Number of binary strings with n 1's and n 0's avoiding zigzags, that is avoiding the substrings 101 and 010. 6
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 03:29 EDT 2021. Contains 346347 sequences. (Running on oeis4.)