A303913 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.

1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 0, 1, 1, 0, 6, 10, 8, 0, 1, 1, 0, 10, 28, 54, 18, 0, 1, 1, 0, 15, 60, 193, 222, 61, 0, 1, 1, 0, 21, 110, 505, 1140, 1107, 170, 0, 1, 1, 0, 28, 182, 1095, 3876, 7688, 5346, 538, 0, 1, 1, 0, 36, 280, 2093, 10326, 33125, 52364, 27399, 1654, 0

Offset: 0

Author

Andrew Howroyd, May 02 2018

Keywords

• nonn
• tabl

Comments

A k-ary cactus is a planar k-gonal cactus with vertices on each polygon numbered 1..k counterclockwise with shared vertices having the same number. In total there are always exactly k ways to number a given cactus since all polygons are connected. See the reference for a precise definition. - Andrew Howroyd, Feb 18 2020

Examples

			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  | 0   0     0      0       0        0        0         0 ...
3  | 0   1     3      6      10       15       21        28 ...
4  | 0   2    10     28      60      110      182       280 ...
5  | 0   8    54    193     505     1095     2093      3654 ...
6  | 0  18   222   1140    3876    10326    23394     47208 ...
7  | 0  61  1107   7688   33125   107056   285383    662620 ...
8  | 0 170  5346  52364  290700  1149126  3621150   9702008 ...
9  | 0 538 27399 373560 2661100 12845166 47813367 147765409 ...
...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1274
• Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.
• Wikipedia, Cactus graph
• Index entries for sequences related to cacti

Crossrefs

Columns k=2..7 are A054358, A054422, A052395, A054364, A054367, A054370.

Cf. A303694, A303912.

Programs

Mathematica

T[0, _] = 1;
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] Binomial[k #, #] &]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

PARI

T(n,k)={if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

Formula

T(n,k) = (Sum_{d|n} mu(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1) for n > 0.