A398112 - OEIS

%I #14 Jul 24 2026 14:18:20

%S 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,

%T 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,

%U 133,618,853,1438,98,5,0,1,1,6,36,253,931,4000,4164,5745,207,6,0

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

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

%H Andrew Howroyd, <a href="/A398112/b398112.txt">Table of n, a(n) for n = 0..1325</a> (first 51 antidiagonals)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cactus_graph">Cactus graph</a>.

%H <a href="/index/Ca#cacti">Index entries for sequences related to cacti</a>

%e Array begins:

%e ==================================================

%e n\k | 1  2  3    4     5      6      7       8 ...

%e ----+---------------------------------------------

%e   0 | 1  1  1    1     1      1      1       1 ...

%e   1 | 1  1  1    1     1      1      1       1 ...

%e   2 | 1  2  2    3     3      4      4       5 ...

%e   3 | 0  2  3    8    10     18     21      32 ...

%e   4 | 0  3  6   28    41    102    133     253 ...

%e   5 | 0  3 11   98   181    618    931    2184 ...

%e   6 | 0  4 23  372   853   4000   6918   20068 ...

%e   7 | 0  4 46 1438  4164  26848  53536  191890 ...

%e   8 | 0  5 98 5745 20955 185689 426746 1890541 ...

%e   ...

%e 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:

%e      o===o===o===o===o

%e T(4,3) = 6 because there are two such cacti which can be rooted at a vertex in 4 + 2 = 6 ways:

%e    o---o---o---o---o     o---o---o---o

%e     \ / \ / \ / \ /       \ / \ / \ /

%e      o   o   o   o         o   o   o

%e                               / \

%e         (4)                  o---o

%e                               (2)

%o (PARI)

%o 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)

%o R(n,k) = { my(g=G(n,k-1)); (g^2 + subst(g,x,x^2))/2 }

%o T(n, m=n+1)={Mat(vector(m, k, Col(R(n, k))))}

%o { my(A=T(8)); for(n=1, #A, print(A[n, ])) }

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

%Y Cf. A332648, A398114 (unrooted).

%K nonn,tabl,new

%O 0,9

%A _Andrew Howroyd_, Jul 23 2026