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

%I #16 Feb 18 2020 19:22:59

%S 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,

%T 54,18,0,1,1,0,15,60,193,222,61,0,1,1,0,21,110,505,1140,1107,170,0,1,

%U 1,0,28,182,1095,3876,7688,5346,538,0,1,1,0,36,280,2093,10326,33125,52364,27399,1654,0

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

%C 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

%H Andrew Howroyd, <a href="/A303913/b303913.txt">Table of n, a(n) for n = 0..1274</a>

%H Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, <a href="https://arxiv.org/abs/math/9804119">Enumeration of m-ary cacti</a>, arXiv:math/9804119 [math.CO], 1998-1999.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cactus_graph">Cactus graph</a>

%H <a href="/index/Ca#cacti">Index entries for sequences related to cacti</a>

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

%e Array begins:

%e ===============================================================

%e n\k| 1 2 3 4 5 6 7 8

%e ---+-----------------------------------------------------------

%e 0 | 1 1 1 1 1 1 1 1 ...

%e 1 | 1 1 1 1 1 1 1 1 ...

%e 2 | 0 0 0 0 0 0 0 0 ...

%e 3 | 0 1 3 6 10 15 21 28 ...

%e 4 | 0 2 10 28 60 110 182 280 ...

%e 5 | 0 8 54 193 505 1095 2093 3654 ...

%e 6 | 0 18 222 1140 3876 10326 23394 47208 ...

%e 7 | 0 61 1107 7688 33125 107056 285383 662620 ...

%e 8 | 0 170 5346 52364 290700 1149126 3621150 9702008 ...

%e 9 | 0 538 27399 373560 2661100 12845166 47813367 147765409 ...

%e ...

%t T[0, _] = 1;

%t T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] Binomial[k #, #] &]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);

%t Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, May 22 2018 *)

%o (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))}

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

%Y Cf. A303694, A303912.

%K nonn,tabl

%O 0,19

%A _Andrew Howroyd_, May 02 2018