login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A303694 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation composed of n blocks of size k. 15
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 (list; table; graph; refs; listen; history; text; internal format)
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
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], Apr 1998.
Wikipedia, Cactus graph
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.
Sequence in context: A333737 A333733 A303929 * A194673 A240595 A083671
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Apr 28 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:13 EDT 2024. Contains 371254 sequences. (Running on oeis4.)