login
Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation composed of n blocks of size k.
15

%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