A102693 -id:A102693 - cp's OEIS frontend

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184

Offset: 0

N. J. A. Sloane

Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen, Sep 03 2000
Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - Andrew Howroyd, May 04 2018
a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets, Oct 19 2005
Labeled plane trees are counted by A006963. - David Callan, Aug 19 2014
This sequence is similar to A000055 but those trees are not embedded in a plane. - Michael Somos, Aug 19 2014

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..200
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
CombOS - Combinatorial Object Server, Generate free plane trees
R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]
D. Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Bernold Fiedler, Scalar polynomial vector fields in real and complex time, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 23.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
G. Labelle, Sur la symétrie et l'asymétrie des structures combinatoires, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
Torsten Mütze, A book proof of the middle levels theorem, arXiv:2306.13019 [math.CO], 2023.
Torsten Mütze and Franziska Weber, Construction of 2-factors in the middle layer of the discrete cube, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
Torsten Mütze and F. Weber, Construction of 2-factors in the middle layer of the discrete cube, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
J. Sawada, Generating rooted and free plane trees, ACM Transactions on Algorithms, Vol. 2 No. 1 (2006), 1-13.
Seunghyun Seo and Heesung Shin, Two involutions on vertices of ordered trees, FPSAC'02 (2002). (see p_n).
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See Table 1.
D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 (1972), 200-204.
Index entries for sequences related to trees

Column k=2 of A303694 and A303864.

Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.

with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # Zerinvary Lajos, Dec 01 2006

a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 07 2012, from formula *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ Michel Marcus, Jan 23 2016

G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).

a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.

More terms, formula from Christian G. Bower, Dec 15 1999

Name corrected ("labeled" --> "unlabeled") by David Callan, Aug 19 2014

A065866 a(n) = n! * Catalan(n+1).

Original entry on oeis.org

1, 2, 10, 84, 1008, 15840, 308880, 7207200, 196035840, 6094932480, 213322636800, 8303173401600, 355850288640000, 16653793508352000, 845180020548864000, 46236318771202560000, 2712530701243883520000, 169890080762116915200000, 11314679378756986552320000

Offset: 0

Len Smiley, Dec 06 2001

nonn

From Noam Zeilberger, Mar 19 2019: (Start)
a(n) is the number of flags in the associahedron of dimension n. For example, there are a(2) = 10 flags in the associahedron of dimension 2, a pentagon. (In this case a flag corresponds to a triple v:e:f of a mutually incident vertex v, edge e, and face f, with f necessarily the unique face of the pentagon.)
Equivalently, a(n) is the number of maximal sequences of consistent parenthesizations of a string of n + 2 letters, starting with n + 1 pairs of parentheses, then removing one pair, and so on, ending with the trivial (outermost) parenthesization. For example, (a(b(cd))):(ab(cd)):(abcd) and (a(b(cd))):(a(bcd)):(abcd) are two of the a(2) = 10 maximal sequences of consistent parenthesizations of the letters abcd. (End)

			G.f. = 1 + 2*x + 10*x^2 + 84*x^3 + 1008*x^4 + 15840*x^5 + 308880*x^6 + ...

R. L. Graham, D. E. Knuth, and O. Patashnik, "Concrete Mathematics", Addison-Wesley, 1994, pp. 200-204.

Harry J. Smith, Table of n, a(n) for n = 0..100

Cf. A000108, A001761.
Cf. A370055, A370058.
Equals 2 * A102693(n+1), n > 0.
Main diagonal of A256116.

List([0..20], n-> 2*Factorial(2*n+1)/Factorial(n+2)); # G. C. Greubel, Mar 19 2019

[Factorial(n)*Catalan(n+1): n in [0..20]]; // G. C. Greubel, Mar 19 2019

with(combstruct): ZL:=[T, {T=Union(Z, Prod(Epsilon, Z, T), Prod(T, Z, Epsilon), Prod(T, T, Z))}, labeled]: seq(count(ZL, size=i+1)/(i+1), i=0..18); # Zerinvary Lajos, Dec 16 2007
a := n -> (2^(2*n+2)*GAMMA(n+3/2))/(sqrt(Pi)*(n+1)*(n+2)):
seq(simplify(a(n)), n=0..17); # Peter Luschny, Mar 20 2019

Table[2*(2n+1)!/(n+2)!, {n,0,20}] (* G. C. Greubel, Mar 19 2019 *)
Table[n! CatalanNumber[n+1],{n,0,20}] (* Harvey P. Dale, Feb 02 2023 *)

{ for (n = 0, 100, a = 2 * (2*n + 1)!/(n + 2)!; write("b065866.txt", n, " ", a) ) } \\ Harry J. Smith, Nov 02 2009

[factorial(n)*catalan_number(n+1) for n in (0..20)] # G. C. Greubel, Mar 19 2019

a(n) = 2 * (2n+1)!/(n+2)!.
E.g.f.: (1-2*x-sqrt(1-4*x))/(2*x^2) = (O.g.f. for A000108)^2 = B_2(x)^2 (cf. GKP reference).
0 = a(n)*(-7200*a(n+2) + 2700*a(n+3) + 246*a(n+4) - 33*a(n+5)) + a(n+1)*(+36*a(n+2) + 372*a(n+3) + 36*a(n+4) - a(n+5)) + a(n+2)*(-18*a(n+2) + 9*a(n+3) + a(n+4)) for n >= 0. - Michael Somos, Apr 14 2015
The e.g.f. A(x) satisfies 0 = -2 + A(x) * (6*x - 2) + A'(x) * (4*x^2 - x). - Michael Somos, Apr 14 2015
(n+2)*a(n) - 2*n*(2*n+1)*a(n-1) = 0. - R. J. Mathar, Oct 31 2015
a(n) ~ 4^n*exp(-n)*n^(n - 2)*sqrt(2)*(24*n - 61)/6. - Peter Luschny, Mar 20 2019
Sum_{n>=0} 1/a(n) = (25*exp(1/4)*sqrt(Pi)*erf(1/2) + 22)/32, where erf is the error function. - Amiram Eldar, Dec 04 2022
a(n) = 2 * Sum_{k=0..n} (n+2)^(k-1) * |Stirling1(n,k)|. - Seiichi Manyama, Aug 31 2024
E.g.f.: (1/x) * Series_Reversion( x/(1 + x)^2 ). - Seiichi Manyama, Feb 06 2025

A124320 Triangle read by rows: T(n,k) = k!*binomial(n+k-1,k) (n >= 0, 0 <= k <= n), rising factorial power, Pochhammer symbol.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 1, 3, 12, 60, 1, 4, 20, 120, 840, 1, 5, 30, 210, 1680, 15120, 1, 6, 42, 336, 3024, 30240, 332640, 1, 7, 56, 504, 5040, 55440, 665280, 8648640, 1, 8, 72, 720, 7920, 95040, 1235520, 17297280, 259459200, 1, 9, 90, 990, 11880, 154440, 2162160, 32432400, 518918400, 8821612800

Offset: 0

Emeric Deutsch, Oct 26 2006

This is the Pochhammer function which is defined P(x,n) = x*(x+1)*...*(x+n-1). By convention P(0,0) = 1. Also known as the rising factorial power. - Peter Luschny, Jan 09 2011

			Triangle starts:
[0]  1;
[1]  1, 1;
[2]  1, 2,   6;
[3]  1, 3,  12,  60;
[4]  1, 4,  20, 120,  840;
[5]  1, 5,  30, 210, 1680, 15120;
[6]  1, 6,  42, 336, 3024, 30240, 332640;
[7]  1, 7,  56, 504, 5040, 55440, 665280, 8648640;
Array starts:
[0] 1,  1,   6,   60,   840,   15120,   332640,   8648640, ... A000407
[1] 1,  2,  12,  120,  1680,   30240,   665280,  17297280, ... A001813
[2] 1,  3,  20,  210,  3024,   55440,  1235520,  32432400, ... A006963
[3] 1,  4,  30,  336,  5040,   95040,  2162160,  57657600, ... A001761
[4] 1,  5,  42,  504,  7920,  154440,  3603600,  98017920, ... A102693
[5] 1,  6,  56,  720, 11880,  240240,  5765760, 160392960, ... A093197
[6] 1,  7,  72,  990, 17160,  360360,  8910720, 253955520, ... A203473
[7] 1,  8,  90, 1320, 24024,  524160, 13366080, 390700800, ...
[8] 1,  9, 110, 1716, 32760,  742560, 19535040, 586051200, ...
[9] 1, 10, 132, 2184, 43680, 1028160, 27907200, 859541760, ...

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
NIST Digital Library of Mathematical Functions, Pochhammer's Symbol

Rows of array: A000407, A001813, A006963, A001761, A102693, A093197, A203473.

Cf. A123680 (row sums), A352601 (array main diagonal), A123680, A068424 (falling factorial power).

T:=proc(n,k) if k<=n then binomial(n+k-1,k)*k! else 0 fi end: for n from 0 to 9 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form
A124320 := (n,k)-> `if`(n=0 and k=0,1,pochhammer(n,k)); seq(print(seq(A124320(n,k),k=0..n)),n=0..5); # Peter Luschny, Jan 09 2011

Table[Pochhammer[n,k], {n,0,5},{k,0,n}]//Flatten (* Peter Luschny, Jan 09 2011 *)

for(n=0,10, for(k=0,n, print1(if(n==0 && k==0, 1, (n+k-1)!/(n-1)!), ", "))) \\ G. C. Greubel, Nov 19 2017

for n in (0..5) : [rising_factorial(n, k) for k in (0..n)] # Peter Luschny, Jan 09 2011

T(n,k) = GAMMA(n+k)/GAMMA(n) for n>0. - Peter Luschny, Jan 09 2011

A203470 a(n) = Product_{2 <= i < j <= n+1} (i + j).

Original entry on oeis.org

1, 5, 210, 105840, 838252800, 129459762432000, 466521199899955200000, 45727437650097816797184000000, 139352822480378029387123167068160000000, 14863555768518278744824500982673408262144000000000, 61707340455179609358720715109663452970925870494515200000000000

Offset: 1

Clark Kimberling, Jan 02 2012

Each term divides its successor, as (conjectured) in A102693. Each term is divisible by the corresponding superfactorial, A000178(n), as in A203471.

G. C. Greubel, Table of n, a(n) for n = 1..36

Cf. A000178, A102693, A203471.

[(&*[Factorial(2*k-1)/Factorial(k+1): k in [2..n+1]]): n in [1..20]]; // G. C. Greubel, Aug 29 2023

a:= n-> mul(mul(i+j, i=2..j-1), j=3..n+1):
seq(a(n), n=1..12);  # Alois P. Heinz, Jul 23 2017

(* First program *)
f[j_]:= j+1; z = 16;
v[n_]:= Product[Product[f[k] + f[j], {j,k-1}], {k,2,n}]
d[n_]:= Product[(i-1)!, {i,n}]
Table[v[n], {n, z}]           (* A203470 *)
Table[v[n+1]/v[n], {n, z-1}]  (* A102693 *)
Table[v[n]/d[n], {n, 20}]     (* A203471 *)
(* Second program *)
Table[Product[Gamma[2*j]/Gamma[j+2], {j,2,n+1}], {n,20}] (* G. C. Greubel, Aug 29 2023 *)

from math import prod, factorial
def A203470(n): return prod(factorial(2*k+1)//factorial(k+2) for k in range(1,n+1)) # Chai Wah Wu, Aug 26 2025

[product(gamma(2*k)/gamma(k+2) for k in range(2,n+2)) for n in range(1,20)] # G. C. Greubel, Aug 29 2023

a(n) ~ sqrt(A) * 2^(n^2 + 5*n/2 + 41/24) * exp(-3*n^2/4 + n/2 - 1/24) * n^(n^2/2 - n/2 - 71/24) / Pi, where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, Apr 08 2021
From G. C. Greubel, Aug 29 2023: (Start)
a(n) = Product_{j=2..n+1} Gamma(2*j)/Gamma(j+2).
a(n) = (2/sqrt(Pi))*( 2^(n+1)^2 * BarnesG(n+5/2)/(Pi^(n/2)*Gamma(n+2)*Gamma(n+3)*BarnesG(3/2)) ).
a(n) = (BarnesG(n+2)/2^n) * Product_{j=2..n+1} Catalan(j). (End)

Name edited by Alois P. Heinz, Jul 23 2017

A203471 a(n) = v(n)/A000178(n), v = A203470, A000178 = (superfactorials).

Original entry on oeis.org

1, 5, 105, 8820, 2910600, 3745942200, 18748440711000, 364619674947528000, 27558684271884061296000, 8100324068034882136733280000, 9267305355220395466643896716480000, 41308086890359390753018505224037952000000

Offset: 1

Clark Kimberling, Jan 02 2012

nonn

G. C. Greubel, Table of n, a(n) for n = 1..55

Cf. A000178, A007685, A102693, A203470, A296589, A338550.

[(&*[Factorial(2*k+1)/(Factorial(k-1)*Factorial(k+2)): k in [1..n]]): n in [1..20]]; // G. C. Greubel, Aug 29 2023

(* First program *)
f[j_]:= j+1; z = 16;
v[n_]:= Product[Product[f[k] + f[j], {j,k-1}], {k,2,n}]
d[n_]:= Product[(i-1)!, {i,n}]
Table[v[n], {n, z}]           (* A203470 *)
Table[v[n+1]/v[n], {n, z-1}]  (* A102693 *)
Table[v[n]/d[n], {n, 20}]     (* A203471 *)
(* Second program *)
Table[Product[Gamma[2*j+2]/(Gamma[j]*Gamma[j+3]), {j,n}], {n,20}] (* G. C. Greubel, Aug 29 2023 *)

[product(gamma(2*k+4)/(gamma(k+1)*gamma(k+4)) for k in range(n)) for n in range(1, 20)] # G. C. Greubel, Aug 29 2023

From G. C. Greubel, Aug 29 2023: (Start)
a(n) = Product_{j=1..n} Gamma(2*j+2)/(Gamma(j)*Gamma(j+3)).
a(n) = (2/sqrt(Pi))*( 2^(n+1)^2 * BarnesG(n+5/2) /(Pi^(n/2) * Gamma(n+2)*Gamma(n+3)*BarnesG(3/2)*BarnesG(n+1)) ).
a(n) = (BarnesG(n+2)/(2^n * BarnesG(n+1))) * Product_{j=1..n} Catalan(j+1). (End)
a(n) ~ A^(3/2) * 2^(n^2 + 2*n + 41/24) * exp(n/2 - 1/8) / (n^(n/2 + 23/8) * Pi^(n/2 + 1)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, Nov 19 2023
a(n) = Product_{1 <= j <= i <= n-1}  (i + j + 3)/(i - j + 1). - Peter Bala, Oct 25 2024

A262034 Number of permutations of [n] beginning with at least ceiling(n/2) ascents.

Original entry on oeis.org

1, 0, 1, 1, 4, 5, 30, 42, 336, 504, 5040, 7920, 95040, 154440, 2162160, 3603600, 57657600, 98017920, 1764322560, 3047466240, 60949324800, 106661318400, 2346549004800, 4151586700800, 99638080819200, 177925144320000, 4626053752320000, 8326896754176000

Offset: 0

Alois P. Heinz, Sep 08 2015

nonn

			a(4) = 4: 1234, 1243, 1342, 2341.
a(5) = 5: 12345, 12354, 12453, 13452, 23451.

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

Cf. A001761, A102693, A262033, A262035.

a:= proc(n) option remember; `if`(n<4, [1, 0, 1$2][n+1],
      2*((n^2-1)*a(n-2)-a(n-1))/(n+3))
    end:
seq(a(n), n=0..30);

np=Rest[With[{nn=30},CoefficientList[Series[(Exp[x^2](x+1)-x^4/2+x^2+x+1)/ x^3,{x,0,nn}],x] Range[0,nn]!]//Quiet];Join[{1},np] (* Harvey P. Dale, May 18 2019 *)

E.g.f.: (exp(x^2)*(x+1)-(x^4/2+x^2+x+1))/x^3.
a(n) = 2*((n^2-1)*a(n-2)-a(n-1))/(n+3) for n>3, a(0)=a(2)=a(3)=1, a(1)=0.
a(n) = n!/(n/2+1)! if n even, a(n) = floor(C(n+1,(n+1)/2)/(n+3)*((n-1)/2)!) if n odd.
a(2n) = A262033(2n) = A001761(n).
a(2n+1) = A102693(n+1).
Sum_{n>=2} 1/a(n) = (39*exp(1/4)*sqrt(Pi)*erf(1/2) - 6)/16, where erf is the error function. - Amiram Eldar, Dec 04 2022

cp's OEIS Frontend

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A065866 a(n) = n! * Catalan(n+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A124320 Triangle read by rows: T(n,k) = k!*binomial(n+k-1,k) (n >= 0, 0 <= k <= n), rising factorial power, Pochhammer symbol.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A203470 a(n) = Product_{2 <= i < j <= n+1} (i + j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

SageMath

Formula

Extensions

A203471 a(n) = v(n)/A000178(n), v = A203470, A000178 = (superfactorials).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A262034 Number of permutations of [n] beginning with at least ceiling(n/2) ascents.

Views

Author

Keywords

Examples

Links