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

Comments

The paths need not end on the horizontal axis.

Number of entries in row n is 1+floor(n/2).

Sum of entries in row n is A182905(n).

T(n,0) = A004148(n+1).

T(n,1) = A166297(n+1).

Links

Table of n, a(n) for n=0..50.

M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

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

Example

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;

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;

Prog

(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 */

Crossrefs

Cf. A182905, A004148, A166297.

Sequence in context: A135530 A137206 A076736 * A193359 A344613 A106489

Adjacent sequences: A182903 A182904 A182905 * A182907 A182908 A182909

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 17 2010

Status

approved