OFFSET
0,14
COMMENTS
Also, the number of unlabeled planar k-gonal cacti having n polygons.
The number of noncrossing partitions counted distinctly is given by A070914(n,k-1).
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], Apr 1998.
Wikipedia, Cactus graph
Wikipedia, Noncrossing partition
FORMULA
T(n,k) = ((Sum_{d|n} phi(n/d)*binomial(k*d,d)) + (Sum_{d|gcd(n-1,k)} phi(d) * binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n,n)/(n*(k-1)+1) for n > 0.
T(n,k) ~ A070914(n,k-1)/(n*k) for fixed k > 1.
EXAMPLE
Array begins:
==================================================================
n\k| 1 2 3 4 5 6 7 8 9
---+--------------------------------------------------------------
0 | 1 1 1 1 1 1 1 1 1 ...
1 | 1 1 1 1 1 1 1 1 1 ...
2 | 1 1 1 1 1 1 1 1 1 ...
3 | 1 2 2 3 3 4 4 5 5 ...
4 | 1 3 7 11 17 25 33 43 55 ...
5 | 1 6 19 52 102 187 300 463 663 ...
6 | 1 14 86 307 811 1772 3412 5993 9821 ...
7 | 1 34 372 1936 6626 17880 40770 82887 154079 ...
8 | 1 95 1825 13207 58385 191967 518043 1213879 2558305 ...
9 | 1 280 9143 93496 532251 2141232 6830545 18471584 44121134 ...
...
MATHEMATICA
T[0, _] = 1;
T[n_, k_] := (DivisorSum[n, EulerPhi[n/#] Binomial[k #, #]&] + DivisorSum[ GCD[n-1, k], EulerPhi[#] Binomial[n k/#, (n-1)/#]&])/(k n) - Binomial[k n, n]/(n (k-1) + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)
PROG
(PARI) T(n, k)={if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(k*d, d)) + sumdiv(gcd(n-1, k), d, eulerphi(d)*binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n, n)/(n*(k-1)+1))}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Apr 28 2018
STATUS
approved