A054357 -id:A054357 - cp's OEIS frontend

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

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 0, 1, 2, 3, 2, 2, 0, 1, 5, 6, 9, 4, 3, 0, 1, 6, 15, 18, 15, 5, 3, 0, 1, 15, 36, 56, 42, 29, 7, 4, 0, 1, 28, 91, 144, 142, 84, 42, 10, 4, 0, 1, 67, 232, 419, 432, 322, 152, 66, 12, 5, 0, 1, 145, 603, 1160, 1365, 1080, 630, 252, 90, 15, 5, 0, 1

Offset: 0

Tilman Piesk, Apr 12 2012

			From _Andrew Howroyd_, Nov 16 2017: (Start)
Triangle begins: (n >= 0, 0 <= k <= n)
   1;
   0,   1;
   1,   0,   1;
   1,   1,   0,   1;
   2,   1,   2,   0,   1;
   2,   3,   2,   2,   0,   1;
   5,   6,   9,   4,   3,   0,  1;
   6,  15,  18,  15,   5,   3,  0,  1;
  15,  36,  56,  42,  29,   7,  4,  0, 1;
  28,  91, 144, 142,  84,  42, 10,  4, 0, 1;
  67, 232, 419, 432, 322, 152, 66, 12, 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 A295198.
Row sums are A054357.
Cf. A091867 (noncrossing partitions of an n-set with k singleton blocks), A211359 (up to rotations and reflections).
Cf. A171128.

a91867[n_, k_] := If[k == n, 1, (Binomial[n + 1, k]/(n + 1)) Sum[Binomial[n + 1 - k, j] Binomial[n - k - j - 1, j - 1], {j, 1, (n - k)/2}]];
a2426[n_] := Sum[Binomial[n, 2*k]*Binomial[2*k, k], {k, 0, Floor[n/2]}];
a171128[n_, k_] := Binomial[n, k]*a2426[n - k];
T[0, 0] = 1;
T[n_, k_] := (1/n)*(a91867[n, k] - a171128[n, k] + Sum[EulerPhi[d]* a171128[n/d, k/d], {d, Divisors[GCD[n, k]]}]);
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 03 2018, after Andrew Howroyd *)

g(x,y) = {1/sqrt((1 - (1 + y)*x)^2 - 4*x^2) - 1}
S(n)={my(A=(1-sqrt(1-4*x/(1-(y-1)*x) + O(x^(n+2))))/(2*x)-1); Vec(1+intformal((A + sum(k=2, n, eulerphi(k)*g(x^k + O(x*x^n), y^k)))/x))}
my(v=S(10)); for(n=1, #v, my(p=v[n]); for(k=0, n-1, print1(polcoeff(p,k), ", ")); print) \\ Andrew Howroyd, Nov 16 2017

T(n,k) = (1/n)*(A091867(n,k) - A171128(n,k) + Sum_{d|gcd(n,k)} phi(d) * A171128(n/d, k/d)) for n > 0. - Andrew Howroyd, Nov 16 2017

A054358 Number of unlabeled asymmetric 2-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 0, 1, 2, 8, 18, 61, 170, 538, 1654, 5344, 17252, 57146, 190786, 646305, 2209050, 7626164, 26532732, 93013852, 328196780, 1165060170, 4158266282, 14915635376, 53745892932, 194477856048, 706436256598, 2575316698792, 9419568272632

Offset: 0

Simon Plouffe

nonn

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.
Index entries for sequences related to cacti

Column k=2 of A303913.

Cf. A002995, A054357.

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

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

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

More terms from Vladeta Jovovic, Oct 04 2007

A085166 A057163-conjugate of A085160.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 5, 8, 9, 14, 16, 10, 19, 17, 18, 11, 12, 15, 20, 21, 13, 22, 23, 37, 42, 24, 51, 44, 47, 25, 26, 38, 53, 56, 27, 60, 45, 46, 48, 49, 50, 28, 29, 30, 31, 40, 39, 43, 32, 52, 54, 55, 57, 58, 59, 33, 34, 35, 41, 61, 62, 63, 36, 64, 65, 107, 121, 66, 149

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085165. a(n) = A057163(A085160(A057163(n))) = A085162(A085165(A085162(n))). Occurs in A073200. Cf. also A085162, A086429, A086430.

Number of cycles: A054357. Number of fixed points: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

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

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 3, 5, 8, 17, 37, 71, 179, 366, 919, 2069, 5027, 12053, 29098, 71846, 175485, 437438, 1087122, 2723326, 6860525, 17301606, 43957596, 111748571, 285591775, 731432424, 1879009622, 4841510973, 12500324496, 32366232373, 83962263464, 218309244314

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. A054357 (unrestricted), A175954 (1 or 2), A210737, A295198, A303875.

\\ number of partitions with restricted block sizes
NCPartitionsModCyclic(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);
my(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
}
Vec(NCPartitionsModCyclic(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

A211353 Refined triangle A211357: T(n,k) is the number of noncrossing partitions up to rotation 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, 4, 6, 3, 5, 1, 2, 1, 1, 1, 1, 3, 5, 10, 5, 15, 3, 5, 6, 3, 1, 3, 1, 1, 1, 1, 4, 7, 19, 10, 35, 7, 19, 21, 12, 4, 21, 7, 7, 1, 3, 4, 4, 1, 1, 1, 1, 1, 4, 10, 28, 14, 70, 14, 48, 56, 28, 10

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,28... (A054357)
Row maxima: 1,1,1,2,2,6,15,35,84,252,630,1542...
Distinct entries per row: 1,1,1,2,2,6,6,9,11,17,17,30...
Rightmost columns are those from the triangle of circular binomial coefficients A047996 without the second column (i.e.triangle A037306).

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

Cf. A211357, A000041, A054357, A047996, A037306.

A135452 Number of different multisets of differences between ends of n non-intersecting chords joining 2n labeled points around a circle.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 33, 71, 117, 242, 421, 877, 1468

Offset: 1

Arvind Ayyer, Dec 14 2007, definition corrected Jan 04 2007, Jan 07 2007

Represent a set of chords as a collection of pairs of integers. For example, if n=3, one possible connectivity is {{1,4},{2,3},{5,6}}.
Define the D-set of a connectivity to be the multiset of differences between connected pairs. In the above example the D-set is {1,1,3}. Since the numbers are on a circle, we can take two possible differences. We take the smaller of the two. Hence the maximal difference can be at most n or n-1 depending on whether n is odd or even. Is another example: the D-set of {{1,6},{2,3},{4,5}} is {1,1,1}.
Then the sequence gives the number of distinct D-sets of all possible connectivities.
While it is true that if two connectivities have different D-sets they are inequivalent, the converse is not true. consider n=6: Both {{4, 5}, {6, 11}, {2, 3}, {8, 9}, {7, 10}, {1, 12}} and {{4, 5}, {1, 6}, {2, 3}, {8, 9}, {7, 10}, {11, 12}} have the same D-set, namely {1,1,1,1,3,5} but they are inequivalent.

Cf. A001008, A054357.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054358 Number of unlabeled asymmetric 2-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A085166 A057163-conjugate of A085160.

Views

Author

Keywords

Links

Crossrefs

A303874 Number of noncrossing partitions of an n-set up to rotation 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

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

Views

Author

Keywords

Comments

Links

Crossrefs

A135452 Number of different multisets of differences between ends of n non-intersecting chords joining 2n labeled points around a circle.

Views

Author

Keywords

Comments

Crossrefs