A182903 Triangle read by rows: T(n,k) is the number of weighted lattice paths in L_n having k peaks.The members of L_n are paths of weight n that start at (0,0), end on the horizontal axis and whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps. A peak is a (1,1)-step followed by a (1,-1)-step.
1, 1, 2, 4, 1, 9, 2, 21, 5, 48, 14, 1, 112, 38, 3, 263, 104, 9, 623, 276, 31, 1, 1484, 730, 99, 4, 3550, 1921, 309, 14, 8525, 5034, 929, 56, 1, 20537, 13145, 2739, 205, 5, 49612, 34208, 7956, 716, 20, 120136, 88780, 22804, 2394, 90, 1, 291519, 229860, 64650
Offset: 0
Examples
T(7,2)=3. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and U=(1,1), D=(1,-1), we have hUDUD, UDhUD, UDUDh. Triangle starts: 1; 1; 2; 4,1; 9,2; 21,5; 48,14,1;
References
- M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.
- E. Munarini, N. Zagaglia Salvi, On the rank polynomial of the lattice of order ideals of fences and crowns, Discrete Mathematics 259 (2002), 163-177.
Formula
Let F=F(t,s,x,y,z) be the 5-variate g.f. of the considered weighted lattice paths, where z marks weight, t (s) marks number of peaks (valleys), x (y) indicates that the path starts with a (1,1)-step ((1,-1)-step). Then F(t,s,x,y,z)=1+z(1+z)F(t,s,1,1,z)+xz^3[t+H(t,s,z)-1]F(t,s,s,1,z)+yz^3[s+H(s,t,z)-1]F(t,s,1,t,z), where H=H(t,s,z) is given by H=1+zH+z^2*H+z^3*(t-1+H)[s(H-1-zH-z^2*H)+1+zH+z^2*H] (see A182900).
Comments