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!)
A316728 Number T(n,k) of permutations of {0,1,...,2n} with first element k whose sequence of ascents and descents forms a Dyck path; triangle T(n,k), n>=0, 0<=k<=2n, read by rows. 6
1, 1, 1, 0, 8, 7, 5, 2, 0, 172, 150, 121, 87, 52, 22, 0, 7296, 6440, 5464, 4411, 3337, 2306, 1380, 604, 0, 518324, 463578, 405024, 344260, 283073, 223333, 166856, 115250, 69772, 31238, 0, 55717312, 50416894, 44928220, 39348036, 33777456, 28318137, 23068057, 18117190, 13543456, 9409366, 5759740, 2620708, 0 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

Alois P. Heinz, Rows n = 0..100, flattened

Wikipedia, Counting lattice paths

FORMULA

Sum_{k=0..2n} T(n,k) = T(n+1,2n+1) = A177042(n).

Sum_{k=0..2n} (k+1) * T(n,k) = A079484(n).

EXAMPLE

T(2,0) = 8: 01432, 02143, 02431, 03142, 03241, 03421, 04132, 04231.

T(2,1) = 7: 12043, 12430, 13042, 13240, 13420, 14032, 14230.

T(2,2) = 5: 23041, 23140, 23410, 24031, 24130.

T(2,3) = 2: 34021, 34120.

T(2,4) = 0.

Triangle T(n,k) begins:

       1;

       1,      1,      0;

       8,      7,      5,      2,      0;

     172,    150,    121,     87,     52,     22,      0;

    7296,   6440,   5464,   4411,   3337,   2306,   1380,    604,     0;

  518324, 463578, 405024, 344260, 283073, 223333, 166856, 115250, 69772, 31238, 0;

MAPLE

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

      `if`(t>0,   add(b(u-j, o+j-1, t-1), j=1..u), 0)+

      `if`(o+u>t, add(b(u+j-1, o-j, t+1), j=1..o), 0))

    end:

T:= (n, k)-> b(k, 2*n-k, 0):

seq(seq(T(n, k), k=0..2*n), n=0..8);

MATHEMATICA

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1,

     If[t > 0,     Sum[b[u - j, o + j - 1, t - 1], {j, 1, u}], 0] +

     If[o + u > t, Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}], 0]];

T[n_, k_] := b[k, 2n - k, 0];

Table[Table[T[n, k], {k, 0, 2n}], {n, 0, 8}] // Flatten (* Jean-Fran├žois Alcover, Mar 27 2021, after Alois P. Heinz *)

CROSSREFS

Column k=0 gives A303285.

Row sums and T(n+1,2n+1) give A177042.

T(n,n) gives A316727.

T(n+1,n) gives A316730.

T(n,2n) gives A000007.

Cf. A079484.

Sequence in context: A114137 A185346 A200017 * A231098 A072003 A160668

Adjacent sequences:  A316725 A316726 A316727 * A316729 A316730 A316731

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Jul 11 2018

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 20 04:43 EDT 2021. Contains 345157 sequences. (Running on oeis4.)