login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A098978 Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2. 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 (list; graph; refs; listen; history; text; internal format)
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 A096320

Adjacent sequences:  A098975 A098976 A098977 * A098979 A098980 A098981

KEYWORD

nonn,tabf

AUTHOR

David Callan, Oct 24 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 06:55 EDT 2021. Contains 345358 sequences. (Running on oeis4.)