cp's OEIS Frontend

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

%I A303912 #25 Dec 01 2024 19:56:09
%S A303912 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 A303912 44,57,28,1,1,1,7,21,85,197,258,63,1,1,1,8,28,146,510,1228,1110,190,1,
%U A303912 1,1,9,36,231,1101,4051,7692,5475,546,1,1,1,10,45,344,2100,10632,33130,52828,27429,1708,1
%N A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons.
%C A303912 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 A303912 Andrew Howroyd, <a href="/A303912/b303912.txt">Table of n, a(n) for n = 0..1274</a>
%H A303912 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 A303912 Wikipedia, <a href="https://en.wikipedia.org/wiki/Cactus_graph">Cactus graph</a>
%H A303912 <a href="/index/Ca#cacti">Index entries for sequences related to cacti</a>
%F A303912 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 A303912 T(n,k) ~ A070914(n,k-1)/n for fixed k > 1.
%e A303912 Array begins:
%e A303912 ===============================================================
%e A303912 n\k| 1   2     3      4       5        6        7         8
%e A303912 ---+-----------------------------------------------------------
%e A303912 0  | 1   1     1      1       1        1        1         1 ...
%e A303912 1  | 1   1     1      1       1        1        1         1 ...
%e A303912 2  | 1   2     3      4       5        6        7         8 ...
%e A303912 3  | 1   3     6     10      15       21       28        36 ...
%e A303912 4  | 1   6    19     44      85      146      231       344 ...
%e A303912 5  | 1  10    57    197     510     1101     2100      3662 ...
%e A303912 6  | 1  28   258   1228    4051    10632    23884     47944 ...
%e A303912 7  | 1  63  1110   7692   33130   107062   285390    662628 ...
%e A303912 8  | 1 190  5475  52828  291925  1151802  3626295   9711032 ...
%e A303912 9  | 1 546 27429 373636 2661255 12845442 47813815 147766089 ...
%e A303912 ...
%t A303912 T[0, _] = 1;
%t A303912 T[n_, k_] := DivisorSum[n, EulerPhi[n/#] Binomial[k #, #]&]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
%t A303912 Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, May 22 2018 *)
%o A303912 (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 A303912 Columns 2..7 are A054357, A052393, A052394, A054363, A054366, A054369.
%Y A303912 Cf. A070914, A303694, A303913.
%K A303912 nonn,tabl
%O A303912 0,9
%A A303912 _Andrew Howroyd_, May 02 2018