A306418 -id:A306418 - cp's OEIS frontend

A324166 Number of totally crossing set partitions of {1,...,n}.

1, 1, 1, 1, 2, 6, 18, 57, 207, 842, 3673, 17062, 84897

Offset: 0

Gus Wiseman, Feb 17 2019

A set partition is totally crossing if every pair of distinct blocks is of the form {{...x...y...}, {...z...t...}} for some x < z < y < t or z < x < t < y.

			The a(6) = 18 totally crossing set partitions:
  {{1,2,3,4,5,6}}
  {{1,4,6},{2,3,5}}
  {{1,4,5},{2,3,6}}
  {{1,3,6},{2,4,5}}
  {{1,3,5},{2,4,6}}
  {{1,3,4},{2,5,6}}
  {{1,2,5},{3,4,6}}
  {{1,2,4},{3,5,6}}
  {{4,6},{1,2,3,5}}
  {{3,6},{1,2,4,5}}
  {{3,5},{1,2,4,6}}
  {{2,6},{1,3,4,5}}
  {{2,5},{1,3,4,6}}
  {{2,4},{1,3,5,6}}
  {{1,5},{2,3,4,6}}
  {{1,4},{2,3,5,6}}
  {{1,3},{2,4,5,6}}
  {{1,4},{2,5},{3,6}}

Cf. A000108 (non-crossing partitions), A000110, A000296, A002662, A016098 (crossing partitions), A054726, A099947 (topologically connected partitions), A305854, A306006, A306418, A306438, A319752.

Cf. A324170, A324171, A324172, A324173.

nn=6;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

Original entry on oeis.org

1, 2, 2, 4, 2, 10, 2, 20, 14, 49, 2, 217, 2, 438, 310, 1580, 2, 6352, 2, 18062, 7824, 58799, 2, 258971, 2532, 742915, 246794, 2729095, 2, 11154954, 2, 35779660, 8414818, 129644809, 242354, 531132915, 2, 1767263211, 300830821, 6593815523, 2, 26289925026, 2, 91708135773

Offset: 1

Paul D. Hanna, Aug 28 2011

nonn

Number of Dyck n-paths with all ascents of equal length. - David Scambler, Nov 17 2011
From Gus Wiseman, Feb 15 2019: (Start)
Also the number of uniform (all blocks have the same size) non-crossing set partitions of {1,...,n}. For example, the a(3) = 2 through a(6) = 10 uniform non-crossing set partitions are:
  {{123}}      {{1234}}        {{12345}}          {{123456}}
  {{1}{2}{3}}  {{12}{34}}      {{1}{2}{3}{4}{5}}  {{123}{456}}
               {{14}{23}}                         {{126}{345}}
               {{1}{2}{3}{4}}                     {{156}{234}}
                                                  {{12}{34}{56}}
                                                  {{12}{36}{45}}
                                                  {{14}{23}{56}}
                                                  {{16}{23}{45}}
                                                  {{16}{25}{34}}
                                                  {{1}{2}{3}{4}{5}{6}}
(End)

			G.f.: A(x) = x + 2*x^2 + 2*x^3 + 4*x^4 + 2*x^5 + 10*x^6 + 2*x^7 + ...
where
A(x) = G_1(x) + G_2(x)^2 + G_3(x)^3 + G_4(x)^4 + G_5(x)^5 + ...
and G_n(x) = x + x*G_n(x)^n is given by:
G_n(x) = Sum_{k>=0} C(n*k+1,k)/(n*k+1)*x^(n*k+1),
G_n(x)^n = Sum_{k>=1} C(n*k,k)/(n*k-k+1)*x^(n*k);
the first few expansions of G_n(x)^n begin:
G_1(x) = x + x^2 + x^3 + x^4 + x^5 + ...
G_2(x)^2 = x^2 + 2*x^4 + 5*x^6 + 14*x^8 + ... + A000108(n)*x^(2*n) + ...
G_3(x)^3 = x^3 + 3*x^6 + 12*x^9 + 55*x^12 + ... + A001764(n)*x^(3*n) + ...
G_4(x)^4 = x^4 + 4*x^8 + 22*x^12 + 140*x^16 + ... + A002293(n)*x^(4*n) + ...
G_5(x)^5 = x^5 + 5*x^10 + 35*x^15 + 285*x^20 + ... + A002294(n)*x^(5*n) + ...

Paul D. Hanna, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Dyck Path.
Wikipedia, Noncrossing partition.

Row sums of A306437.

Cf. A000108, A001263, A001764, A016098, A038041, A061095, A125181, A134264, A194558, A306418, A306438.

Table[Sum[Binomial[n,d]/(n-d+1),{d,Divisors[n]}],{n,20}] (* Gus Wiseman, Feb 15 2019 *)

{a(n)=if(n<1,0,sumdiv(n,d,binomial(n,d)/(n-d+1)))}

{a(n)=polcoeff(sum(m=1,n,serreverse(x/(1+x^m+x*O(x^n)))^m),n)}

a(n) = Sum_{d|n} C(n,d)/(n-d+1).

G.f.: Sum_{n>=1} Series_Reversion( x/(1+x^n) )^n.

cp's OEIS Frontend

A324166 Number of totally crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica