A003080 -id:A003080 - cp's OEIS frontend

A035082 Number of rooted polygonal cacti (Husimi graphs) with n nodes.

0, 1, 0, 1, 1, 3, 5, 13, 27, 67, 157, 390, 963, 2437, 6186, 15908, 41127, 107148, 280569, 738675, 1953054, 5185364, 13816018, 36934431, 99030038, 266254593, 717652816, 1938831589, 5249221790, 14240130827, 38702218134, 105367669062

Offset: 0

Christian G. Bower, Nov 15 1998

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures.
F. Harary and E. M. Palmer, Graphical Enumeration, p. 71

Andrew Howroyd, Table of n, a(n) for n = 0..500
C. G. Bower, Transforms (2)
F. Harary and R. Z. Norman, The Dissimilarity Characteristic of Husimi Trees, Annals of Mathematics, 58 1953, pp. 134-141.
F. Harary and G. E. Uhlenbeck, On the Number of Husimi Trees, Proc. Nat. Acad. Sci. USA vol. 39 pp. 315-322 1953
N. J. A. Sloane, Transforms
Index entries for sequences related to cacti
Index entries for sequences related to rooted trees

Cf. A003080, A035083, A035084, A035085, A035086, A035087, A035088.

BIK(p)={(1/(1-p) + (1+p)/subst(1-p, x, x^2))/2}
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(p=O(x)); for(n=1, n, p=x+x^2*Ser(EulerT(Vec(BIK(p)-1)-Vec(p)))); concat([0], Vec(p))} \\ Andrew Howroyd, Aug 30 2018

Shifts left under transform T where Ta = EULER(BIK(a)-a).

A034940 Number of rooted labeled triangular cacti with 2n+1 nodes (n triangles).

Original entry on oeis.org

1, 3, 75, 5145, 688905, 152193195, 50174679555, 23089081640625, 14140034726843025, 11119632520038117075, 10920803043967635894075, 13100477280449146440878025, 18849023772776126861572265625, 32038907667175368299033846026875, 63516199119599233704934379969701875

Offset: 0

Christian G. Bower, Oct 15 1998

			E.g. a(3) = 5!! 7^3 = (1*3*5) * 343 = 5145.
From _Peter Bala_, Jul 31 2012: (Start)
Relation with rows of A214406: F(x) := A(exp(x)).
(d/dx)^1(F) = F/(1-F^2)
(d/dx)^2(F)) = F*(1 + F^2)/(1 - F^2)^3
(d/dx)^3(F)) = F*(1 + 8*F^2 + 3*F^4)/(1 - F^2)^5
(d/dx)^4(F)) = F*(1 + 33*F^2 + 71*F^4 + 15*F^6)/(1 - F^2)^7
(End)

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 307. (4.2.44)

Alois P. Heinz, Table of n, a(n) for n = 0..100
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
Wikipedia, Lagrange Inversion Theorem
Index entries for sequences related to cacti

Cf. A003080, A000169, A214406.

a[n_] := (2*n-1)!!*(2*n+1)^n; Table[a[n], {n, 0, 11}] (* Jean-François Alcover, May 13 2013, after Noam D. Elkies *)

a(n) = (2*n+1)^n*(2*n)!/(2^n*n!); \\ Andrew Howroyd, Aug 30 2018

a(n) = b(2*n+1) where e.g.f. of b satisfies B(x)=x*exp(B(x)^2/2).
The closed form a(n) = (2n-1)!! (2n+1)^n can be obtained from the generating function. - Noam D. Elkies, Dec 16 2002
From Peter Bala, Jul 31 2012: (Start)
E.g.f. A(x) = series reversion of x*exp(-1/2*x^2) = sum {n >= 0} a(n)*x^(2*n+1)/(2*n+1)! = x + 3*x^3/3! + 75*x^5/5! + .... The Lagrange inversion formula gives a(n) = (2*n+1)^n*(2*n)!/(2^n*n!).
A(x)^2 = T(x^2), where T denotes the tree function T(x) := sum {n >= 1} n^(n-1)*x^n/n!. A(x)^r = sum {n >= 0} r*(2*n+r)^(n-1)*x^(2*n+r)/(2^n*n!).
x = A(x)*exp(-1/2*A(x)^2). dA/dx = exp(1/2*A^2)/(1-A^2).
Let the function F(x) = A(exp(x)). Then dF/dx = F/(1-F^2). More generally, (d/dx)^(n+1)(F) is a rational function in F(x) given by (d/dx)^(n+1)(F) = F*R(n,F^2)/(1-F^2)^(2*n+1), where R(n,x) is the n-th row generating polynomial of A214406.
(End)

a(10) corrected by Jean-François Alcover, May 13 2013

a(12)-a(14) from Alois P. Heinz, Jul 08 2015

A287891 Number of rooted unlabeled 4-cactus graphs on 3n+1 nodes.

Original entry on oeis.org

1, 1, 3, 11, 46, 208, 1002, 5012, 25863, 136519, 733902, 4003475, 22106155, 123313289, 693871975, 3933700703, 22447035938, 128828019447, 743142630614, 4306327193744, 25056121416684, 146325789652514, 857393585946194, 5039223717251954, 29700183601347111, 175496470696059267

Offset: 0

N. J. A. Sloane, Jun 21 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..500
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.

Column k=4 of A332648.

Cf. A003080, A287889, A287890, A287892.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[]); for(n=1, n, my(g=1+x*Ser(v)); v=EulerT(Vec(g*(g^2 + subst(g, x, x^2))/2))); concat([1], v)} \\ Andrew Howroyd, Feb 17 2020

a(0) changed and terms a(11) and beyond from Andrew Howroyd, Feb 17 2020

A003081 Number of triangular cacti with 2n+1 nodes (n triangles).

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 19, 48, 126, 355, 1037, 3124, 9676, 30604, 98473, 321572, 1063146, 3552563, 11982142, 40746208, 139573646, 481232759, 1669024720, 5819537836, 20390462732, 71762924354, 253601229046, 899586777908, 3202234779826, 11435967528286, 40964243249727

Offset: 0

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 306, (4.2.35).
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 73, (3.4.21).
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
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992) pp. 53-80.
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)
Index entries for sequences related to cacti

Column k=3 of A332649.

Cf. A003080, A034940, A034941.

terms = 31;
nmax = 2 terms;
A[_] = 0;
Do[A[x_] = x Exp[Sum[(A[x^n]^2 + A[x^(2n)])/(2n), {n, 1, terms}]] + O[x]^nmax // Normal, {nmax}];
g[x_] = (A[x] /. x^k_ -> x^((k - 1)/2)) - x + 1;
g[x] + x((g[x^3] - g[x]^3)/3) + O[x]^terms // CoefficientList[#, x]& (* Jean-François Alcover, Feb 26 2020, after Andrew Howroyd *)

a(n)=b(2n+1). A003080(n)=c(2n+1).
G.f.: B(x)=C(x)+(C(x^3)-C(x)^3)/3.
G.f.: g(x) + x*(g(x^3) - g(x)^3)/3 where g(x) is the g.f. of A003080. - Andrew Howroyd, Feb 18 2020

Extended with formula by Christian G. Bower, 10/98

A332648 Array read by antidiagonals: T(n,k) is the number of rooted unlabeled k-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 3, 5, 9, 1, 1, 1, 3, 11, 13, 20, 1, 1, 1, 4, 13, 46, 37, 48, 1, 1, 1, 4, 22, 62, 208, 111, 115, 1, 1, 1, 5, 25, 140, 333, 1002, 345, 286, 1, 1, 1, 5, 37, 176, 985, 1894, 5012, 1105, 719, 1, 1, 1, 6, 41, 319, 1397, 7374, 11258, 25863, 3624, 1842, 1

Offset: 0

Andrew Howroyd, Feb 18 2020

The number of nodes will be n*(k-1) + 1.

			Array begins:
======================================================
n\k | 1   2    3     4     5      6      7       8
----+-------------------------------------------------
  0 | 1   1    1     1     1      1      1       1 ...
  1 | 1   1    1     1     1      1      1       1 ...
  2 | 1   2    2     3     3      4      4       5 ...
  3 | 1   4    5    11    13     22     25      37 ...
  4 | 1   9   13    46    62    140    176     319 ...
  5 | 1  20   37   208   333    985   1397    3059 ...
  6 | 1  48  111  1002  1894   7374  11757   31195 ...
  7 | 1 115  345  5012 11258  57577 103376  331991 ...
  8 | 1 286 1105 25863 68990 463670 937179 3643790 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Columns k=1..4 are A000012, A000081(n+1), A003080, A287891.

Cf. A303694, A332649.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[]); for(n=1, n, my(g=1+x*Ser(v)); v=EulerT(Vec((g^k + g^(k%2)*subst(g^(k\2), x, x^2))/2))); concat([1], v)}
T(n)={Mat(concat([vectorv(n+1,i,1)], vector(n,k,Col(R(n,k)))))}
{ my(A=T(8)); for(n=1, #A, print(A[n,])) }

A345955 Number of isomorphism classes of indecomposable Fano Bott manifolds of complex dimension n.

Original entry on oeis.org

1, 1, 3, 7, 21, 60, 189, 595, 1948, 6455, 21804, 74464, 257311, 896874, 3151564, 11148982, 39680010, 141969156, 510352307, 1842370850, 6676349598, 24277171876, 88556616799, 323959047186, 1188237214539, 4368874535437, 16099389598907, 59449932709972, 219953954227839

Offset: 1

Eunjeong Lee, Jun 29 2021

nonn

a(n) is also the number of rooted triangular cacti with 2n+1 nodes (n triangles) with one triangle at the root vertex.

Yunhyung Cho, Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, On the enumeration of Fano Bott manifolds, arXiv:2106.12788 [math.AG], 2021. See Table 1 p. 8.
Frank Harary and George E. Uhlenbeck, On the number of Husimi trees. I, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 315-322.

Cf. A003080.

G.f.: (x/2)*(F(x^2)+F(x)^2) where F(x) is the g.f. of A003080 (see the equation (1) in [Harary-Uhlenbeck] or [Cho-Lee-Masuda-Park, Lemma 4.3]).

cp's OEIS Frontend

A035082 Number of rooted polygonal cacti (Husimi graphs) with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

A034940 Number of rooted labeled triangular cacti with 2n+1 nodes (n triangles).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A287891 Number of rooted unlabeled 4-cactus graphs on 3n+1 nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A003081 Number of triangular cacti with 2n+1 nodes (n triangles).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A332648 Array read by antidiagonals: T(n,k) is the number of rooted unlabeled k-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A345955 Number of isomorphism classes of indecomposable Fano Bott manifolds of complex dimension n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula