A398112 Array read by antidiagonals: T(n,k) is the number of rooted 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, 2, 0, 1, 1, 2, 2, 0, 1, 1, 3, 3, 3, 0, 1, 1, 3, 8, 6, 3, 0, 1, 1, 4, 10, 28, 11, 4, 0, 1, 1, 4, 18, 41, 98, 23, 4, 0, 1, 1, 5, 21, 102, 181, 372, 46, 5, 0, 1, 1, 5, 32, 133, 618, 853, 1438, 98, 5, 0, 1, 1, 6, 36, 253, 931, 4000, 4164, 5745, 207, 6, 0

Offset

0,9

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

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Wikipedia, Cactus graph.

Index entries for sequences related to cacti

Example

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 | 0  2  3    8    10     18     21      32 ...
  4 | 0  3  6   28    41    102    133     253 ...
  5 | 0  3 11   98   181    618    931    2184 ...
  6 | 0  4 23  372   853   4000   6918   20068 ...
  7 | 0  4 46 1438  4164  26848  53536  191890 ...
  8 | 0  5 98 5745 20955 185689 426746 1890541 ...
  ...
T(4,2) = 3 because the only cactus consists of 4 digons, but there are 3 distinguishable ways to choose a root vertex. The graph is shown below:
     o===o===o===o===o
T(4,3) = 6 because there are two such cacti which can be rooted at a vertex in 4 + 2 = 6 ways:
   o---o---o---o---o     o---o---o---o
    \ / \ / \ / \ /       \ / \ / \ /
     o   o   o   o         o   o   o
                              / \
        (4)                  o---o
                              (2)

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)
R(n, k) = { my(g=G(n, k-1)); (g^2 + subst(g, x, x^2))/2 }
T(n, m=n+1)={Mat(vector(m, k, Col(R(n, k))))}
{ my(A=T(8)); for(n=1, #A, print(A[n, ])) }

Crossrefs

Columns 2..4 are A008619, A001190(n+2), A398113.

Cf. A332648, A398114 (unrooted).

Sequence in context: A026931 A339823 A127506 * A353433 A007968 A236532

Adjacent sequences: A398109 A398110 A398111 * A398113 A398114 A398115

Keyword

nonn,tabl,new

Author

Andrew Howroyd, Jul 23 2026

Status

approved