OFFSET
0,14
COMMENTS
The number of noncrossing k-gonal cacti is given by column 2*(k-1) of A070914. This sequence enumerates these cacti with rotations being considered equivalent.
Equivalently, T(n,k) is the number of connected acyclic k-uniform noncrossing antichains with n blocks covering (k-1)*n+1 nodes where the intersection of two blocks is at most 1 node modulo cyclic rotation of the nodes.
Noncrossing trees correspond to the case of k = 2.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).
Wikipedia, Cactus graph.
FORMULA
T(0,k) = T(1,k) = T(2,k) = 1.
EXAMPLE
=====================================================
n\k | 1 2 3 4 5 6 ...
----+------------------------------------------------
0 | 1 1 1 1 1 1 ...
1 | 1 1 1 1 1 1 ...
2 | 1 1 1 1 1 1 ...
3 | 1 4 5 8 9 12 ...
4 | 1 11 33 63 105 159 ...
5 | 1 49 230 664 1419 2637 ...
6 | 1 204 1827 7462 21085 48048 ...
7 | 1 984 15466 90896 334707 941100 ...
8 | 1 4807 137085 1159587 5579961 19354687 ...
9 | 1 24739 1260545 15369761 96589350 413533260 ...
...
PROG
(PARI) \\ here u is Fuss-Catalan sequence with p = 2*k-1.
u(n, k, r) = {r*binomial(n*(2*k-1) + r, n)/(n*(2*k-1) + r)}
T(n, k) = if(n==0, 1, u(n, k, 1)/((k-1)*n+1) + sumdiv(gcd(k, n-1), d, if(d>1, eulerphi(d)*u((n-1)/d, k, 2*k/d)/k)))
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Mar 05 2023
STATUS
approved