A316727 -id:A316727 - cp's OEIS frontend

A303285 Number of permutations p of [2n] such that the sequence of ascents and descents of p0 forms a Dyck path.

1, 1, 8, 172, 7296, 518324, 55717312, 8460090160, 1726791794432, 456440969661508, 151770739970889792, 62022635037246022000, 30564038464166725328768, 17876875858414492985045712, 12245573879235563308351042496, 9711714975145772145881269175104

Offset: 0

Alois P. Heinz, Apr 20 2018

nonn

Here p is a permutation of 1,2,3,...,2n, and p0 refers to the string p followed by 0.
Also the number of permutations p of [2n] such that the sequence of ascents and descents of 0p forms a Dyck path. a(2) = 8: 1432, 2143, 2431, 3142, 3241, 3421, 4132, 4231.
Also the number of permutations p of [2n] that are of odd order and whose M statistic (as defined in the Spiro paper) is equal to n-1. - Sam Spiro, Nov 01 2018

			a(0) = 1: the empty permutation.
a(1) = 1: 12.
a(2) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv:1810.00993 [math.CO], 2018.
Wikipedia, Counting lattice paths

Bisection (even part) of A303284.
Bisection (even part) of A303287.
Column k=0 of A316728.
Cf. A177042, A180056, A316727, A321280.

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

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[0, 2n, 0];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 29 2018, from Maple *)

\\ here b(n) is A177042
b(n)={if(n==0, 1, 2*sum(k=0, n, (-1)^k*binomial(2*n+1,k)*(n-k+1)^(2*n)));}
a(n)={if(n==0, 1, sum(k=1, n, binomial(2*n, 2*k-1)*b(k-1)*b(n-k))/2);} \\ Andrew Howroyd, Nov 01 2018

a(n) ~ c * 2^(2*n) * n^(2*n - 1) / exp(2*n), where c = 8.838022110416151362523442920999767406145711133564692... - Vaclav Kotesovec, May 22 2018
a(n) = (1/2)*Sum_{k odd} binomial(2*n,k)*A177042((k-1)/2)*A177042((2n-k-1)/2) for n>0. - Sam Spiro, Nov 01 2018
a(n) = A321280(2n,n-1) for n >= 1. - Alois P. Heinz, Nov 02 2018

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.

Original entry on oeis.org

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

Alois P. Heinz, Jul 11 2018

			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;

Alois P. Heinz, Rows n = 0..100, flattened
Wikipedia, Counting lattice paths

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.

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);

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 *)

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).

cp's OEIS Frontend

A303285 Number of permutations p of [2n] such that the sequence of ascents and descents of p0 forms a Dyck path.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula