A361239 Array read by antidiagonals: T(n,k) is the number of noncrossing k-gonal cacti with n polygons up to rotation and reflection.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 4, 7, 1, 1, 1, 1, 6, 19, 28, 1, 1, 1, 1, 7, 35, 124, 108, 1, 1, 1, 1, 9, 57, 349, 931, 507, 1, 1, 1, 1, 10, 85, 737, 3766, 7801, 2431, 1, 1, 1, 1, 12, 117, 1359, 10601, 45632, 68685, 12441, 1

Offset: 0

Author

Andrew Howroyd, Mar 06 2023

Keywords

• nonn
• tabl

Examples

			Array begins:
===================================================
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     3      4       6        7         9 ...
  4 | 1     7     19      35       57        85 ...
  5 | 1    28    124     349      737      1359 ...
  6 | 1   108    931    3766    10601     24112 ...
  7 | 1   507   7801   45632   167741    471253 ...
  8 | 1  2431  68685  580203  2790873   9678999 ...
  9 | 1 12441 630850 7687128 48300850 206780448 ...
  ...
		

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.

Crossrefs

Columns 1..4 are A000012, A296533, A361240, A361241.

Row n=3 is A032766.

Cf. A361236, A361243.

Programs

PARI

\\ R(n,k) gives A361236.
u(n,k,r) = {r*binomial(n*(2*k-1) + r, n)/(n*(2*k-1) + r)}
R(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)))}
T(n, k) = {(R(n, k) + u(n\2, k, if(n%2, k, 1)))/2}

Formula

T(0,k) = T(1,k) = T(2,k) = 1.

T(2*n,k) = (A361236(2*n,k) + binomial((2*k-1)*n + 1, n)/((2*k-1)*n + 1))/2.

T(2*n+1,k) = (A361236(2*n+1,k) + k*binomial((2*k-1)*n + k, n)/((2*k-1)*n + k))/2.