login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A303287 Number of permutations p of [n] such that the sequence of ascents and descents of p or of p0 (if n is even) forms a Dyck path. 8
1, 1, 1, 2, 8, 22, 172, 604, 7296, 31238, 518324, 2620708, 55717312, 325024572, 8460090160, 55942352184, 1726791794432, 12765597850950, 456440969661508, 3730771315561300, 151770739970889792, 1359124435588313876, 62022635037246022000, 603916464771468176392 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

LINKS

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

Wikipedia, Counting lattice paths

FORMULA

a(2n) = A303284(2n).

EXAMPLE

a(0) = 1: the empty permutation.

a(1) = 1: 1.

a(2) = 1: 12.

a(3) = 2: 132, 231.

a(4) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.

a(5) = 22: 12543, 13254, 13542, 14253, 14352, 14532, 15243, 15342, 23154, 23541, 24153, 24351, 24531, 25143, 25341, 34152, 34251, 34521, 35142, 35241, 45132, 45231.

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, 0, 1):

seq(a(n), n=0..25);

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, 0, 1];

Table[a[n], {n, 0, 25}] (* Jean-Fran├žois Alcover, May 25 2018, translated from Maple *)

CROSSREFS

Bisections give: A303285 (even part), A177042 (odd part).

Cf. A180056, A304001, A303284, A304777, A304778.

Sequence in context: A191643 A151356 A238530 * A321068 A158466 A065694

Adjacent sequences:  A303284 A303285 A303286 * A303288 A303289 A303290

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Apr 20 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 20 09:27 EDT 2022. Contains 353871 sequences. (Running on oeis4.)