A247299 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having a total of k h- and H-steps at level 0.

1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 3, 1, 2, 4, 3, 3, 4, 1, 5, 6, 9, 5, 6, 5, 1, 10, 15, 15, 16, 9, 10, 6, 1, 22, 33, 33, 32, 26, 16, 15, 7, 1, 50, 71, 78, 66, 60, 41, 27, 21, 8, 1, 113, 163, 171, 158, 125, 103, 64, 43, 28, 9, 1, 260, 374, 391, 360, 295, 225, 167, 99, 65, 36, 10, 1

Offset

0,9

Comments

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.

Row n contains n+1 entries.

Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).

T(n,0) = A166300(n).

Sum(k*T(n,k), k=0..n) = A247300(n)

Links

Alois P. Heinz, Rows n = 0..140, flattened

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 = 1/(1 - t*z - t*z^2 - z^3*g), where g is given by g = 1 + z*g + z^2*g + z^3*g^2.

Example

Row 3 is 1,0,2,1 because B(3) = {ud, hH, Hh, hhh}.
Triangle starts:
1;
0,1;
0,1,1;
1,0,2,1;
1,2,1,3,1;
2,4,3,3,4,1;

Maple

eqg := g = 1+z*g+z^2*g+z^3*g^2: g := RootOf(eqg, g): G := 1/(1-t*z-t*z^2-z^3*g): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 13 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 13 do seq(coeff(P[n], t, k), k = 0 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n or n<0, 0,
      `if`(n=0, 1, expand(`if`(y=0, x, 1)*(b(n-1, y)+
      b(n-2, y)) +b(n-2, y+1) +b(n-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 17 2014

Mathematica

b[n_, y_] := b[n, y] = If[y<0 || y>n || n<0, 0, If[n == 0, 1, Expand[If[y == 0, x, 1]*(b[n-1, y] + b[n-2, y]) + b[n-2, y+1] + b[n-1, y-1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Crossrefs

Cf. A004148, A166300, A247300,

Sequence in context: A212182 A236567 A360564 * A127586 A055893 A050221

Adjacent sequences: A247296 A247297 A247298 * A247300 A247301 A247302

Keyword

nonn,tabl

Author

Emeric Deutsch, Sep 17 2014

Status

approved