A316730 Number of permutations of {0,1,...,2n+2} with first element n whose sequence of ascents and descents forms a Dyck path.

1, 7, 121, 4411, 283073, 28318137, 4076415425, 798519164779, 204292676593353, 66150225395814649, 26444888796754193841, 12792566645739144488693, 7364969554345555373419625, 4976538708651698959601499559, 3900052284443403730374391636689

Offset

0,2

Comments

All terms are odd.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..224

Wikipedia, Counting lattice paths

Formula

a(n) = A316728(n+1,n).

a(n) ~ c * 4^n * (n!)^2, where c = 1.897642067924382577976619913635026612792069869805703855808680498665... - Vaclav Kotesovec, Jul 15 2018

Example

a(0) = 1: 021.
a(1) = 7: 12043, 12430, 13042, 13240, 13420, 14032, 14230.
a(2) = 121: 2301654, 2304165, 2304651, 2305164, ..., 2635041, 2635140, 2645031, 2645130.

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:
a:= n-> b(n, n+2, 0):
seq(a(n), n=0..20);

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]];
a[n_] := b[n, n+2, 0];
a /@ Range[0, 20] (* Jean-François Alcover, Mar 27 2021, after Alois P. Heinz *)

Crossrefs

Cf. A316728.

Sequence in context: A279235 A094088 A012043 * A211103 A012103 A012086

Adjacent sequences: A316727 A316728 A316729 * A316731 A316732 A316733

Keyword

nonn

Author

Alois P. Heinz, Jul 11 2018

Status

approved