login
A246187
Triangle read by rows: T(n,k) is the number of weighted lattice paths in F[n] having length k (length = number of steps). 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, 0, 1, 0, 2, 1, 0, 0, 5, 1, 0, 0, 4, 9, 1, 0, 0, 0, 17, 14, 1, 0, 0, 0, 8, 46, 20, 1, 0, 0, 0, 0, 49, 100, 27, 1, 0, 0, 0, 0, 16, 180, 190, 35, 1, 0, 0, 0, 0, 0, 129, 510, 329, 44, 1, 0, 0, 0, 0, 0, 32, 603, 1225, 532, 54, 1, 0, 0, 0, 0, 0, 0, 321, 2121, 2618, 816, 65, 1, 0, 0, 0, 0, 0, 0, 64, 1827, 6202, 5124, 1200, 77, 1
OFFSET
0,5
COMMENTS
The paths need not end on the horizontal axis.
Number of entries in row n is n+1.
Sum of entries in row n is A182905(n).
Sum of entries in column k is A001700(k).
LINKS
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-t*z^2*g), where g=g(t,z) satisfies g = 1 + t*z*g + t*z^2*g +t^2*z^3*g^2.
The g.f. G(t,z) satisfies t*z^2*(1 - 2*t*z - 2*t*z^2) + (1 - t*z - 3*t*z^2)*G - 1 = 0.
EXAMPLE
Row 2 is 0,2,1; indeed, the weight-2 paths are hh, H, and U (where h=(1,0) of weight 1, H=(1,0) of weight 2, and U=(1,1)) and their lengths are 2,1,and 1, respectively.
Triangle starts:
1;
0,1;
0,2,1;
0,0,5,1;
0,0,4,9,1;
MAPLE
eq := t*z^2*(1-2*t*z-2*t*z^2)*G^2+(1-t*z-3*t*z^2)*G-1 = 0: GG := RootOf(eq, G): Gser := simplify(series(GG, z = 0, 20)): for n from 0 to 18 do P[n] := sort(expand(coeff(Gser, z, n))) end do; for n from 0 to 18 do seq(coeff(P[n], t, j), j = 0 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0, 0,
`if`(n=0, 1, expand(x*(b(n-1, y) +b(n-1, y-1)+
`if`(n>1, b(n-2, y) +b(n-2, y+1), 0)))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..14); # Alois P. Heinz, Aug 29 2014
MATHEMATICA
b[n_, y_] := b[n, y] = If[y<0, 0, If[n==0, 1, Expand[x*(b[n-1, y] + b[n-1, y-1] + If[n>1, b[n-2, y] + b[n-2, y+1], 0])]]]; 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, Nov 07 2015, after Alois P. Heinz *)
CROSSREFS
Sequence in context: A136129 A278213 A034093 * A079508 A057150 A185663
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 29 2014
STATUS
approved