A398114 Array read by antidiagonals: T(n,k) is the number of unlabeled k-gonal cacti having n polygons with each vertex in at most two polygons, n >= 0, k >= 1.

1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 2, 1, 0, 1, 1, 1, 2, 4, 2, 1, 0, 1, 1, 1, 3, 5, 11, 4, 1, 0, 1, 1, 1, 3, 9, 15, 30, 6, 1, 0, 1, 1, 1, 4, 10, 39, 55, 96, 11, 1, 0, 1, 1, 1, 4, 15, 49, 187, 212, 319, 18, 1, 0, 1, 1, 1, 5, 17, 96, 276, 1046, 903, 1135, 37, 1, 0

Offset

0,25

Comments

Removing a cut point in these cacti separates the graph into exactly 2 connected components. Equivalently, these are the cacti whose vertex degrees are at most 4.

Links

Table of n, a(n) for n=0..90.

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 | 0  1  1   2   2    3     3     4     4 ...
  4 | 0  1  2   4   5    9    10    15    17 ...
  5 | 0  1  2  11  15   39    49    96   114 ...
  6 | 0  1  4  30  55  187   276   661   882 ...
  7 | 0  1  6  96 212 1046  1756  5292  7779 ...
  8 | 0  1 11 319 903 6141 11954 44711 72890 ...
  ...
The T(4,3) = 2 cacti are:
   o---o---o---o---o     o---o---o---o
    \ / \ / \ / \ /       \ / \ / \ /
     o   o   o   o         o   o   o
                              / \
                             o---o
The T(4,4) = 4 cacti are:
    o--o          o--o          o--o       o--o
    |  |          |  |          |  |       |  |
    o--o--o       o--o--o       o--o--o    o--o--o
       |  |          |  |          |  |       |  |
       o--o--o       o--o--o    o--o--o    o--o--o--o
          |  |          |  |    |  |       |  |  |  |
          o--o--o    o--o--o    o--o--o    o--o  o--o
             |  |    |  |          |  |
             o--o    o--o          o--o

Prog

(PARI)
G(n, k) = { if(k==0, 1+x+O(x*x^n), my(g=O(1)); for(i=0, n, g = 1+x*(g^k + g^(k%2)*subst(g^(k\2), x, x^2))/2); g) }
CPalK(g, k) = { my(g2=subst(g, x, x^2)); if(k%2, g*g2^(k\2), (g^2*g2^(k/2-1) + g2^(k/2))/2) }
U(n, k)={ my(g = G(n-1, k-1)); 1 + (subst(g-1, x, x^2) - (g - 1)^2)/2 + x*(CPalK(g, k) + sumdiv(k, d, eulerphi(d)*subst((g + O(x^(n\d+1)))^(k/d), x, x^d))/k)/2 }
T(n, m=n+1)={Mat(vector(m, k, Col(U(n, k))))}
{ my(A=T(8)); for(n=1, #A, print(A[n, ])) }

Crossrefs

Columns k=2..5 are A000012, A000672, A135527, A398115.

Cf. A332649, A398112 (rooted at vertex).

Sequence in context: A327688 A395191 A055800 * A060572 A163543 A358095

Adjacent sequences: A398111 A398112 A398113 * A398115 A398122 A398123

Keyword

nonn,tabl,new

Author

Andrew Howroyd, Jul 23 2026

Status

approved