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
Examples
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,
Links
- 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
Programs
-
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 *) -
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 */
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]) }.