A324173 -id:A324173 - cp's OEIS frontend

A326336 Number of set partitions of {1..n} whose capturing blocks are connected.

1, 1, 1, 1, 2, 7, 24, 100, 458, 2279, 12270

Offset: 0

Gus Wiseman, Jun 28 2019

Two blocks are capturing if they are of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. A set partition has its capturing blocks connected if the graph whose vertices are the blocks and whose edges are capturing pairs of blocks is connected.

			The a(0) = 1 through a(6) = 24 set partitions:
  {}  {1}  {12}  {123}  {1234}    {12345}    {123456}
                        {14}{23}  {125}{34}  {1236}{45}
                                  {134}{25}  {1245}{36}
                                  {135}{24}  {1246}{35}
                                  {14}{235}  {125}{346}
                                  {145}{23}  {1256}{34}
                                  {15}{234}  {126}{345}
                                             {134}{256}
                                             {1345}{26}
                                             {1346}{25}
                                             {135}{246}
                                             {1356}{24}
                                             {136}{245}
                                             {14}{2356}
                                             {145}{236}
                                             {1456}{23}
                                             {146}{235}
                                             {15}{2346}
                                             {156}{234}
                                             {16}{2345}
                                             {15}{26}{34}
                                             {16}{23}{45}
                                             {16}{24}{35}
                                             {16}{25}{34}

Simple graphs whose capturing blocks are connected are A326330.
Set partitions whose crossing blocks are connected are A099947.
Set partitions whose nesting blocks are connected are A326335.
Cf. A000110, A001519, A016098, A122880, A324173, A326243, A326248, A326293, A326331, A326337.

capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
captcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],capXQ]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[captcmpts[#]]<=1&]],{n,0,6}]

A268815 Number of purely crossing + partitions of [n].

Original entry on oeis.org

1, 1, 0, 0, 1, 1, 5, 19, 76, 360, 1792, 9634, 55286, 336396, 2162554, 14629720, 103818489, 770678553, 5969822993, 48148947503, 403545713463, 3508356996105, 31587389832791, 294087418038113, 2827471212909189, 28037001032306431, 286398141349873925, 3010540174760962975

Offset: 0

Michel Marcus, Feb 14 2016

nonn

For the definition of these special purely crossing partitions refer to Dykema link (see PC+(n) Definition 2.1 and Table 2).
From Gus Wiseman, Feb 23 2019: (Start)
a(n) is the number of topologically connected (A099947) set partitions of {1,...,n} with no successive elements in the same block. For example, the a(4) = 1 through a(7) = 19 set partitions are:
  {{13}{24}}  {{135}{24}}  {{135}{246}}    {{1357}{246}}
                           {{13}{25}{46}}  {{13}{246}{57}}
                           {{14}{25}{36}}  {{13}{257}{46}}
                           {{14}{26}{35}}  {{135}{26}{47}}
                           {{15}{24}{36}}  {{135}{27}{46}}
                                           {{136}{24}{57}}
                                           {{136}{25}{47}}
                                           {{137}{25}{46}}
                                           {{14}{257}{36}}
                                           {{14}{26}{357}}
                                           {{146}{25}{37}}
                                           {{146}{27}{35}}
                                           {{147}{25}{36}}
                                           {{147}{26}{35}}
                                           {{15}{246}{37}}
                                           {{15}{247}{36}}
                                           {{157}{24}{36}}
                                           {{16}{24}{357}}
                                           {{16}{247}{35}}
(End)

			G.f.: A(x) = 1 + x + x^4 + x^5 + 5*x^6 + 19*x^7 + 76*x^8 + 360*x^9 + 1792*x^10 +...

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

Cf. A000108, A000110, A005493, A016098, A099947, A268814, A306417, A324011, A324166, A324173, A324324, A324327.

n = 30; F = x*Sum[BellB[k] x^k, {k, 0, n}] + O[x]^n; B = ComposeSeries[1/( InverseSeries[F, w] /w)-1, x/(1+x) + O[x]^n]; CoefficientList[B, x] // Rest (* Jean-François Alcover, Feb 16 2016, adapted from K. J. Dykema's code *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
intvQ[set_]:=Or[set=={},Sort[set]==Range[Min@@set,Max@@set]];
Table[Length[Select[sps[Range[n]],And[!MatchQ[#,{_,{_,x_,y_,_},_}/;x+1==y],#=={}||And@@Not/@intvQ/@Union@@@Subsets[#,{1,Length[#]-1}]]&]],{n,0,10}] (* Gus Wiseman, Feb 23 2019 *)

lista(nn) = {c = x/serreverse(x*serlaplace(exp(exp(x+x*O(x^nn)) -1))); b = subst(c, x, x/(1+x) + O(x^nn)); Vec(b);}

{a(n) = my(A=1+x); for(i=1, n, A = sum(m=0, n, x^m/prod(k=1, m, (1+x)*A - k*x +x*O(x^n)) )); polcoeff(A, n)}
for(n=0,25,print1(a(n),", ")) \\ Paul D. Hanna, Mar 07 2016

{Stirling2(n, k) = n!*polcoeff(((exp(x+x*O(x^n)) - 1)^k)/k!, n)}
{Bell(n) = sum(k=0,n, Stirling2(n, k) )}
{a(n) = my(A=1+x); for(i=1, n, A = sum(m=0, n, Bell(m)*x^m/((1+x)*A +x*O(x^n))^m) ); polcoeff(A, n)}
for(n=0,25,print1(a(n),", ")) \\ Paul D. Hanna, Mar 07 2016

G.f.: G(x) satisfies C(x) = G(x/1-x) where C(x) is the g.f. of A099947 (see B(x) in Dykema link p. 7).
From Paul D. Hanna, Mar 07 2016: (Start)
O.g.f. A(x) satisfies
(1) A(x) = Sum_{n>=0} A000110(n)*x^n/((1+x)^n*A(x)^n), where A000110 are the Bell numbers.
(2) A(x) = Sum_{n>=0} x^n / Product_{k=1..n} ((1+x)*A(x) - k*x).
(3) A(x) = 1/(1 - x/((1+x)*A(x) - 1*x/(1 - x/((1+x)*A(x) - 2*x/(1 - x/((1+x)*A(x) - 3*x/(1 - x/((1+x)*A(x) - 4*x/(1 - x/((1+x)*A(x) - ... )))))))))), a continued fraction. (End)

cp's OEIS Frontend

A326336 Number of set partitions of {1..n} whose capturing blocks are connected.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A268815 Number of purely crossing + partitions of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula