|
%I #18 Feb 18 2020 19:22:21
%S 1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,3,1,1,1,1,3,7,6,1,1,1,1,3,11,
%T 19,14,1,1,1,1,4,17,52,86,34,1,1,1,1,4,25,102,307,372,95,1,1,1,1,5,33,
%U 187,811,1936,1825,280,1,1,1,1,5,43,300,1772,6626,13207,9143,854,1
%N Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation composed of n blocks of size k.
%C Also, the number of unlabeled planar k-gonal cacti having n polygons.
%C The number of noncrossing partitions counted distinctly is given by A070914(n,k-1).
%H Andrew Howroyd, <a href="/A303694/b303694.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], Apr 1998.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cactus_graph">Cactus graph</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Noncrossing_partition">Noncrossing partition</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)) + (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.
%F T(n,k) ~ A070914(n,k-1)/(n*k) for fixed k > 1.
%e Array begins:
%e ==================================================================
%e n\k| 1 2 3 4 5 6 7 8 9
%e ---+--------------------------------------------------------------
%e 0 | 1 1 1 1 1 1 1 1 1 ...
%e 1 | 1 1 1 1 1 1 1 1 1 ...
%e 2 | 1 1 1 1 1 1 1 1 1 ...
%e 3 | 1 2 2 3 3 4 4 5 5 ...
%e 4 | 1 3 7 11 17 25 33 43 55 ...
%e 5 | 1 6 19 52 102 187 300 463 663 ...
%e 6 | 1 14 86 307 811 1772 3412 5993 9821 ...
%e 7 | 1 34 372 1936 6626 17880 40770 82887 154079 ...
%e 8 | 1 95 1825 13207 58385 191967 518043 1213879 2558305 ...
%e 9 | 1 280 9143 93496 532251 2141232 6830545 18471584 44121134 ...
%e ...
%t T[0, _] = 1;
%t 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);
%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)) + 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))}
%Y Columns 2..7 are A002995(n+1), A054423, A054362, A054365, A054368, A054371.
%Y Cf. A070914, A209805, A303864, A303929.
%K nonn,tabl
%O 0,14
%A _Andrew Howroyd_, Apr 28 2018
|
