A303287 -id:A303287 - 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

A177042 Eulerian version of the Catalan numbers, a(n) = A008292(2*n+1,n+1)/(n+1).

Original entry on oeis.org

1, 2, 22, 604, 31238, 2620708, 325024572, 55942352184, 12765597850950, 3730771315561300, 1359124435588313876, 603916464771468176392, 321511316149669476991132, 202039976682357297272094824, 147980747895225006590333244088, 124963193751534047864734415925360

Offset: 0

Roger L. Bagula, May 01 2010

nonn

According to the Bidkhori and Sullivant reference's abstract, authors show "that the Eulerian-Catalan numbers enumerate Dyck permutations, [providing] two proofs for this fact, the first using the geometry of alcoved polytopes and the second a direct combinatorial proof via an Eulerian-Catalan analog of the Chung-Feller theorem." - Jonathan Vos Post, Jan 07 2011

Twice the number of permutations of {1,2,...,2n} with n ascents. - Peter Luschny, Jan 11 2011

Alois P. Heinz, Table of n, a(n) for n = 0..220
F. Ardila, The Catalan matroid, J. Combin. Theory Ser. A 104 (2003) 49-62.
Hoda Bidkhori and Seth Sullivant, Eulerian-Catalan Numbers, arXiv:1101.1108 [math.CO], 2011.
Digital Library of Mathematical Functions, Table 26.14.1

Cf. A000108, A008518, A025585, A180056.
Bisection (odd part) of A303287.
Row sums of A316728.

A177042:=func< n | n eq 0 select 1 else 2*(&+[(-1)^k*Binomial(2*n+1,k)*(n-k+1)^(2*n): k in [0..n]]) >;
[A177042(n): n in [0..40]]; // G. C. Greubel, Jun 18 2024

A177042 := proc(n) A008292(2*n+1,n+1)/(n+1) ; end proc:
seq(A177042(n),n=0..10) ; # R. J. Mathar, Jan 08 2011
A177042 := n -> A025585(n+1)/(n+1):
A177042 := n -> `if`(n=0,1,2*A180056(n)):
# The A173018-based recursion below needs no division!
A := proc(n, k) option remember;
       if n = 0 and k = 0 then 1
     elif k > n  or k < 0 then 0
     else (n-k) *A(n-1, k-1) +(k+1) *A(n-1, k)
       fi
     end:
A177042 := n-> `if`(n=0, 1, 2*A(2*n, n)):
seq(A177042(n), n=0..30);
# Peter Luschny, Jan 11 2011

<< DiscreteMath`Combinatorica`
Table[(Eulerian[2*n + 1, n])/(n + 1), {n, 0, 20}]
(* Second program: *)
A[n_, k_] := A[n, k] = Which[n == 0 && k == 0, 1, k > n || k < 0, 0, True, (n - k)*A[n - 1, k - 1] + (k + 1)*A[n - 1, k]]; A177042[n_] := If[n == 0, 1, 2*A[2*n, n]]; Table[A177042[n], {n, 0, 30}] (* Jean-François Alcover, Jul 13 2017, after Peter Luschny *)

def A177042(n): return 2*sum((-1)^k*binomial(2*n+1,k)*(n-k+1)^(2*n) for k in range(n+1)) - int(n==0)
[A177042(n) for n in range(41)] # G. C. Greubel, Jun 18 2024

a(n) = 2*A180056(n) for n > 0, A180056 the central Eulerian numbers in the sense of A173018.
a(n) = A025585(n+1)/(n+1), A025585 the central Eulerian numbers in the sense of A008292.
a(n) = 2 Sum_{k=0..n} (-1)^k binomial(2n+1,k) (n-k+1)^(2n).
a(n) = (n+1)^(-1) Sum_{k=0..n} (-1)^k binomial(2n+2,k)(n+1-k)^(2n+1). - Peter Luschny, Jan 11 2011
a(n) = A008518(2n,n). - Alois P. Heinz, Jun 12 2017
From Alois P. Heinz, Jul 21 2018: (Start)
a(n) = (2n)! * [x^(2n) y^n] (exp(x)-y*exp(y*x))/(exp(y*x)-y*exp(x)).
a(n) = (2n+1)!/(n+1) * [x^(2n+1) y^(n+1)] (1-y)/(1-y*exp((1-y)*x)). (End)

Edited by Alois P. Heinz, Jan 14 2011

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

Original entry on oeis.org

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

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

A304777 Number of partitions p of n such that the sequence of level steps (when interpreted as ascents) and descents of p forms a Dyck path.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 3, 4, 3, 6, 5, 7, 5, 9, 10, 12, 10, 15, 13, 18, 19, 27, 20, 30, 30, 40, 40, 52, 48, 61, 61, 77, 79, 100, 99, 124, 129, 150, 150, 200, 199, 240, 249, 294, 303, 363, 369, 441, 484, 550, 569, 686, 716, 817, 885, 1003, 1065

Offset: 0

Alois P. Heinz, May 18 2018

nonn

			a(5) = 2: 221, 5.
a(11) = 4: 33221, 443, 551, (11).
a(12) = 3: 33321, 552, (12).
a(15) = 6: 44331, 44421, 55221, 663, 771, (15).

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

Cf. A303287, A304778.

b:= proc(n, i, c) option remember; `if`(n=0, `if`(c=0, 1, 0),
     `if`(min(i, c)<1, 0, add(b(n-i*j, i-1,
     `if`(j=0, c, c+j-2)), j=0..n/i)))
    end:
a:= n-> `if`(n=0, 1, b(n$2, 1)):
seq(a(n), n=0..100);

b[n_, i_, c_] := b[n, i, c] = If[n == 0, If[c == 0, 1, 0], If[Min[i, c] < 1, 0, Sum[b[n - i*j, i - 1, If[j == 0, c, c + j - 2]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 1, b[n, n, 1]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 28 2018, from Maple *)

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 9, 15, 23, 38, 62, 100, 163, 267, 441, 725, 1198, 1986, 3291, 5472, 9116, 15204, 25399, 42494, 71183, 119396, 200507, 337090, 567318, 955749, 1611672, 2720212, 4595198, 7768975, 13145109, 22258264, 37716358, 63953853, 108515011

Offset: 0

Alois P. Heinz, May 18 2018

nonn

			a(6) = 4: 132, 141, 231, 6.
a(7) = 6: 12121, 142, 151, 232, 241, 7.
a(8) = 9: 12131, 13121, 143, 152, 161, 242, 251, 341, 8.
a(9) = 15: 12132, 12141, 12321, 13131, 14121, 153, 162, 171, 23121, 243, 252, 261, 342, 351, 9.

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

Cf. A003242, A303287, A304777.

b:= proc(n, l, c) option remember; `if`(c<0 and l>0, 0,
      `if`(n=0, `if`(l<0 or c=0, 1, 0), add(`if`(i=l, 0,
       b(n-i, i, c+`if`(i>l, 1, -1))), i=1..n)))
    end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..50);

b[n_, l_, c_] := b[n, l, c] = If[c<0 && l>0, 0, If[n==0, If[l<0 || c==0, 1, 0], Sum[If[i==l, 0, b[n-i, i, c + If[i>l, 1, -1]]], {i, 1, n}]]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 31 2018, from Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A241902 = 1.7502412917183090312497386246... and c = 7.0142545527132612683043468956... - Vaclav Kotesovec, May 22 2018

A304001 Number of permutations of [n] whose up-down signature has a nonnegative total sum.

Original entry on oeis.org

1, 1, 1, 5, 12, 93, 360, 3728, 20160, 259535, 1814400, 27820524, 239500800, 4251096402, 43589145600, 877606592736, 10461394944000, 235288904377275, 3201186852864000, 79476406782222500, 1216451004088320000, 33020655481590446318, 562000363888803840000

Offset: 0

Alois P. Heinz, May 04 2018

nonn

The up-down signature has (+1) for each ascent and (-1) for each descent.

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

Bisections give: A002674 (even part), A179457(2n+1,n+1) (odd part).

Cf. A000246 (for nonnegative partial sums), A006551 (total sums are 0 or 1), A008292, A303287.

b:= proc(u, o, t) option remember; (n->
     `if`(t>=n, n!, `if`(t<-n, 0,
      add(b(u-j, o+j-1, t-1), j=1..u)+
      add(b(u+j-1, o-j, t+1), j=1..o))))(u+o)
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, 0), j=1..n)):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(irem(n, 2, 'r')=0, ceil(n!/2),
         add(combinat[eulerian1](n, j), j=0..r)):
seq(a(n), n=0..25);

Eulerian1[n_, k_] := If[k == 0, 1, If[n == 0, 0, Sum[(-1)^j (k - j + 1)^n Binomial[n + 1, j], {j, 0, k + 1}]]];
a[n_] := Module[{r, m}, {r, m} = QuotientRemainder[n, 2]; If[m == 0, Ceiling[n!/2], Sum[Eulerian1[n, j], {j, 0, r}]]];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 26 2021, after 2nd Maple program *)

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

A177042 Eulerian version of the Catalan numbers, a(n) = A008292(2*n+1,n+1)/(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

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

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

A304777 Number of partitions p of n such that the sequence of level steps (when interpreted as ascents) and descents of p forms a Dyck path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A304001 Number of permutations of [n] whose up-down signature has a nonnegative total sum.

Views

Author

Keywords

Comments

Links