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
Examples
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 ... ...
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
Crossrefs
Programs
-
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 *) -
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))}
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.
Comments