A111275 -id:A111275 - cp's OEIS frontend

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

1, 1, 2, 3, 6, 10, 28, 63, 190, 546, 1708, 5346, 17428, 57148, 191280, 646363, 2210670, 7626166, 26538292, 93013854, 328215300, 1165060668, 4158330416, 14915635378, 53746119972, 194477856100, 706437056648, 2575316704200, 9419571138368

Offset: 0

Simon Plouffe

nonn

a(n) = the number of inequivalent non-crossing partitions of n points (equally spaced) on a circle, under rotations of the circle. This may be considered the number of non-crossing partitions of n unlabeled points on a circle, so this sequence has the same relation to the Catalan numbers (A000108) as the number of partitions of an integer (A000041) has to the Bell numbers (A000110). - Len Smiley, Sep 06 2005

Indranil Ghosh, Table of n, a(n) for n = 0..1000
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Tilman Piesk, Partition related number triangles
Index entries for sequences related to cacti

Column k=2 of A303912.
Row sums of A209805.
Cf. A002995, A054358, A111275.

a[n_] := If[n == 0, 1, (Binomial[2*n, n]/(n + 1) + DivisorSum[n, Binomial[2*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jul 17 2017 *)

a(n)=if(n==0, 1, (binomial(2*n, n)/(n + 1) + sumdiv(n, d, binomial(2*d, d)*eulerphi(n/d)*(dIndranil Ghosh, Jul 17 2017

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/n - binomial(2*n, n)/(n+1)) \\ Andrew Howroyd, May 02 2018

from sympy import binomial, divisors, totient
def a(n): return 1 if n==0 else (binomial(2*n, n)//(n + 1) + sum(binomial(2*d, d)*totient(n//d)*(dIndranil Ghosh, Jul 17 2017

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

a(n) ~ 2^(2*n) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Len Smiley, Sep 06 2005

More terms from Vladeta Jovovic, Oct 04 2007

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.

Original entry on oeis.org

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

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 12, 17, 12, 3, 1, 1, 4, 19, 41, 41, 19, 4, 1, 1, 4, 27, 78, 116, 78, 27, 4, 1, 1, 5, 38, 148, 298, 298, 148, 38, 5, 1, 1, 5, 50, 250, 680, 932, 680, 250, 50, 5, 1

Offset: 1

Tilman Piesk, Mar 10 2012

Like the Narayana triangle A001263 (and unlike A152176) this triangle is symmetric.

			Triangle begins:
1;
1,  1;
1,  1,  1;
1,  2,  2,  1;
1,  2,  4,  2,  1;
1,  3,  8,  8,  3,  1;
1,  3, 12, 17, 12,  3,  1;
1,  4, 19, 41, 41, 19,  4,  1;
1,  4, 27, 78,116, 78, 27,  4,  1;
1,  5, 38,148,298,298,148, 38,  5,  1

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Tilman Piesk, Partition related number triangles

Cf. A111275 (row sums)

Cf. A088855, A209805.

b[n_, k_] := Binomial[n - 1, n - k]*Binomial[n, n - k];
T[n_, k_] := (n*Binomial[Quotient[n - 1, 2], Quotient[k - 1, 2]]*Binomial[ Quotient[n, 2], Quotient[k, 2]] + DivisorSum[GCD[n, k], EulerPhi[#]* b[n/#, k/#]&] + DivisorSum[GCD[n, k - 1], EulerPhi[#]*b[n/#, (n + 1 - k)/#]&] - k*Binomial[n, k]^2/(n - k + 1))/(2*n);
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 30 2018, after Andrew Howroyd *)

b(n,k)=binomial(n-1,n-k)*binomial(n,n-k);
T(n,k)=(n*binomial((n-1)\2, (k-1)\2)*binomial(n\2, k\2) + sumdiv(gcd(n,k), d, eulerphi(d)*b(n/d,k/d)) + sumdiv(gcd(n,k-1), d, eulerphi(d)*b(n/d,(n+1-k)/d)) - k*binomial(n,k)^2/(n-k+1))/(2*n); \\ Andrew Howroyd, Nov 15 2017

T(n,k) = (A088855(n,k) + A209805(n,k))/2. - Andrew Howroyd, Nov 15 2017

A211359 Triangle read by rows: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that contain k singleton blocks.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 0, 1, 2, 3, 2, 2, 0, 1, 5, 4, 8, 3, 3, 0, 1, 6, 11, 12, 12, 4, 3, 0, 1, 14, 21, 39, 24, 22, 5, 4, 0, 1, 22, 55, 84, 85, 48, 30, 7, 4, 0, 1, 51, 124, 245, 228, 190, 82, 46, 8, 5, 0, 1, 95, 327, 620, 730, 570, 350, 136, 60

Offset: 0

Tilman Piesk, Apr 12 2012

			From _Andrew Howroyd_, May 02 2018: (Start)
Triangle begins:
   1;
   0,   1;
   1,   0,   1;
   1,   1,   0,   1;
   2,   1,   2,   0,   1;
   2,   3,   2,   2,   0,  1;
   5,   4,   8,   3,   3,  0,  1;
   6,  11,  12,  12,   4,  3,  0, 1;
  14,  21,  39,  24,  22,  5,  4, 0, 1;
  22,  55,  84,  85,  48, 30,  7, 4, 0, 1;
  51, 124, 245, 228, 190, 82, 46, 8, 5, 0, 1;
  ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..1274 (terms 0..90 from Tilman Piesk)

Column k=0 is A303931.
Row sums are A111275.
Cf. A209612, A211357, A303875.

\\ See A303875 for NCPartitionsModDihedral
{ my(rows=Vec(NCPartitionsModDihedral(vector(10, k, if(k==1,y,1)))));
for(n=1, #rows, for(k=0, n-1, print1(polcoeff(rows[n], k), ", ")); print; ) } \\ Andrew Howroyd, May 02 2018

A303875 Number of noncrossing partitions of an n-set up to rotation and reflection with all blocks having a prime number of elements.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 3, 5, 7, 14, 26, 49, 107, 215, 502, 1112, 2619, 6220, 14807, 36396, 88397, 219920, 545196, 1364669, 3434436, 8658463, 21989434, 55893852, 142823174, 365766327, 939575265, 2420885031, 6250344302, 16183450744, 41981605437, 109155492638

Offset: 0

Andrew Howroyd, May 01 2018

nonn

The number of such noncrossing partitions counted distinctly is given by A210737.

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

Cf. A111275, A185100 (1 or 2), A210737, A303874, A303931.

\\ number of partitions with restricted block sizes
NCPartitionsModDihedral(v)={ my(n=#v);
my(p=serreverse( x/(1 + sum(k=1, #v, x^k*v[k])) + O(x^2*x^n) )/x);
my(vars=variables(p));
my(varpow(r,d)=substvec(r + O(x^(n\d+1)), vars, apply(t->t^d, vars)));
my(q=x*deriv(p)/p, h=varpow(p,2));
my(R=sum(i=0, (#v-1)\2, v[2*i+1]*x*(x^2*h)^i), Q=sum(i=1, #v\2, v[2*i]*(x^2*h)^i), T=sum(k=1, #v, my(t=v[k]); if(t, x^k*t*sumdiv(k, d, eulerphi(d) * varpow(p,d)^(k/d))/k)));
(T + 2 + intformal(sum(d=1, n, eulerphi(d)*varpow(q,d))/x) - p + (1 + Q + (1+R)^2*h/(1-Q))/2)/2 + O(x*x^n)
}
Vec(NCPartitionsModDihedral(vector(40,k,isprime(k))))

A111276 Number of chiral non-crossing partition patterns of n points on a circle, divided by 2.

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 14, 60, 210, 728, 2442, 8252, 27716, 93924, 319964, 1098900, 3800928, 13244836, 46460738, 164015272, 582353976, 2078812492, 7457141650, 26871707908, 97236327900, 353213328024, 1287648322950, 4709765510884, 17279999438748, 63583033400968

Offset: 1

David Callan and Len Smiley, Oct 21 2005

nonn

Half of the number of those rotation-inequivalent patterns of non-crossing partitions of n (equally spaced) points on a circle which are not invariant under reflections. Division by two counts one pattern from each chiral (Right-handed,Left-handed) pair.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
D. Callan and L. Smiley, Non-crossing Partitions under Rotation and Reflection, arXiv:math/0510447 [math.CO], 2005.
L. Smiley, a(5) = 0
L. Smiley, a(6)=8/2=4

Cf. A001405, A054357, A111275.

a[n_] := If[n < 6, 0, ((Binomial[2n, n]/(n+1) + DivisorSum[n, Binomial[2#, #] EulerPhi[n/#] Boole[# < n]&])/n - Binomial[n, Floor[n/2]])/2];
Array[a, 22] (* Jean-François Alcover, Feb 17 2019 *)

a(n) = (sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/n - binomial(2*n, n)/(n+1) - binomial(n,n\2))/2 \\ Andrew Howroyd, Nov 19 2024

a(n) = (A054357(n) - A001405(n))/2.

a(23) onwards from Andrew Howroyd, Nov 19 2024

A211355 Refined triangle A211359: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 3, 1, 2, 1, 1, 1, 1, 3, 4, 8, 4, 9, 3, 4, 4, 2, 1, 3, 1, 1, 1, 1, 4, 5, 14, 8, 19, 5, 14, 13, 8, 4, 12, 4, 4, 1, 3, 4, 3, 1, 1, 1, 1, 1, 4, 7, 20, 10, 38, 10, 30, 32, 16, 7, 48

Offset: 1

Tilman Piesk, Apr 09 2012

The rows are counted from 1, the columns from 0.
Row lengths: 1,2,3,5,7,11... (partition numbers A000041)
Row sums: 1,2,3,6,10,24... (A111275)
Row maxima: 1,1,1,2,2,5,9,19,48,132,330,781
Distinct entries per row: 1,1,1,2,2,4,6,9,15,21,28,43
Rightmost columns are those from the triangle A052307  without the second column.

Tilman Piesk, Rows n=1..12 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A211359, A000041, A111275, A052307.

A111274 Erroneous enumeration of "congruent and symmetric divisions" of n points on a circle.

Original entry on oeis.org

1, 2, 3, 6, 9, 24

Offset: 1

dead

Motzkin, T. "Relations Between Hypersurface Cross Ratios and a Combinatorial Formula for Partitions of a Polygon for Permanent Preponderance and for Non-Associative Products." Bull. Amer. Math. Soc. 54, page 360, 1948.

L. Smiley, a(5)

See A111275 for the correct enumeration.

a(5)=9 is clearly a clerical error.

cp's OEIS Frontend

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

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

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A211359 Triangle read by rows: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that contain k singleton blocks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A303875 Number of noncrossing partitions of an n-set up to rotation and reflection with all blocks having a prime number of elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A111276 Number of chiral non-crossing partition patterns of n points on a circle, divided by 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A211355 Refined triangle A211359: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A111274 Erroneous enumeration of "congruent and symmetric divisions" of n points on a circle.

Views

Author

Keywords

References

Links