|
|
A303913
|
|
Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.
|
|
8
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,19
|
|
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
|
|
LINKS
|
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.
|
|
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.
|
|
EXAMPLE
|
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 ...
...
|
|
MATHEMATICA
|
T[0, _] = 1;
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] Binomial[k #, #] &]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
|
|
PROG
|
(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))}
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|