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.

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

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: A185346 A378096 A200017 * A231098 A072003 A160668

Adjacent sequences: A316725 A316726 A316727 * A316729 A316730 A316731

Keyword

nonn,tabf

Author

Alois P. Heinz, Jul 11 2018

Status

approved