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!)
A099172 Array T(m, n) read by antidiagonals: number of binary strings with m 1's and n 0's without zigzags. 1
1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 2, 5, 5, 2, 1, 1, 2, 6, 8, 6, 2, 1, 1, 2, 7, 11, 11, 7, 2, 1, 1, 2, 8, 14, 18, 14, 8, 2, 1, 1, 2, 9, 17, 26, 26, 17, 9, 2, 1, 1, 2, 10, 20, 35, 42, 35, 20, 10, 2, 1, 1, 2, 11, 23, 45, 62, 62, 45, 23, 11, 2, 1, 1, 2, 12, 26, 56, 86, 100, 86, 56, 26, 12, 2, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

Table of n, a(n) for n=0..90.

E. Munarini and N. Z. Salvi, Binary strings without zigzags, [alternative link], 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], 2005-2007.

R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-372. See p. 269

FORMULA

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

T(m, n) = Sum{k=0..min(m+[m/2], n+[n/2]), C(m-k+2[k/3], [k/3])*C(n-k+2[k/3], [k/3]) }.

EXAMPLE

Array begins:

1, 1, 1,  1,  1,  1,   1,   1,

1, 2, 2,  2,  2,  2,   2,   2,

1, 2, 4,  5,  6,  7,   8,   9,

1, 2, 5,  8, 11, 14,  17,  20,

1, 2, 6, 11, 18, 26,  35,  45,

1, 2, 7, 14, 26, 42,  62,  86,

1, 2, 8, 17, 35, 62, 100, 150,

1, 2, 9, 20, 45, 86, 150, 242,

MAPLE

gf:=(1 + x*y + x^2*y^2)/(1 - x - y + x*y - x^2*y^2); seq(seq(coeff(series(coeff(series(gf, y, m+1), y, m), x, d-m+1), x, d-m), m=0..d), d=0..9);

MATHEMATICA

T[m_, n_] := Sum[Binomial[m - k + 2 Floor[k/3], Floor[k/3]] Binomial[n - k + 2 Floor[k/3], Floor[k/3]], {k, 0, Min[m+Floor[m/2], n+Floor[n/2]]}];

Table[T[m-n, n], {m, 0, 12}, {n, 0, m}] // Flatten (* Jean-François Alcover, Aug 17 2018 *)

PROG

(PARI) T(m, n)=sum(k=0, min(m+m\2, n+n\2), binomial(m-k+2*(k\3), k\3)*binomial(n-k+2*(k\3), k\3))

(PARI) T(n, k) = {x = xx + xx*O(xx^n); y = yy + yy*O(yy^k); polcoeff(polcoeff((1 + x*y + x^2*y^2)/(1 - x - y + x*y - x^2*y^2), n, xx), k, yy); } \\ Michel Marcus, Nov 25 2013

(PARI) {A(n, m) = if( n<0 || m<0, 0, polcoeff( polcoeff( (1 + x*y + x^2*y^2 ) / (1 - x - y + x*y - x^2*y^2) + x * O(x^n), n) + y * O(y^m), m))}; /* Michael Somos, Jun 06 2016 */

CROSSREFS

Main diagonal is A078678. Antidiagonal sums are A128588.

Sequence in context: A138015 A327742 A103444 * A214246 A214257 A214248

Adjacent sequences:  A099169 A099170 A099171 * A099173 A099174 A099175

KEYWORD

nonn,tabl

AUTHOR

Ralf Stephan, Oct 10 2004

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 June 15 04:47 EDT 2021. Contains 345043 sequences. (Running on oeis4.)