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

A346925 a(n) = Sum_{d|n} mu(n/d) * binomial(3d,d) / (2d+1).

Original entry on oeis.org

1, 2, 11, 52, 272, 1414, 7751, 43208, 246663, 1430440, 8414639, 50065628, 300830571, 1822758766, 11124755380, 68328711696, 422030545334, 2619630794574, 16332922290299, 102240108466928, 642312451209982, 4048514835624478, 25594403741131679, 162250237951706584

Offset: 1

Ilya Gutkovskiy, Aug 07 2021

nonn

Moebius transform of A001764.

Cf. A001764, A002996, A008683.

Table[Sum[MoebiusMu[n/d] Binomial[3 d, d]/(2 d + 1), {d, Divisors[n]}], {n, 24}]

a(n) = sumdiv(n, d, moebius(n/d)*binomial(3*d, d)/(2*d+1)); \\ Michel Marcus, Aug 07 2021

A346935 a(n) = Sum_{d|n} mu(n/d) * binomial(4d,d) / (3d+1).

Original entry on oeis.org

1, 3, 21, 136, 968, 7059, 53819, 420592, 3362238, 27342916, 225568797, 1882926144, 15875338989, 134993712777, 1156393242330, 9969937070688, 86445222719723, 753310719641286, 6594154339031799, 57956002304003096, 511238042454487704, 4524678117713613419, 40166643855158315819

Offset: 1

Ilya Gutkovskiy, Aug 08 2021

nonn

Moebius transform of A002293.

Cf. A002293, A002996, A008683, A346925, A346936, A346937, A346938, A346939.

Table[Sum[MoebiusMu[n/d] Binomial[4 d, d]/(3 d + 1), {d, Divisors[n]}], {n, 23}]

A346936 a(n) = Sum_{d|n} mu(n/d) * binomial(5d,d) / (4d+1).

Original entry on oeis.org

1, 4, 34, 280, 2529, 23712, 231879, 2330160, 23950320, 250540836, 2658968129, 28558319744, 309831575759, 3390416555996, 37377257156716, 414741861215840, 4628362722856424, 51912988232308104, 584909606696793884, 6617078646710069720, 75134301594081157746, 855968478539048248916

Offset: 1

Ilya Gutkovskiy, Aug 08 2021

nonn

Moebius transform of A002294.

Cf. A002294, A002996, A008683, A346925, A346935, A346937, A346938, A346939.

Table[Sum[MoebiusMu[n/d] Binomial[5 d, d]/(4 d + 1), {d, Divisors[n]}], {n, 22}]

A346937 a(n) = Sum_{d|n} mu(n/d) * binomial(6d,d) / (5d+1).

Original entry on oeis.org

1, 5, 50, 500, 5480, 62776, 749397, 9203128, 115607259, 1478308780, 19180049927, 251857056364, 3340843549854, 44700484300317, 602574657421585, 8175951649914160, 111572030260242089, 1530312970224714489, 21085148778264281864, 291705220703240850760, 4050527291832419432577

Offset: 1

Ilya Gutkovskiy, Aug 08 2021

nonn

Moebius transform of A002295.

Cf. A002295, A002996, A008683, A346925, A346935, A346936, A346938, A346939.

Table[Sum[MoebiusMu[n/d] Binomial[6 d, d]/(5 d + 1), {d, Divisors[n]}], {n, 21}]

A346938 a(n) = Sum_{d|n} mu(n/d) * binomial(7d,d) / (6d+1).

Original entry on oeis.org

1, 6, 69, 812, 10471, 141702, 1997687, 28988856, 430321563, 6503342378, 99726673129, 1547847703500, 24269405074739, 383846166714410, 6116574500850339, 98106248277869040, 1582638261961640246, 25661404527359789034, 417980115131315136399, 6836064539918615002932

Offset: 1

Ilya Gutkovskiy, Aug 08 2021

nonn

Moebius transform of A002296.

Cf. A002296, A002996, A008683, A346925, A346935, A346936, A346937, A346939.

Table[Sum[MoebiusMu[n/d] Binomial[7 d, d]/(6 d + 1), {d, Divisors[n]}], {n, 20}]

A346939 a(n) = Sum_{d|n} mu(n/d) * binomial(8d,d) / (7d+1).

Original entry on oeis.org

1, 7, 91, 1232, 18277, 285285, 4638347, 77650784, 1329890613, 23190011435, 410333440535, 7349042707872, 132969010888279, 2426870701777445, 44627576949345735, 826044435331747776, 15378186970730687399, 287756293702214647875, 5409093674555090316299, 102094541350713952736608

Offset: 1

Ilya Gutkovskiy, Aug 08 2021

nonn

Moebius transform of A007556.

Cf. A002996, A007556, A008683, A346925, A346935, A346936, A346937, A346938.

Table[Sum[MoebiusMu[n/d] Binomial[8 d, d]/(7 d + 1), {d, Divisors[n]}], {n, 20}]

A172354 n such that the Moebius function take successively, from n, the values -1,0,-1,0,-1,0.

Original entry on oeis.org

195, 1491, 1547, 1947, 2139, 2715, 2749, 2751, 2847, 2967, 3359, 3615, 3819, 4011, 4013, 4015, 4047, 4155, 4547, 5019, 5449, 5647, 5741, 5779, 6351, 6353, 6355, 6447, 6547, 6563, 6565, 6567, 6947, 6959, 6961, 6963, 7347, 7503, 7545, 7683, 8007, 9339, 10091

Offset: 1

Michel Lagneau, Feb 01 2010

nonn

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, p. 826.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 262 and 287.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Marc Deléglise and Joël Rivat, Computing the summation of the Mobius function, Experiment. Math. 5:4 (1996), pp. 291-295.
Ed Pegg Jr., The Mobius function (and squarefree numbers)
Primefan, Mobius and Mertens Values For n=1 to 2500
G. Villemin's Almanac of Numbers, Nombres de Moebius et de Mertens

Moebius (or Möbius) function mu(n): A008683, A007423, A002321, A002996.

with(numtheory): for n from 1 to 15000 do;if mobius(n)= -1 and mobius(n+1) = 0 and mobius(n+2)= -1 and mobius(n+3)= 0 and mobius(n+4)= -1 and mobius(n+5) = 0 then print(n); else fi ; od;

SequencePosition[MoebiusMu[Range[11000]],{-1,0,-1,0,-1,0}][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Sep 17 2016 *)

is(n)=moebius(n)<0 && !moebius(n+1) && moebius(n+2)<0 && !moebius(n+3) && moebius(n+4)<0 && !moebius(n+5) \\ Charles R Greathouse IV, Sep 26 2013

a(4) inserted by Charles R Greathouse IV, Sep 26 2013

A130513 Subtriangle of triangle in A051168: remove central column of A051168 and all columns to the right; now read by upwards diagonals.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 5, 2, 1, 0, 14, 7, 3, 1, 0, 42, 20, 9, 3, 1, 0, 132, 66, 30, 12, 4, 1, 0, 429, 212, 99, 40, 15, 4, 1, 0, 1430, 715, 333, 143, 55, 18, 5, 1, 0, 4862, 2424, 1144, 497, 200, 70, 22, 5, 1, 0, 16796, 8398, 3978, 1768, 728, 273, 91, 26, 6, 1, 0, 58786, 29372, 13995

Offset: 1

Philippe Deléham, Aug 08 2007

			Triangle T(n,k), 1<=k<=n, begins:
1;
1, 0;
2, 1, 0;
5, 2, 1, 0;
14, 7, 3, 1, 0;
42, 20, 9, 3, 1, 0;
132, 66, 30, 12, 4, 1, 0;
429, 212, 99, 40, 15, 4, 1, 0;

A. Errera, Analysis situs: Un problème d'énumération, Memoires Acad. Bruxelles (1931), Serie 2, Vol. 11, No. 6, 26pp.

Cf. A000108, A000150, A050181, A050182, A050183, A050184, A050185.

Table[1/(2n-k) Plus@@ (MoebiusMu[ # ]Binomial[(2n-k)/#,(n-k)/# ]&/@ Divisors[GCD[2n-k,n-k]]),{n,12},{k,n}] (* Wouter Meeussen, Jul 20 2008 *)

Sum_{k, 1<=k<=n} T(n,k) = A022553(n); Sum_{k, 1<=k<=n}k*T(n,k) = A002996(n).

T(n,k) = 1/(2n-k) Sum( d | gcd(2n-k,n-k) = mu(d) C((2n-k)/d,(n-k)/d) ). - Wouter Meeussen, Jul 20 2008

Edited by N. J. A. Sloane, Oct 08 2007

A286310 G.f.: 1 + Sum_{n>=1} a(n)x^n/(1 - x^n) = 1/(1 - x/(1 - 2x/(1 - 3x/(1 - 4x/(1 - ...))))).

Original entry on oeis.org

1, 2, 14, 102, 944, 10378, 135134, 2026920, 34459410, 654728128, 13749310574, 316234132728, 7905853580624, 213458046541738, 6190283353628416, 191898783960483600, 6332659870762850624, 221643095476665302070, 8200794532637891559374, 319830986772877116086448

Offset: 1

Ilya Gutkovskiy, May 06 2017

nonn

			G.f.: 1 + x/(1 - x) + 2*x^2/(1 - x^2) + 14*x^3/(1 - x^3) + 102*x^4/(1 - x^4) + ... = 1/(1 - x/(1 - 2*x/(1 - 3*x/(1 - 4*x/(1 - ...))))).

N. J. A. Sloane, Transforms

Cf. A001147, A002996, A062794.

nn = 20; f[x_] := 1 + Sum[a[n] x^n/(1 - x^n), {n, 1, nn}]; sol = SolveAlways[0 == Series[f[x] - 1/(1 + ContinuedFractionK[-n x, 1, {n, 1, nn}]), {x, 0, nn}], x]; Table[a[n], {n, 1, nn}] /. sol // Flatten
a[n_] := Sum[MoebiusMu[n/d] (2 d - 1)!!, {d, Divisors[n]}]; Array[a, 20]

Sum_{d|n} a(d) = A001147(n) for n > 0.

a(n) ~ 2^(n + 1/2) * n^n / exp(n). - Vaclav Kotesovec, Sep 16 2021

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

A346925 a(n) = Sum_{d|n} mu(n/d) * binomial(3*d,d) / (2*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A346935 a(n) = Sum_{d|n} mu(n/d) * binomial(4*d,d) / (3*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A346936 a(n) = Sum_{d|n} mu(n/d) * binomial(5*d,d) / (4*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A346937 a(n) = Sum_{d|n} mu(n/d) * binomial(6*d,d) / (5*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A346938 a(n) = Sum_{d|n} mu(n/d) * binomial(7*d,d) / (6*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A346939 a(n) = Sum_{d|n} mu(n/d) * binomial(8*d,d) / (7*d+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A172354 n such that the Moebius function take successively, from n, the values -1,0,-1,0,-1,0.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A130513 Subtriangle of triangle in A051168: remove central column of A051168 and all columns to the right; now read by upwards diagonals.

Views

Author

A346925 a(n) = Sum_{d|n} mu(n/d) * binomial(3d,d) / (2d+1).

A346935 a(n) = Sum_{d|n} mu(n/d) * binomial(4d,d) / (3d+1).

A346936 a(n) = Sum_{d|n} mu(n/d) * binomial(5d,d) / (4d+1).

A346937 a(n) = Sum_{d|n} mu(n/d) * binomial(6d,d) / (5d+1).

A346938 a(n) = Sum_{d|n} mu(n/d) * binomial(7d,d) / (6d+1).

A346939 a(n) = Sum_{d|n} mu(n/d) * binomial(8d,d) / (7d+1).

A286310 G.f.: 1 + Sum_{n>=1} a(n)x^n/(1 - x^n) = 1/(1 - x/(1 - 2x/(1 - 3x/(1 - 4x/(1 - ...))))).