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

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, 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, 187, 811, 1936, 1825, 280, 1, 1, 1, 1, 5, 43, 300, 1772, 6626, 13207, 9143, 854, 1

Offset

0,14

Comments

Also, the number of unlabeled planar k-gonal cacti having n polygons.

The number of noncrossing partitions counted distinctly is given by A070914(n,k-1).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], Apr 1998.

Wikipedia, Cactus graph

Wikipedia, Noncrossing partition

Index entries for sequences related to cacti

Formula

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.

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

Example

Array begins:
==================================================================
n\k| 1   2    3     4      5       6       7        8        9
---+--------------------------------------------------------------
0  | 1   1    1     1      1       1       1        1        1 ...
1  | 1   1    1     1      1       1       1        1        1 ...
2  | 1   1    1     1      1       1       1        1        1 ...
3  | 1   2    2     3      3       4       4        5        5 ...
4  | 1   3    7    11     17      25      33       43       55 ...
5  | 1   6   19    52    102     187     300      463      663 ...
6  | 1  14   86   307    811    1772    3412     5993     9821 ...
7  | 1  34  372  1936   6626   17880   40770    82887   154079 ...
8  | 1  95 1825 13207  58385  191967  518043  1213879  2558305 ...
9  | 1 280 9143 93496 532251 2141232 6830545 18471584 44121134 ...
...

Mathematica

T[0, _] = 1;
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);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

Prog

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

Crossrefs

Columns 2..7 are A002995(n+1), A054423, A054362, A054365, A054368, A054371.

Cf. A070914, A209805, A303864, A303929.

Sequence in context: A333737 A333733 A303929 * A194673 A240595 A083671

Adjacent sequences: A303691 A303692 A303693 * A303695 A303696 A303697

Keyword

nonn,tabl

Author

Andrew Howroyd, Apr 28 2018

Status

approved