A332651 -id:A332651 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 4, 6, 1, 1, 1, 1, 3, 7, 8, 11, 1, 1, 1, 1, 4, 8, 25, 19, 23, 1, 1, 1, 1, 4, 13, 31, 88, 48, 47, 1, 1, 1, 1, 5, 14, 67, 132, 366, 126, 106, 1, 1, 1, 1, 5, 20, 80, 372, 636, 1583, 355, 235, 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      9
----+-------------------------------------------------
  0 | 1  1   1    1    1     1     1     1      1 ...
  1 | 1  1   1    1    1     1     1     1      1 ...
  2 | 1  1   1    1    1     1     1     1      1 ...
  3 | 1  2   2    3    3     4     4     5      5 ...
  4 | 1  3   4    7    8    13    14    20     22 ...
  5 | 1  6   8   25   31    67    80   143    165 ...
  6 | 1 11  19   88  132   372   504  1093   1391 ...
  7 | 1 23  48  366  636  2419  3659  9722  13485 ...
  8 | 1 47 126 1583 3280 16551 28254 91391 138728 ...
...

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, A000055(n+1), A003081, A287892.

Cf. A303694, A332648, A332650, A332651.

\\ here R(n,k) is column k+1 of A332648.
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)}
U(n,k)={my(p=Ser(R(n,k-1))); my(g(d)=subst(p + O(x*x^(n\d)), x, x^d)); Vec(g(1) + x*sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/(2*k) - x*(g(1)^k)/2 + x*if(k%2==0, g(2)^(k/2) - g(1)^2*g(2)^(k/2-1))/4)}
T(n)={Mat(concat([vectorv(n+1,i,1)], vector(n, k, Col(U(n,k+1)))))}
{ my(A=T(8)); for(n=1, #A, print(A[n,])) }

A332650 Number of polygonal cacti on 2n-1 unlabeled nodes with every polygon having an odd prime number of edges.

Original entry on oeis.org

1, 1, 2, 4, 10, 30, 105, 400, 1654, 7229, 32944, 154749, 744973, 3655993, 18232812, 92162974, 471301437, 2434542190, 12687850499, 66646225443, 352548333438, 1876770716627, 10048289587337, 54079948967654, 292447643655469, 1588388448970674, 8661869330014601

Offset: 1

Andrew Howroyd, Feb 18 2020

nonn

			a(3) = 2 because there are two cacti on 5 nodes which are a pentagon and 2 triangles joined at a node.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Cf. A000083, A035085, A091487, A332649, A332651.

\\ Here UCacti gives number of unrooted cacti with restricted polygons.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
RCacti(u)={my(v=[1]); while(#v<#u, my(g=x*Ser(v), g2=subst(g,x,x^2) + O(x^2*x^#v), r=sum(k=1, #u-1, my(c=u[k+1]); if(c, c*(g^k + g^(k%2)*g2^(k\2))))/2 + O(x^#u)); v=concat([1], EulerT(Vec(r, 1-serprec(r, x))))); v}
UCacti(u)={my(p=x*Ser(RCacti(u))); my(g(d)=subst(p + O(x*x^(#u\d)), x, x^d)); Vec(g(1) + sum(k=1, #u, my(c=u[k]); if(c, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/(2*k) - (g(1)^k)/2 + if(k%2==0, g(2)^(k/2) - g(1)^2*g(2)^(k/2-1))/4)))}
seq(n)={my(v=UCacti(vector(2*n-1, i, i>2 && isprime(i)))); vector(n, i, v[2*i-1])}

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI