A246177 Triangle read by rows: T(n,k) is the number of weighted lattice paths in B(n) such that the area between the x-axis and the path is k.

1, 1, 2, 3, 1, 5, 2, 1, 8, 5, 3, 1, 13, 10, 8, 4, 2, 21, 20, 18, 12, 7, 3, 1, 34, 38, 39, 30, 22, 12, 7, 2, 1, 55, 71, 80, 70, 57, 39, 26, 14, 7, 3, 1, 89, 130, 160, 154, 138, 106, 81, 52, 34, 18, 10, 4, 2, 144, 235, 312, 327, 315, 267, 220, 163, 118, 78, 49, 28, 16, 7, 3, 1

Offset: 0

Author

Emeric Deutsch, Aug 20 2014

Keywords

• nonn
• tabf

Comments

The members of B(n) are paths of weight n that start at (0,0), end on but never 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.

Apparently, number of terms in row n is 1+floor(n^2/8).

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

T(n,0) = A000045(n+1) (the Fibonacci numbers).

T(n,1) = A001629(n-1) (n>=1).

Examples

			Row 3 is 3,1; indeed, B(3) consists of the paths hhh, hH, Hh, UD with areas 0,0,0,1, respectively.
Triangle starts:
   1;
   1;
   2;
   3,   1;
   5,   2,   1;
   8,   5,   3,   1;
  13,  10,   8,   4,   2;
  21,  20,  18,  12,   7,   3,  1;
  34,  38,  39,  30,  22,  12,  7,  2,  1;
  55,  71,  80,  70,  57,  39, 26, 14,  7,  3,  1;
  89, 130, 160, 154, 138, 106, 81, 52, 34, 18, 10, 4, 2;
		

Links

• Alois P. Heinz, Rows n = 0..65, flattened
• M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Crossrefs

Cf. A004148, A000045, A001629.

Programs

Maple

g := 1/(1-z-z^2-t*z^3*A[1]): for j to 15 do A[j] := 1/(1-t^j*z-t^j*z^2-t^(2*j+1)*z^3*A[j+1]) end do: gser := simplify(series(g, z = 0, 20)): for n from 0 to 17 do P[n] := sort(coeff(gser, z, n)) end do: for n from 0 to 17 do seq(coeff(P[n], t, j), j = 0 .. floor((1/8)*n^2)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n, 0, `if`(n=0, 1,
      expand(b(n-1, y)*x^y +`if`(n>1, b(n-2, y)*x^y+b(n-2, y+1)*
      x^(y+1/2), 0) +b(n-1, y-1)*x^(y-1/2))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Aug 20 2014

Mathematica

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

Formula

The trivariate g.f. G=G(t,s,z), where t marks area, s marks length (=number of steps), and z marks weight, satisfies G = 1+szG+sz^2G+ts^2z^3G(t,ts,z)G. This follows at once from the fact that every nonempty path is of the form hC or HC or UCDC, where h denotes a (1,0)-step of weight 1, H denotes a (1,0)-step of weight 2, U denotes a (1,1)-step, D denotes a (1,-1)-step, and the C's denote paths, not necessarily the same. From the equation one can find G(t,s,z) as a continued fraction (the Maple program makes use of this).