A303285 -id:A303285 - cp's OEIS frontend

A180056 The number of permutations of {1,2,...,2n} with n ascents.

1, 1, 11, 302, 15619, 1310354, 162512286, 27971176092, 6382798925475, 1865385657780650, 679562217794156938, 301958232385734088196, 160755658074834738495566, 101019988341178648636047412, 73990373947612503295166622044, 62481596875767023932367207962680

Offset: 0

Peter Luschny, Aug 08 2010

nonn

Define the Eulerian numbers A(n,k) (see A008292) to be the number of permutations of {1,2,..,n} with k ascents: A(n,k) = Sum_{j=0..k} (-1)^j binomial(n+1,j)*(k-j+1)^n.

Then a(n) = A(2*n,n) are the central Eulerian numbers. (Analogous to what are called the central binomial coefficients).

Alois P. Heinz, Table of n, a(n) for n = 0..200
Digital Library of Mathematical Functions, Table 26.14.1

A bisection of A006551.
Cf. A008292, A025585, A123125, A303284, A303285, A303286, A303287.
A diagonal of A321967.

A180056 :=
proc(n) local j;
  add((-1)^j*binomial(2*n+1,j)*(n-j+1)^(2*n),j=0..n)
end:
# A180056_list(m) returns [a_0,a_1,..,a_m]
A180056_list :=
  proc(m) local A, R, M, n, k;
    R := 1; M := m + 1;
    A := array([seq(1, n = 1..M)]);
    for n from 2 to M do
      for k from 2 to M do
        if n = k then R := R, A[k] fi;
        A[k] := n*A[k-1] + k*A[k]
      od
    od;
  R
end:

A025585[n_] := Sum[(-1)^j*(n-j)^(2*n-1)*Binomial[2*n, j], {j, 0, n}]; a[0] = 1; a[n_] := A025585[n+1]/(2*n+2); Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Jun 28 2013, after Gary Detlefs *)
<< Combinatorica`; Table[Combinatorica`Eulerian[2 n, n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 15 2016 *)

def A180056_list(m):
    ret = [1]
    M = m + 1
    A = [1 for i in range(0, M)]
    for n in range(2, M):
        for k in range(2, M):
            if n == k:
                ret.append(A[k])
            A[k] = n*A[k-1] + k*A[k]
    return ret

a(n-1) = A025585(n)/(2*n). - Gary Detlefs, Nov 11 2011
a(n+1)/a(n) ~ 4*n^2. - Ran Pan, Oct 26 2015
a(n) ~ sqrt(3) * 2^(2*n+1) * n^(2*n) / exp(2*n). - Vaclav Kotesovec, Oct 16 2016
From Alois P. Heinz, Jul 21 2018: (Start)
a(n) = ceiling(1/2 * (2n)! * [x^(2n) y^n] (exp(x)-y*exp(y*x))/(exp(y*x)-y*exp(x))).
a(n) = (2n)! * [x^(2n) y^n] (1-y)/(1-y*exp((1-y)*x)). (End)
a(n) = A123125(2n,n). - Alois P. Heinz, Nov 13 2024

Partially edited by N. J. A. Sloane, Aug 08 2010

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.

Original entry on oeis.org

1, 1, 1, 2, 8, 22, 172, 604, 7296, 31238, 518324, 2620708, 55717312, 325024572, 8460090160, 55942352184, 1726791794432, 12765597850950, 456440969661508, 3730771315561300, 151770739970889792, 1359124435588313876, 62022635037246022000, 603916464771468176392

Offset: 0

Alois P. Heinz, Apr 20 2018

nonn

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Wikipedia, Counting lattice paths

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

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

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

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

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

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

A303284 Number of permutations p of [n] such that the sequence of ascents and descents of 0p or of 0p0 (if n is odd) forms a Dyck path.

Original entry on oeis.org

1, 1, 1, 4, 8, 60, 172, 1974, 7296, 114972, 518324, 10490392, 55717312, 1384890104, 8460090160, 250150900354, 1726791794432, 59317740001132, 456440969661508, 17886770092245360, 151770739970889792, 6687689652133397064, 62022635037246022000, 3037468107154650475868

Offset: 0

Alois P. Heinz, Apr 20 2018

nonn

			a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 1: 21.
a(3) = 4: 132, 213, 231, 312.
a(4) = 8: 1432, 2143, 2431, 3142, 3241, 3421, 4132, 4231.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Wikipedia, Counting lattice paths

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

Cf. A180056, A303287.

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

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

b(u, o, t) = if(u+o==0, 1, if(t > 0, sum(j=1, u, b(u-j, o+j-1, t-1)), 0) + if(o+u > t, sum(j=1, o, b(u+j-1, o-j, t+1)), 0))
a(n) = b(0, n, 0) \\ Felix Fröhlich, May 25 2018, adapted from Mathematica

a(2n) = A303287(2n).

A321280 Number T(n,k) of permutations p of [n] with exactly k descents such that the up-down signature of p has nonnegative partial sums; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 8, 1, 22, 22, 1, 52, 172, 1, 114, 856, 604, 1, 240, 3488, 7296, 1, 494, 12746, 54746, 31238, 1, 1004, 43628, 330068, 518324, 1, 2026, 143244, 1756878, 5300418, 2620708, 1, 4072, 457536, 8641800, 43235304, 55717312, 1, 8166, 1434318, 40298572, 309074508, 728888188, 325024572

Offset: 0

Alois P. Heinz, Nov 01 2018

			Triangle T(n,k) begins:
  1;
  1;
  1;
  1,     2;
  1,     8;
  1,    22,      22;
  1,    52,     172;
  1,   114,     856,       604;
  1,   240,    3488,      7296;
  1,   494,   12746,     54746,      31238;
  1,  1004,   43628,    330068,     518324;
  1,  2026,  143244,   1756878,    5300418,    2620708;
  1,  4072,  457536,   8641800,   43235304,   55717312;
  1,  8166, 1434318,  40298572,  309074508,  728888188,  325024572;
  1, 16356, 4438540, 180969752, 2026885824, 7589067592, 8460090160;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv preprint arXiv:1810.00993 [math.CO], 2018.
David G. L. Wang, T. Zhao, The peak and descent statistics over ballot permutations, arXiv:2009.05973 [math.CO], 2020.

Columns k=0-3 give: A000012, A005803 (for n>0), A321268, A321269.
Row sums give A000246.
T(2n+1,n) gives A177042.
T(2n+2,n) gives A303285(n+1).
Cf. A262124, A262125.

b:= proc(u, o, c) option remember; `if`(c<0, 0, `if`(u+o=0, 1/x,
       add(expand(x*b(u-j, o-1+j, c-1)), j=1..u)+
       add(b(u+j-1, o-j, c+1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(`if`(n=0, 1, b(n, 0, 1))):
seq(T(n), n=0..14);

b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o == 0, 1/x, Sum[Expand[ x*b[u - j, o - 1 + j, c - 1]], {j, 1, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ If[n == 0, 1, b[n, 0, 1]]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 08 2018, after Alois P. Heinz *)

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

Original entry on oeis.org

1, 1, 5, 87, 3337, 223333, 23068057, 3403720071, 679894572497, 176710079709345, 57967294285022281, 23427042148948682599, 11437832700333350250001, 6637473822604173137681381, 4515971399162518697397538173, 3560540787622773257563653593551

Offset: 0

Alois P. Heinz, Jul 11 2018

nonn

All terms are odd.

			a(0) = 1: 0.
a(1) = 1: 120.
a(2) = 5: 23041, 23140, 23410, 24031, 24130.
a(3) = 87: 3401652, 3402165, 3402651, 3405162, ..., 3625041, 3625140, 3645021, 3645120.

Alois P. Heinz, Table of n, a(n) for n = 0..225
Wikipedia, Counting lattice paths

Cf. A303285, A316728.

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$2, 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[n, n, 0];
a /@ Range[0, 20] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

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

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

A321268 Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly two descents.

Original entry on oeis.org

0, 0, 0, 0, 22, 172, 856, 3488, 12746, 43628, 143244, 457536, 1434318, 4438540, 13611136, 41473216, 125797010, 380341580, 1147318004, 3455325600, 10394291094, 31242645420, 93853769320, 281825553760, 846030314842, 2539248578732, 7620161662556, 22865518160768

Offset: 1

Sam Spiro, Nov 01 2018

Also the number of permutations of [n] of odd order whose M statistic (as defined in the Spiro paper) is equal to two.

			Some permutations counted by a(5) include 14253 and 34521.

Sam Spiro, Table of n, a(n) for n = 1..100
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv:1810.00993 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (11,-50,122,-173,143,-64,12).

Cf. A000246, A005803, A321269, A303285, A177042.

Column k=2 of A321280.

a[1] = 0; a[n_] := 2n^2 - 2n - 1 - n 2^(n-1) - 2 Binomial[n, 3] + Sum[ Binomial[n, k] (2^k - 2k), {k, 0, n}];
Table[a[n], {n, 1, 28}] (* Jean-François Alcover, Nov 11 2018 *)

a(n)={if(n<2, 0, 2*n^2 - 2*n - 1 - n*2^(n-1) - 2*binomial(n,3) + sum(k=0, n, binomial(n, k)*(2^k - 2*k)))} \\ Andrew Howroyd, Nov 01 2018

concat([0,0,0,0], Vec(2*x^5*(11 - 35*x + 32*x^2 - 6*x^3) / ((1 - x)^4*(1 - 2*x)^2*(1 - 3*x)) + O(x^40))) \\ Colin Barker, Mar 07 2019

a(n) = 3*A008292(n-1,3)- 2*binomial(n,3)+binomial(n,2)-1 for n > 1.
a(n) =   A065826(n-1,3)- 2*binomial(n,3)+binomial(n,2)-1 for n > 1.
a(n) = 3^n-3*n*2^(n-1)-2*binomial(n,3)+4*binomial(n,2)-1 for n > 1.
From Colin Barker, Mar 07 2019: (Start)
G.f.: 2*x^5*(11 - 35*x + 32*x^2 - 6*x^3) / ((1 - x)^4*(1 - 2*x)^2*(1 - 3*x)).
a(n) = 11*a(n-1) - 50*a(n-2) + 122*a(n-3) - 173*a(n-4) + 143*a(n-5) - 64*a(n-6) + 12*a(n-7) for n>8.
a(n) = -1 + 3^n - (16+9*2^n)*n/6 + 3*n^2 - n^3/3 for n>1.
(End)

A321269 Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly three descents.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 604, 7296, 54746, 330068, 1756878, 8641800, 40298572, 180969752, 790697160, 3385019968, 14270283414, 59457742524, 245507935018, 1006678811272, 4105447763032, 16672235476128, 67482738851220, 272439143364672, 1097660274098482, 4415486996246052

Offset: 1

Sam Spiro, Nov 01 2018

Also the number of permutations of [n] of odd order whose M statistic (as defined in the Spiro paper) is equal to three.

			The permutations counted by a(7) include 1237654 and 17265243.

Alois P. Heinz, Table of n, a(n) for n = 1..1660
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv preprint arXiv:1810.00993 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (24,-260,1684,-7278,22172,-49004,79596,-95065,82508,-50616,20800,-5136,576).

Cf. A000246, A005803, A321268, A303285, A177042.

Column k=3 of A321280.

t[n_, k_] := Sum[(-1)^j (k - j)^n Binomial[n + 1, j], {j, 0, k}];
a[n_] := If[n<7, 0, 4 t[n-1, 4] - (Binomial[n, 3] - Binomial[n, 2] + 4) * 2^(n-2) - 22 Binomial[n, 5] + 16 Binomial[n, 4] - 4 Binomial[n, 3] + 2n];
Array[a, 30] (* Jean-François Alcover, Feb 29 2020, from Sam Spiro's 1st formula *)

concat([0,0,0,0,0,0], Vec(2*x^7*(302 - 3600*x + 18341*x^2 - 52006*x^3 + 89327*x^4 - 94728*x^5 + 61016*x^6 - 23368*x^7 + 5424*x^8 - 576*x^9) / ((1 - x)^6*(1 - 2*x)^4*(1 - 3*x)^2*(1 - 4*x)) + O(x^30))) \\ Colin Barker, Mar 07 2019

From Sam Spiro, Mar 07 2019: (Start)
a(n) = 4*A008292(n-1,4)-(binomial(n,3)-binomial(n,2)+4)*2^(n-2)-22*binomial(n,5)+16*binomial(n,4)-4*binomial(n,3)+2n for n>3.
a(n) = A065826(n-1,4)-(binomial(n,3)-binomial(n,2)+4)*2^(n-2)-22*binomial(n,5)+16*binomial(n,4)-4*binomial(n,3)+2n for n>3.
a(n) = 4^n-4*n*3^(n-1)+9*binomial(n,2)*2^(n-2)-binomial(n,3)*2^(n-2)-2^n-8*binomial(n,3)-22*binomial(n,5)+16*binomial(n,4)+2*n for n>3.
(End)
From Colin Barker, Mar 07 2019: (Start)
G.f.: 2*x^7*(302 - 3600*x + 18341*x^2 - 52006*x^3 + 89327*x^4 - 94728*x^5 + 61016*x^6 - 23368*x^7 + 5424*x^8 - 576*x^9) / ((1 - x)^6*(1 - 2*x)^4*(1 - 3*x)^2*(1 - 4*x)).
a(n) = 24*a(n-1) - 260*a(n-2) + 1684*a(n-3) - 7278*a(n-4) + 22172*a(n-5) - 49004*a(n-6) + 79596*a(n-7) - 95065*a(n-8) + 82508*a(n-9) - 50616*a(n-10) + 20800*a(n-11) - 5136*a(n-12) + 576*a(n-13) for n>16.
(End)

More terms from Alois P. Heinz, Nov 01 2018

cp's OEIS Frontend

A180056 The number of permutations of {1,2,...,2n} with n ascents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303284 Number of permutations p of [n] such that the sequence of ascents and descents of 0p or of 0p0 (if n is odd) forms a Dyck path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A321280 Number T(n,k) of permutations p of [n] with exactly k descents such that the up-down signature of p has nonnegative partial sums; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A321268 Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly two descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica