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

%I #22 Feb 18 2020 19:22:37

%S 1,1,1,1,1,1,1,1,2,1,1,1,3,3,1,1,1,4,6,6,1,1,1,5,10,19,10,1,1,1,6,15,

%T 44,57,28,1,1,1,7,21,85,197,258,63,1,1,1,8,28,146,510,1228,1110,190,1,

%U 1,1,9,36,231,1101,4051,7692,5475,546,1,1,1,10,45,344,2100,10632,33130,52828,27429,1708,1

%N Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled 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.

%H Andrew Howroyd, <a href="/A303912/b303912.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} phi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1)) for n > 0.

%F T(n,k) ~ A070914(n,k-1)/n for fixed k > 1.

%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 | 1 2 3 4 5 6 7 8 ...

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

%e 4 | 1 6 19 44 85 146 231 344 ...

%e 5 | 1 10 57 197 510 1101 2100 3662 ...

%e 6 | 1 28 258 1228 4051 10632 23884 47944 ...

%e 7 | 1 63 1110 7692 33130 107062 285390 662628 ...

%e 8 | 1 190 5475 52828 291925 1151802 3626295 9711032 ...

%e 9 | 1 546 27429 373636 2661255 12845442 47813815 147766089 ...

%e ...

%t T[0, _] = 1;

%t T[n_, k_] := DivisorSum[n, EulerPhi[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, eulerphi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

%Y Columns 2..7 are A054357, A052393, A052394, A054363, A054366, A054369.

%Y Cf. A070914, A303694, A303913.

%K nonn,tabl

%O 0,9

%A _Andrew Howroyd_, May 02 2018