A098978 Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2.

1, 1, 1, 1, 2, 3, 5, 8, 1, 13, 23, 6, 35, 69, 27, 1, 97, 212, 110, 10, 275, 662, 426, 66, 1, 794, 2091, 1602, 360, 15, 2327, 6661, 5912, 1760, 135, 1, 6905, 21359, 21534, 8022, 945, 21, 20705, 68850, 77685, 34840, 5685, 246, 1, 62642, 222892, 278192, 146092

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

Index entries for sequences related to Łukasiewicz

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

Column k=0 is A025242 (apart from first term).

Cf. A243752.

Sequence in context: A093092 A031111 A089911 * A111301 A247193 A362358

Adjacent sequences: A098975 A098976 A098977 * A098979 A098980 A098981

Keyword

nonn,tabf

Author

David Callan, Oct 24 2004

Status

approved