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, 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

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