OFFSET
0,5
COMMENTS
T(n,k) is the number of Łukasiewicz paths of length n having k peaks. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1). Example: T(3,1)=3 because we have HUD, UDH and U(2)DD, where H=(1,0), U(1,1), U(2)=(1,2) and D=(1,-1). (see R. P. Stanley reference). - Emeric Deutsch, Jan 06 2005
REFERENCES
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps. - Emeric Deutsch, Jan 06 2005
LINKS
Alois P. Heinz, Rows n = 0..200, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. - From N. J. A. Sloane, May 05 2012
FORMULA
G.f.: (1 + z^2 - t*z^2 - (-4*z + (-1 - z^2 + t*z^2)^2)^(1/2))/(2*z) = Sum_{n>=0, 0<=k<=n/2} T(n, k)z^n*t^k and it satisfies G = 1 + G^2*z + G*(-z^2 + t*z^2).
T(n,k) = Sum_{j=0..floor(n/2)-k} (-1)^j * binomial(n-(j+k), j+k) * binomial(2n-3(j+k), n-(j+k)-1) * binomial(j+k, k)/(n-(j+k)). - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006
EXAMPLE
Table begins
\ k 0, 1, 2, ...
n
0 | 1;
1 | 1;
2 | 1, 1;
3 | 2, 3;
4 | 5, 8, 1;
5 | 13, 23, 6;
6 | 35, 69, 27, 1;
7 | 97, 212, 110, 10;
8 |275, 662, 426, 66, 1;
T(3,1) = 3 because each of UUUDDD, UDUUDD, UUDDUD has one UUDD.
MAPLE
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 3, 2][t])
+b(x-1, y-1, [1, 1, 4, 1][t])*`if`(t=4, z, 1))))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15); # Alois P. Heinz, Jun 10 2014
MATHEMATICA
T[n_, k_] := Binomial[n-k, k] Binomial[2n-3k, n-k-1] HypergeometricPFQ[{k -n/2-1/2, k-n/2, k-n/2, k-n/2+1/2}, {k-2n/3, k-2n/3+1/3, k-2n/3+2/3}, 16/27]/(n-k); T[0, 0] = 1; Flatten[Table[T[n, k], {n, 0, 15}, {k, 0, n/2}]] (* Jean-François Alcover, Dec 21 2016, after 2nd formula *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
David Callan, Oct 24 2004
STATUS
approved