A303871 -id:A303871 - cp's OEIS frontend

A303929 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation and reflection 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, 5, 6, 1, 1, 1, 1, 3, 8, 13, 12, 1, 1, 1, 1, 4, 11, 34, 49, 27, 1, 1, 1, 1, 4, 16, 60, 169, 201, 65, 1, 1, 1, 1, 5, 20, 109, 423, 1019, 940, 175, 1, 1, 1, 1, 5, 26, 167, 918, 3381, 6710, 4643, 490, 1

Offset: 0

Andrew Howroyd, May 02 2018

			=================================================================
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    5     8     11      16      20      26       32 ...
5  | 1   6   13    34     60     109     167     257      359 ...
6  | 1  12   49   169    423     918    1741    3051     4969 ...
7  | 1  27  201  1019   3381    9088   20569   41769    77427 ...
8  | 1  65  940  6710  29335   96315  259431  607696  1280045 ...
9  | 1 175 4643 47104 266703 1072187 3417520 9240444 22066742 ...
...

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

Columns 2..5 are A006082(n+1), A082938, A303870, A303871.

Cf. A111275, A209612, A211359, A303694, A303875.

u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
c[n_, k_] := If[n == 0, 1, (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[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0;
Table[T[n - k, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 14 2018, translated from PARI *)

\\ here c(n,k) is A303694
u(n,k,r) = {r*binomial(k*n + r, n)/(k*n + r)}
e(n,k) = {sum(j=0, n\2, u(j, k, 1+(n-2*j)*k/2))}
c(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))}
T(n,k)={(1/2)*(c(n,k) + if(n==0, 1, if(k%2, if(n%2, 2*u(n\2,k,(k+1)/2), u(n/2,k,1) + u(n/2-1,k,k)), e(n,k) + if(n%2, u(n\2,k,k/2)))/2))}

A054365 Number of unlabeled 5-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 3, 17, 102, 811, 6626, 58385, 532251, 5011934, 48344880, 475982471, 4766639628, 48434621610, 498363430232, 5184274255789, 54451326151253, 576810990484823, 6156943228387305, 66170786572330174, 715564777086617766

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 5. - Andrew Howroyd, May 04 2018

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Luke Lippstreu, Jorge Mago, Marcus Spradlin, and Anastasia Volovich, Weak Separation, Positivity and Extremal Yangian Invariants, arXiv:1906.11034 [hep-th], 2019.
Index entries for sequences related to cacti

Column k=5 of A303694.

Cf. A054363, A054364, A303871.

with(combinat): with(numtheory): m := 5: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od: # Zerinvary Lajos, Dec 01 2006

a[0] = 1;
a[n_] := (DivisorSum[n, EulerPhi[n/#] Binomial[5#, #]&] + DivisorSum[GCD[n - 1, 5], EulerPhi[#] Binomial[5n/#, (n-1)/#]&])/(5n) - Binomial[5n, n]/ (4n+1);
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 01 2018, after Andrew Howroyd *)

a(n) = {if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(5*d, d)) + sumdiv(gcd(n-1, 5), d, eulerphi(d)*binomial(5*n/d, (n-1)/d)))/(5*n) - binomial(5*n, n)/(4*n+1))} \\ Andrew Howroyd, May 04 2018

a(n) = ((Sum_{d|n} phi(n/d)*binomial(5*d, d)) + (Sum_{d|gcd(n-1, 5)} phi(d)*binomial(5*n/d, (n-1)/d)))/(5*n) - binomial(5*n, n)/(4*n+1) for n > 0. - Andrew Howroyd, May 04 2018

More terms from Zerinvary Lajos, Dec 01 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A054365 Number of unlabeled 5-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions