A002995 -id:A002995 - cp's OEIS frontend

A384964 Triangle read by rows: T(n,k) is the number of embeddings on the sphere of connected simple planar graphs with n nodes and k faces up to orientation preserving isomorphisms, n >= 1, k=1..max(1,2*n-4).

1, 1, 1, 1, 2, 2, 1, 1, 3, 8, 8, 6, 2, 1, 6, 29, 60, 73, 52, 25, 6, 2, 14, 113, 388, 768, 903, 728, 379, 136, 26, 6, 34, 444, 2303, 6584, 11782, 14321, 12113, 7298, 3048, 872, 147, 17, 95, 1763, 12650, 49806, 123547, 210314, 255884, 228807, 150929, 73428, 25536, 6142, 892, 73

Offset: 1

Andrew Howroyd, Jun 13 2025

Equivalently, T(n,k) is the number of sensed simple planar maps with n vertices and k faces.
The number of edges is n+k-2.
Terms of this sequence can be computed using the tool "plantri". The expanded reference gives rows 1..14 of this table.

			Triangle begins:
   1;
   1;
   1,   1,
   2,   2,    1,    1,
   3,   8,    8,    6,     2,     1,
   6,  29,   60,   73,    52,    25,     6,    2,
  14, 113,  388,  768,   903,   728,   379,  136,   26,   6,
  34, 444, 2303, 6584, 11782, 14321, 12113, 7298, 3048, 872, 147, 17;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..158 (rows 1..14)
Gunnar Brinkmann and Brendan McKay, Fast generation of planar graphs (expanded edition), Tables 19-22.

Row sums are A384965.
Antidiagonal sums are A006394.
Columns 1..2 are A002995, A384966.
Cf. A379430 (not necessarily simple), A342059 (2-connected), A239893 (3-connected), A384963 (unsensed).

A005354 Number of asymmetric planar trees with n nodes.

Original entry on oeis.org

1, 1, 0, 0, 0, 1, 3, 9, 28, 85, 262, 827, 2651, 8626, 28507, 95393, 322938, 1104525, 3812367, 13266366, 46504495, 164098390, 582521687, 2079133141, 7457788295, 26872946466, 97238824018, 353218128299, 1287657977946, 4709784136316

Offset: 0

N. J. A. Sloane, Simon Plouffe, Susanna Cuyler

a(13) in the Labelle table is a typographical error. - R. J. Mathar, Feb 03 2010

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from Vincenzo Librandi)
Gilbert Labelle, Counting asymmetric enriched trees, J. Symbolic Comput. 14 (1992), no. 2-3, 211-242.
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.
T. 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.
Index entries for sequences related to trees

Cf. A000108, A002995, A022553.

From R. J. Mathar, Feb 03 2010: (Start)
A000108 := proc(n) binomial(2*n,n)/(n+1) ; end proc:
A007727 := proc(n) local a,d; a := 0 ; for d in numtheory[divisors](n) do a := a+binomial(2*d,d)*numtheory[mobius](n/d) ; end do ; a ; end proc;
A022553 := proc(n) A007727(n)/2/n ; end proc:
A005354 := proc(n) local a; if n <=1 then 1; else a := A022553(n-1) ; a := a-A000108(n-1)/2 ; if type(n,'even') then a := a-A000108(n/2-1)/2 ; end if; a ; end if; end proc: seq(A005354(n),n=0..20) ; (End)

a[0] = a[1] = 1; a[n_] := DivisorSum[n-1, MoebiusMu[(n-1)/#]*Binomial[2#, #]&]/(2(n-1)) - CatalanNumber[n-1]/2 - Boole[EvenQ[n]]*CatalanNumber[n/2 - 1]/2; Table[a[n], {n, 0, 29}] (* Jean-François Alcover, May 09 2012, after R. J. Mathar, updated Jan 31 2018 *)

From Christian G. Bower, Dec 15 1999: (Start)
G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A022553(n-1) and C is g.f. of A000108(n-1).
a(n) = A022553(n-1) - A000108(n-2)/2 - (if n is even) A000108(n/2-1)/2. (End)

More terms from Christian G. Bower, Dec 15 1999

A038775 a(n) is the number of cycles of the permutation that converts forest(n) of depth-first planar planted binary trees into breadth-first representation.

Original entry on oeis.org

1, 2, 3, 6, 10, 12, 17, 26, 34, 50, 56, 68, 82, 94, 113

Offset: 1

Wouter Meeussen, May 04 2000

The first a(n) terms of A038774 add up to Catalan(n) = A000108(n).

			a(5)=10 since there are 10 cycles in this permutation of forest(5), with lengths 1, 1, 3, 4, 3, 2, 16, 8, 2, 2 summing up to 42=Catalan(5).

Sean A. Irvine, Java program (github)

Cf. A000108, A038774.

Similarly generated sequences: A001683, A002995, A003239, A057507, A057513.

a(13)-a(15) from Sean A. Irvine, May 22 2022

A085173 Permutation of natural numbers induced by the Catalan bijection gma085173 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 5, 6, 4, 22, 21, 18, 20, 17, 13, 12, 15, 19, 14, 10, 16, 11, 9, 64, 63, 59, 62, 58, 50, 49, 55, 61, 54, 46, 57, 48, 45, 36, 35, 32, 34, 31, 41, 40, 52, 60, 51, 38, 56, 39, 37, 27, 26, 43, 47, 42, 29, 53, 33, 28, 24, 44, 30, 25, 23, 196, 195, 190, 194, 189

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "rising slope" mapping illustrated in A085161.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085174. a(n) = A085161(A085174(A085161(n))) = A085169(A057501(A085170(n))) = A074684(A057501(A074683(n))). Occurs in A073200. Cf. also A085159 (whole step rotate), A086427.

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A054358 Number of unlabeled asymmetric 2-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 0, 1, 2, 8, 18, 61, 170, 538, 1654, 5344, 17252, 57146, 190786, 646305, 2209050, 7626164, 26532732, 93013852, 328196780, 1165060170, 4158266282, 14915635376, 53745892932, 194477856048, 706436256598, 2575316698792, 9419568272632

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=2 of A303913.

Cf. A002995, A054357.

a[0] = 1; a[n_] := DivisorSum[n, MoebiusMu[n/#] Binomial[2#, #]&]/n - Binomial[2n, n]/(n+1);
Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jul 01 2018, after Andrew Howroyd *)

a(n) = if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(2*d, d))/n - binomial(2*n, n)/(n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} mu(n/d)*binomial(2*d, d)) - binomial(2*n, n)/(n+1) for n > 0. - Andrew Howroyd, May 02 2018

More terms from Vladeta Jovovic, Oct 04 2007

A085174 Permutation of natural numbers induced by the Catalan bijection gma085174 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 8, 6, 7, 5, 4, 22, 19, 21, 15, 14, 18, 16, 20, 13, 11, 17, 12, 10, 9, 64, 60, 63, 52, 51, 59, 56, 62, 41, 39, 58, 40, 38, 37, 50, 47, 49, 43, 42, 55, 53, 61, 36, 33, 54, 35, 29, 28, 46, 44, 57, 32, 30, 48, 34, 27, 25, 45, 31, 26, 24, 23, 196, 191, 195, 178, 177

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "rising slope" mapping illustrated in A085161.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085173. a(n) = A085161(A085173(A085161(n))) = A085169(A057502(A085170(n))) = A074684(A057502(A074683(n))). Occurs in A073200. Cf. also A085160 (whole step rotate), A086428.

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A003241 Number of achiral rooted trees.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 26, 45, 71, 110, 168, 247, 351, 503, 700, 944, 1294, 1719, 2267, 2961, 3839, 4891, 6297, 7891, 9912, 12347, 15381, 18784, 23203, 28138, 34233, 41275, 49824, 59306, 71309, 84268, 100127, 118045, 139472, 162659

Offset: 1

N. J. A. Sloane

nonn

There may be an error in eq (37) in the Harary-Robinson paper. - R. J. Mathar, Sep 28 2011

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jean-François Alcover, Table of n, a(n) for n = 1..80
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

L := BFILETOLIST("b003238.txt") ;
Pofxn := proc(n)
        global L;
        add( op(i,L)*x^(i+1),i=1..120) ;
        subs(x=x^n,%) ;
end proc:
P := Pofxn(1) ;
Rn := proc(n)
        global L;
        (Pofxn(n-2)*Pofxn(2)+Pofxn(n-1)*Pofxn(1)-Pofxn(n))/x^(n-1) ;
end proc:
Px2 := Pofxn(2) ;
Px3 := Pofxn(3) ;
Px4 := Pofxn(4) ;
# eq (37) seems not to work
# R := 2*x+P^2/x^2+(1-x)*P/x*(Px2/x^2-1)-(P^2-Px2)/2/x -Px3/x^2-(Px2^2-Px4)/2/x^3 ;
#use eqs (39)-(44) instead
R := x+P+(P^2+Px2)/2/x+P*Px2/x^2+P*Px3/x^3+(Px2^2-Px4)/2/x^3 :
# heuristics, adding up to R^(40) suffices for first 80 terms
for n from 5 to 40 do
        R := R+Rn(n) :
end do:
taylor(R,x=0,80) ;
gfun[seriestolist](%) ; # R. J. Mathar, Sep 28 2011

L = Cases[Import["https://oeis.org/A003238/b003238.txt", "Table"], {, }][[All, 2]];
Pofxn[n_] := Sum[x^(i+1) L[[i]], {i, 1, 120}] /. x -> x^n;
P = Pofxn[1];
Rn[n_] := (1/x^(n-1))(Pofxn[2] Pofxn[n-2] + Pofxn[1] Pofxn[n-1] - Pofxn[n]);
Px2 = Pofxn[2]; Px3 = Pofxn[3]; Px4 = Pofxn[4];
R = (P^2 + Px2)/(2x) + (P Px2)/x^2 + (P Px3)/x^3 + P + (Px2^2 - Px4)/(2x^3) + x;
For[n = 5, n <= 40, n++, R += Rn[n]];
CoefficientList[R + O[x]^41, x] // Rest (* Jean-François Alcover, Apr 06 2020, from Maple *)

Extended by R. J. Mathar, Sep 28 2011

A006936 Moebius transform of numbers of preferential arrangements.

Original entry on oeis.org

0, 1, 0, 2, 12, 74, 538, 4682, 47280, 545832, 7087186, 102247562, 1622632020, 28091567594, 526858343698, 10641342970366, 230283190930560, 5315654681981354, 130370767028589528, 3385534663256845322

Offset: 0

N. J. A. Sloane

nonn

Moebius transform of A000670(n-1)=[1,1,3,13,75,...] is a(n)=[1,0,2,12,74,...]. - Michael Somos, Mar 04 2004

G. C. Greubel, Table of n, a(n) for n = 0..420
David Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
N. J. A. Sloane, Transforms

Cf. A000670.

a[n_] := DivisorSum[n, MoebiusMu[n/#]*(#-1)!*SeriesCoefficient[1/(2-Exp[x + O[x]^#]), #-1]&]; a[0]=0; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Dec 03 2015, adapted from PARI *)

a(n)=if(n<1,0,sumdiv(n,d,moebius(n/d)*(d-1)!*polcoeff(1/(2-exp(x+O(x^d))),d-1)))

A106363 Planar trees where no branch is identical to its adjacent neighbor.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 3, 7, 14, 43, 115, 326, 931, 2719, 7979, 23804, 71418, 216444, 660276, 2028558, 6268350, 19479746, 60835542, 190881085, 601459251, 1902680249, 6040955223, 19245061851, 61503863732, 197135868680, 633615135842

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

Index entries for sequences related to trees

Cf. A002995.

G.f.: A(x) = B(x) + (C(x^2) - C(x)^2)/2. B(x) is g.f. of A106362. C(x) is g.f. of A106361.

A003240 Number of partially achiral rooted trees.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 62, 120, 236, 454, 884, 1697, 3275, 6266, 12020, 22935, 43788, 83325, 158516, 300914, 570794, 1081157, 2045934, 3867617, 7304149, 13783221, 25984936, 48956715, 92155376, 173376484, 325919786, 612378787, 1149777034

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 1..3760 (terms 1..70 from Herman Jamke)
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

t(n)=local(A=x); if(n<1, 0, for(k=1, n-1, A/=(1-x^k+x*O(x^n))^polcoeff(A, k)); polcoeff(A, n))
{n=100;Ty2=sum(i=0,100,t(i)*y^(2*i)); p=subst(y*Ty2/(y-Ty2),y,y+y*O(y^n));p=Pol(p,y); r=subst(Ty2*(y+p+(p^2-subst(p,y,y^2))/(2*y))/y^2,y,x+x*O(x^n)); for(I=1,n-2,print1(polcoeff(r,i)","))} \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 26 2008

a(n) ~ c * d^n * n, where d = 1.8332964415228533737988849634129366404833316666328290543862325494628120733... is the root of the equation Sum_{k>=1} A000081(k) / d^(2*k-1) = 1 and c = 0.030410107348865811204534352170117292921782094079168428605205142049899... - Vaclav Kotesovec, Dec 13 2020

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 26 2008

cp's OEIS Frontend

A384964 Triangle read by rows: T(n,k) is the number of embeddings on the sphere of connected simple planar graphs with n nodes and k faces up to orientation preserving isomorphisms, n >= 1, k=1..max(1,2*n-4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A005354 Number of asymmetric planar trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A038775 a(n) is the number of cycles of the permutation that converts forest(n) of depth-first planar planted binary trees into breadth-first representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A085173 Permutation of natural numbers induced by the Catalan bijection gma085173 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A054358 Number of unlabeled asymmetric 2-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A085174 Permutation of natural numbers induced by the Catalan bijection gma085174 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A003241 Number of achiral rooted trees.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Extensions

A006936 Moebius transform of numbers of preferential arrangements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A106363 Planar trees where no branch is identical to its adjacent neighbor.

Views

Author