login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 13
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

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: A332649 A321724 A303929 * A194673 A240595 A083671

Adjacent sequences:  A303691 A303692 A303693 * A303695 A303696 A303697

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:44 EDT 2020. Contains 333073 sequences. (Running on oeis4.)