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,14

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.

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.

Example

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

Prog

(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}

Crossrefs

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

Row n=3 is A032766.

Cf. A361236, A361243.

Sequence in context: A046534 A224489 A318933 * A140334 A131324 A371884

Adjacent sequences: A361236 A361237 A361238 * A361240 A361241 A361242

Keyword

nonn,tabl

Author

Andrew Howroyd, Mar 06 2023

Status

approved