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,14

Comments

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

Links

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

Example

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 ...
...

Prog

(PARI) \\ 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, ])) }

Crossrefs

Columns k=1..4 are A000012, A000055(n+1), A003081, A287892.

Cf. A303694, A332648, A332650, A332651.

Sequence in context: A294775 A369929 A330461 * A321724 A333737 A333733

Adjacent sequences: A332646 A332647 A332648 * A332650 A332651 A332652

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 18 2020

Status

approved