A119473 Triangle read by rows: T(n,k) is number of binary words of length n and having k runs of 0's of odd length, 0 <= k <= ceiling(n/2). (A run of 0's is a subsequence of consecutive 0's of maximal length.)
1, 1, 1, 2, 2, 3, 4, 1, 5, 8, 3, 8, 15, 8, 1, 13, 28, 19, 4, 21, 51, 42, 13, 1, 34, 92, 89, 36, 5, 55, 164, 182, 91, 19, 1, 89, 290, 363, 216, 60, 6, 144, 509, 709, 489, 170, 26, 1, 233, 888, 1362, 1068, 446, 92, 7, 377, 1541, 2580, 2266, 1105, 288, 34, 1, 610, 2662, 4830
Offset: 0
Examples
T(5,2)=8 because we have 00010, 01000, 01011, 01101, 01110, 10101, 10110 and 11010. T(5,2)=8 because there are 8 compositions of 6 that have 2 even parts: 4+2, 2+4, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+2+1, 1+2+1+2, 1+1+2+2. - _Geoffrey Critzer_, Mar 03 2012 Triangle starts: 1; 1, 1; 2, 2; 3, 4, 1; 5, 8, 3; 8, 15, 8, 1; From _Philippe Deléham_, Dec 07 2011: (Start) Triangle (1,1,-1,0,0,0...) DELTA (1,-1,0,0,0,...) begins: 1; 1, 1; 2, 2, 0; 3, 4, 1, 0; 5, 8, 3, 0, 0; 8, 15, 8, 1, 0, 0; 13, 28, 19, 4, 0, 0, 0; 21, 51, 42, 13, 1, 0, 0, 0; 34, 92, 89, 36, 5, 0, 0, 0, 0; ... (End)
References
- I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley and Sons, 1983, page 54.
Links
- Alois P. Heinz, Rows n = 0..200, flattened
- Rigoberto Flórez, Javier González, Mateo Matijasevick, Cristhian Pardo, José Luis Ramírez, Lina Simbaqueba, and Fabio Velandia, Lattice paths in corridors and cyclic corridors, Contrib. Disc. Math. (2024) Vol. 19. No. 2, 36-55. See p. 17.
- Ralph Grimaldi and Silvia Heubach, Binary strings without odd runs of zeros, Ars Combinatoria 75 (2005), 241-255.
Programs
-
Maple
G:=(1+t*z)/(1-z-z^2-t*z^2): Gser:=simplify(series(G,z=0,18)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(coeff(Gser,z^n)) od: for n from 0 to 14 do seq(coeff(P[n],t,j),j=0..ceil(n/2)) od; # yields sequence in triangular form # second Maple program: b:= proc(n) option remember; local j; if n=0 then 1 else []; for j to n do zip((x, y)->x+y, %, [`if`(irem(j, 2)=0, 0, NULL), b(n-j)], 0) od; %[] fi end: T:= n-> b(n+1): seq(T(n), n=0..14); # Alois P. Heinz, May 23 2013 -
Mathematica
f[list_] := Select[list, # > 0 &]; nn = 15; a = (x + y x^2)/(1 - x^2); Map[f, Drop[CoefficientList[Series[1/(1 - a), {x, 0, nn}], {x, y}], 1]] // Flatten (* Geoffrey Critzer, Mar 03 2012 *)
Formula
G.f.: (1+t*z)/(1-z-z^2-t*z^2).
G.f. of column k (k>=1): z^(2*k-1)*(1-z^2)/(1-z-z^2)^(k+1).
T(n,k) = T(n-1,k) + T(n-2,k) + T(n-2,k-1). - Philippe Deléham, Dec 07 2011
Sum_{k=0..n} T(n,k)*x^k = A000045(n+1), A000079(n), A105476(n+1), A159612(n+1), A189732(n+1) for x = 0, 1, 2, 3, 4 respectively. - Philippe Deléham, Dec 07 2011
G.f.: (1+x*y)*T(0)/2, where T(k) = 1 + 1/(1 - (2*k+1+ x*(1+y))*x/((2*k+2+ x*(1+y))*x + 1/T(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 06 2013
Comments