A182906 Triangle read by rows: T(n,k) is the number of weighted lattice paths in F[n] having endpoint height k (k<=floor(n/2)). The members of F[n] are paths of weight n that start at (0,0), do not go below 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.
1, 1, 2, 1, 4, 2, 8, 5, 1, 17, 12, 3, 37, 28, 9, 1, 82, 66, 25, 4, 185, 156, 66, 14, 1, 423, 370, 171, 44, 5, 978, 882, 437, 129, 20, 1, 2283, 2112, 1107, 364, 70, 6, 5373, 5079, 2790, 1000, 225, 27, 1, 12735, 12264
Offset: 0
Examples
T(4,1)=5. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and U=(1,1), D=(1,-1), we have hhU, hUh, Uhh, HU, and UH. Triangle starts: 1; 1; 2, 1; 4, 2; 8, 5, 1; 17, 12, 3; 37, 28, 9, 1;
Links
- M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.
Programs
-
Maple
g := ((1-z-z^2-sqrt((1+z+z^2)*(1-3*z+z^2)))*1/2)/z^3: G := g/(1-t*z^2*g); Gser := simplify(series(G, z = 0, 22)): for n from 0 to 14 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 14 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form T := proc (n, k) if k < 0 then 0 elif n < 0 then 0 elif (1/2)*n < k then 0 elif n = 0 and k = 0 then 1 else T(n-1, k)+T(n-1, 1+k)+T(n-2, k)+T(n-2, k-1) end if end proc: for n from 0 to 14 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do;
-
Maxima
T(n,k):=(k+1)*sum((binomial(i+1,n+1-i)*binomial(i+1,-i+n-k))/(i+1),i,0,n-k+1); /* Vladimir Kruchinin, Jan 25 2019 */
Formula
G.f.: G(t,z) = g/(1-tz^2*g), where g=g(z) is defined by g = 1 + z*g + z^2*g + z^3*g^2.
Rec. rel.: T(n,k) = T(n-1,k) + T(n-1,k+1) + T(n-2,k) + T(n-2,k-1); the 2nd Maple program makes use of this.
T(n,k) = (k+1)*Sum_{i=0..n-k+1} C(i+1,n+1-i)*C(i+1,-i+n-k)/(i+1). - Vladimir Kruchinin, Jan 25 2019
Comments