A326209 -id:A326209 - cp's OEIS frontend

A326210 Number of labeled simple graphs with vertices {1..n} containing a nesting pair of edges, where two edges {a,b}, {c,d} are nesting if a < c and b > d or a > c and b < d.

0, 0, 0, 0, 16, 672, 29888, 2071936, 268204288, 68717285888, 35184350796800, 36028796807919616, 73786976292712960000, 302231454903635611721728, 2475880078570760326175178752, 40564819207303340845566684397568, 1329227995784915872903782635437883392

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

Also simple graphs containing a crossing pair of edges, where two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

Also simple graphs such that, if the edges are listed in lexicographic order, their maxima (seconds) are not weakly increasing.

			The a(4) = 16 nesting edge-sets:
  {14,23}
  {12,14,23}
  {13,14,23}
  {14,23,24}
  {14,23,34}
  {12,13,14,23}
  {12,14,23,24}
  {12,14,23,34}
  {13,14,23,24}
  {13,14,23,34}
  {14,23,24,34}
  {12,13,14,23,24}
  {12,13,14,23,34}
  {12,14,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}
The a(4) = 16 crossing edge-sets:
  {13,24}
  {12,13,24}
  {13,14,24}
  {13,23,24}
  {13,24,34}
  {12,13,14,24}
  {12,13,23,24}
  {12,13,24,34}
  {13,14,23,24}
  {13,14,24,34}
  {13,23,24,34}
  {12,13,14,23,24}
  {12,13,14,24,34}
  {12,13,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}

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

Non-nesting graphs are A054726.
Nesting digraphs are A326209.
Nesting (or crossing) set partitions are A016098.
MM-numbers of nesting multiset partitions are A326256.
Cf. A001519, A006125, A095661, A324170, A324172, A324326.
Cf. A326211, A326243, A326244, A326248, A326250.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!OrderedQ[Last/@#]&]],{n,0,5}]

seq(n)={my(p=1 + 3/2*x - x^2 - x/2*sqrt(1 - 12*x + 4*x^2 + O(x^n))); concat([0], vector(n, k, 2^binomial(k,2)-polcoef(p,k)))} \\ Andrew Howroyd, Aug 26 2019

A006125(n) = a(n) + A054726(n).

Terms a(7) and beyond from Andrew Howroyd, Aug 26 2019

A326243 Number of capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 1, 11, 80, 503, 2993, 17609, 105017, 644528, 4107600, 27313805, 189866541, 1379728831, 10470032837, 82833202559, 681977545967, 5832430910181, 51723181525978, 474866750479993, 4506706112772881, 44151975623559477, 445958774322599940, 4638590033810841345

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

A set partition is capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The a(5) = 11 capturing set partitions:
  {{1,2,5},{3,4}}
  {{1,3,4},{2,5}}
  {{1,3,5},{2,4}}
  {{1,4},{2,3,5}}
  {{1,4,5},{2,3}}
  {{1,5},{2,3,4}}
  {{1},{2,5},{3,4}}
  {{1,4},{2,3},{5}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Non-capturing set partitions are A054391.
Crossing and nesting set partitions are (both) A016098.
Cf. A000108, A000110, A001519, A054391, A058681, A122880, A324170.
Cf. A326209, A326211, A326237, A326246, A326249, A326255, A326259.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xt||x>z&&y

a(n) = A000110(n) - A054391(n).

a(12) and beyond from Christian Sievers, Aug 23 2024

A326211 Number of unsortable normal multiset partitions of weight n.

Original entry on oeis.org

0, 0, 0, 1, 17, 170, 1455, 11678, 92871, 752473

Offset: 0

Gus Wiseman, Jun 19 2019

A multiset partition is normal if it covers an initial interval of positive integers. It is unsortable if no permutation has an ordered concatenation, or equivalently if the concatenation of its lexicographically-ordered parts is not weakly increasing. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

			The a(3) = 1 and a(4) = 17 multiset partitions:
  {{1,3},{2}}  {{1,1,3},{2}}
               {{1,2},{1,2}}
               {{1,2},{1,3}}
               {{1,2,3},{2}}
               {{1,2,4},{3}}
               {{1,3},{2,2}}
               {{1,3},{2,3}}
               {{1,3},{2,4}}
               {{1,3,3},{2}}
               {{1,3,4},{2}}
               {{1,4},{2,3}}
               {{1},{1,3},{2}}
               {{1},{2,4},{3}}
               {{1,3},{2},{2}}
               {{1,3},{2},{3}}
               {{1,3},{2},{4}}
               {{1,4},{2},{3}}

Unsortable set partitions are A058681.
Sortable normal multiset partitions are A326212.
Non-crossing normal multiset partitions are A324171.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A000108, A016098, A255906, A324170.
Cf. A326209, A326210, A326243, A326250, A326255, A326256.

lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Sort[#,lexsort]&/@Join@@mps/@allnorm[n],!OrderedQ[Join@@#]&]],{n,0,5}]

A255906(n) = a(n) + A326212(n).

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Original entry on oeis.org

1, 1, 2, 8, 36, 160, 704, 3088, 13536, 59328, 260032, 1139712

Offset: 0

Gus Wiseman, Jun 20 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(4) = 36 non-crossing, non-nesting simple labeled graphs.

The case for set partitions is A001519.
Simple graphs with crossing or nesting edges are A326279.
Cf. A000088, A000108, A006125, A016098, A054726, A095661, A117662.
Cf. A326209, A326210, A326250, A326255, A326256.

croXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x

A006125(n) = a(n) + A326279(n).
Conjectures from Colin Barker, Jun 28 2019: (Start)
G.f.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).
a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.
(End)

A326258 MM-numbers of unsortable multiset partitions (with empty parts allowed).

Original entry on oeis.org

145, 169, 215, 290, 338, 355, 377, 395, 430, 435, 473, 481, 505, 507, 535, 559, 565, 580, 645, 667, 676, 695, 710, 725, 754, 790, 793, 803, 815, 841, 845, 860, 865, 869, 870, 905, 923, 946, 962, 965, 989, 995, 1010, 1014, 1015, 1027, 1065, 1070, 1073, 1075

Offset: 1

Gus Wiseman, Jun 22 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.

A multiset partition is unsortable if no permutation has an ordered concatenation. For example, the multiset partition ((1,2),(1,1,1),(2,2,2)) is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

			The sequence of terms together with their multiset multisystems begins:
  145: {{2},{1,3}}
  169: {{1,2},{1,2}}
  215: {{2},{1,4}}
  290: {{},{2},{1,3}}
  338: {{},{1,2},{1,2}}
  355: {{2},{1,1,3}}
  377: {{1,2},{1,3}}
  395: {{2},{1,5}}
  430: {{},{2},{1,4}}
  435: {{1},{2},{1,3}}
  473: {{3},{1,4}}
  481: {{1,2},{1,1,2}}
  505: {{2},{1,6}}
  507: {{1},{1,2},{1,2}}
  535: {{2},{1,1,4}}
  559: {{1,2},{1,4}}
  565: {{2},{1,2,3}}
  580: {{},{},{2},{1,3}}
  645: {{1},{2},{1,4}}
  667: {{2,2},{1,3}}

Unsortable set partitions are A058681.
Normal unsortable multiset partitions are A326211.
Unsortable digraphs are A326209.
MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of capturing multiset partitions are A326255.
Cf. A001055, A016098, A056239, A112798, A302242.
Cf. A326212, A326243, A326257, A326259.

lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],!OrderedQ[Join@@Sort[primeMS/@primeMS[#],lexsort]]&]

A326248 Number of crossing, nesting set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 28, 252, 1890, 13020, 86564, 571944, 3826230, 26233662, 185746860, 1364083084, 10410773076, 82609104802, 681130756224, 5829231836494, 51711093240518, 474821049202852, 4506533206814480, 44151320870760216, 445956292457725714

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

A set partition is crossing if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < y < t or z < x < t < y, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t.

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

Christian Sievers, Table of n, a(n) for n = 0..576

Crossing and nesting set partitions are (both) A016098.
Crossing, capturing set partitions are A326246.
Nesting, non-crossing set partitions are A122880.
Cf. A000108, A000110, A001519, A058681, A099947, A117662, A324170.
Cf. A326209, A326211, A326243, A326245, A326256, A326258.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;x_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;x

a(n) = A000110(n) - 2*A000108(n) + A001519(n). - Christian Sievers, Oct 16 2024

a(11) and beyond from Christian Sievers, Oct 16 2024

A326212 Number of sortable normal multiset partitions of weight n.

Original entry on oeis.org

1, 1, 4, 15, 59, 230, 901, 3522, 13773, 53847, 210527, 823087, 3218002, 12581319, 49188823, 192312112, 751877137, 2939592383, 11492839729, 44933224559, 175674134309, 686828104551, 2685272063984, 10498530869151, 41045803846015, 160475597429847

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

A multiset partition is normal if it covers an initial interval of positive integers. It is sortable if some permutation has an ordered concatenation. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

			The a(0) = 1 through a(3) = 15 multiset partitions:
  {}  {{1}}  {{1,1}}    {{1,1,1}}
             {{1,2}}    {{1,1,2}}
             {{1},{1}}  {{1,2,2}}
             {{1},{2}}  {{1,2,3}}
                        {{1},{1,1}}
                        {{1},{1,2}}
                        {{1,1},{2}}
                        {{1},{2,2}}
                        {{1,2},{2}}
                        {{1},{2,3}}
                        {{1,2},{3}}
                        {{1},{1},{1}}
                        {{1},{1},{2}}
                        {{1},{2},{2}}
                        {{1},{2},{3}}

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

Sortable set partitions are A011782.
Unsortable normal multiset partitions are A326211.
Crossing normal multiset partitions are A326277.
Cf. A000041, A000108, A058681, A255906, A324170, A324171.
Cf. A326209, A326237, A326255, A326256, A326257, A326258.

lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Sort[#,lexsort]&/@Join@@mps/@allnorm[n],OrderedQ[Join@@#]&]],{n,0,5}]

seq(n) = my(p=1/eta(x + O(x*x^n))); Vec(((1 - x)*(1 - 2*x) - x^2*p)/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*p)) \\ Andrew Howroyd, May 11 2023

A255906(n) = a(n) + A326211(n).

G.f.: ((1 - x)*(1 - 2*x) - x^2*P(x))/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*P(x)) where P(x) is the g.f. of A000041. - Andrew Howroyd, May 11 2023

Terms a(10) and beyond from Andrew Howroyd, May 11 2023

A326237 Number of non-nesting digraphs with vertices {1..n}, where two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.

Original entry on oeis.org

1, 2, 12, 104, 1008, 10272, 107712, 1150592

Offset: 0

Gus Wiseman, Jun 19 2019

These are digraphs with the property that, if the edges are listed in lexicographic order, the sequence of targets is weakly increasing. For example, the digraph with lexicographically ordered edge set {(1,2),(2,1),(3,1),(3,2)} is nesting because the targets are (2,1,1,2), a sequence that is not weakly increasing.
Also the number of non-semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 non-semicrossing digraph edge-sets are:
  {}
  {11}
  {12}
  {21}
  {22}
  {11,12}
  {11,21}
  {12,21}
  {12,22}
  {21,22}
  {11,12,21}
  {12,21,22}
Apparently a duplicate of A152254. - R. J. Mathar, Jul 12 2019

			The a(2) = 12 non-nesting digraph edge-sets:
  {}
  {11}
  {12}
  {21}
  {22}
  {11,12}
  {11,21}
  {11,22}
  {12,22}
  {21,22}
  {11,12,22}
  {11,21,22}

Nesting digraphs are A326209.
Non-nesting set partitions are A000108.
Non-capturing set partitions are A054391.
Cf. A002416, A002720, A054391, A058681, A122880, A229865.
Cf. A326249, A326250, A326251, A326256, A326257.

Table[Length[Select[Subsets[Tuples[Range[n],2]],OrderedQ[Last/@#]&]],{n,4}]

A002416(n) = a(n) + A326209(n).

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Original entry on oeis.org

0, 0, 0, 3, 50, 982, 32636, 2096723

Offset: 0

Gus Wiseman, Jun 21 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d.

Gus Wiseman, The a(4) = 50 weakly nesting simple graphs.

Non-nesting set partitions are A000108.
Non-crossing graphs are A054726.
Nesting digraphs are A326209.
Crossing graphs are A326210.
MM-numbers of nesting multiset partitions are A326256.
Cf. A000088, A000332, A006125, A117662.
Cf. A326211, A326243, A326244, A326248, A326257, A326279.

wnsXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x<=z

Conjecture: A006125(n) = a(n) + A000108(n).

A229865 Number of n X n 0..1 arrays with corresponding row and column sums equal.

Original entry on oeis.org

1, 2, 8, 80, 2432, 247552, 88060928, 112371410944, 523858015518720, 9041009511609073664, 583447777113052431515648, 141885584718620229407228821504, 130832005909904417592540055577034752, 459749137931232137234615429529864283095040, 6182706200522446492946534924719926752508110700544

Offset: 0

R. H. Hardin, Oct 01 2013

nonn

Also known as labeled Eulerian digraphs allowing loops. - Brendan McKay, May 12 2019

			Some solutions for n=4:
  0 0 0 1     0 0 1 0     0 0 0 1     0 0 1 0     0 0 1 1
  0 1 0 0     1 0 0 0     1 0 1 0     0 0 1 1     1 0 0 1
  0 0 0 1     0 1 0 0     0 1 0 1     0 1 1 1     1 1 1 0
  1 0 1 0     0 0 0 1     0 1 1 0     1 1 0 0     0 1 1 1
From _Gus Wiseman_, Jun 22 2019: (Start)
The a(3) = 8 Eulerian digraph edge-sets:
  {}
  {11}
  {22}
  {11,22}
  {12,21}
  {11,12,21}
  {12,21,22}
  {11,12,21,22}
(End)

Mohammad Behzad Kang and Andrew Salch, The mod p cohomology of the Morava stabilizer group at large primes, arXiv:2410.24171 [math.AT], 2024. See p. 46.

Column 1 of A229870.
The unlabeled version is A308111.
Cf. A000595, A002416, A002720, A007080.
Cf. A326209, A326237, A326251, A326252, A326253.

Table[Length[Select[Subsets[Tuples[Range[n],2]],Sort[First/@#]==Sort[Last/@#]&]],{n,4}] (* Gus Wiseman, Jun 22 2019 *)

a(n) = 2^n * A007080(n). - Andrew Howroyd, Sep 11 2019

a(0)=1 prepended by Alois P. Heinz, May 14 2019

Terms a(11) and beyond from Andrew Howroyd, Sep 11 2019

cp's OEIS Frontend

A326210 Number of labeled simple graphs with vertices {1..n} containing a nesting pair of edges, where two edges {a,b}, {c,d} are nesting if a < c and b > d or a > c and b < d.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326243 Number of capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326211 Number of unsortable normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A326258 MM-numbers of unsortable multiset partitions (with empty parts allowed).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326248 Number of crossing, nesting set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326212 Number of sortable normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions