A324170 -id:A324170 - cp's OEIS frontend

A326251 Number of digraphs with vertices {1..n} whose increasing edges are not crossing.

1, 2, 16, 512, 49152, 11534336, 6039797760, 6768868458496, 15885743998107648, 77083611222073409536, 767126299049285413502976, 15572324598183490228037091328, 642316330843573124053884695740416, 53681919993405760099480940765478125568

Offset: 0

Gus Wiseman, Jun 30 2019

nonn

A directed edge (a,b) is increasing if a < b. Two edges (a,b), (c,d) are crossing if a < c < b < d or c < a < d < b.

Conjecture: Also the number of non-nesting digraphs with vertices {1..n} whose increasing edges are not crossing, where two edges (a,b), (c,d) are nesting if a < c < d < b or c < a < b < d.

Simple graphs whose edges are non-crossing are A054726.
Digraphs whose edges are not crossing are A326237.
Digraphs whose increasing edges are crossing are A326252.
Cf. A002416, A229865, A324170, A326209, A326250, A326251.

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

a(n) = 2^(n * (n + 1)/2) * A054726(n).

A324326 Number of crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 10, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 36, 0, 14, 0, 0, 0, 25, 0, 0, 0, 71, 0, 0, 0, 0, 0, 0, 0, 103, 0, 0, 0, 0, 0, 0, 0, 75

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A multiset partition is crossing if it contains two blocks of the form {{...x...y...},{...z...t...}} with x < z < y < t or z < x < t < y.

			The a(36) = 10 crossing multiset partitions of {1,1,2,2,3,4}:
  {{1,3},{1,2,2,4}}
  {{2,4},{1,1,2,3}}
  {{1,1,3},{2,2,4}}
  {{1,2,3},{1,2,4}}
  {{1},{1,3},{2,2,4}}
  {{1},{2,4},{1,2,3}}
  {{2},{1,3},{1,2,4}}
  {{2},{1,1,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1},{2},{1,3},{2,4}}

Cf. A000108, A001055, A001970, A016098, A054726, A099947, A181821, A305936, A306438, A318284, A318285.

Cf. A324167, A324168, A324169, A324170, A324171, A324324, A324325.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

a(n) + A324325(n) = A318284(n).

A326260 MM-numbers of capturing, non-nesting multiset partitions (with empty parts allowed).

Original entry on oeis.org

2599, 4163, 5198, 6463, 6893, 7291, 7797, 8326, 8507, 9131, 9959, 10396, 10649, 11041, 11639, 12489, 12811, 12926, 12995, 13786, 14237, 14582, 14899, 15157, 15594, 16123, 16403, 16652, 17014, 17063, 17089, 17141, 18101, 18193, 18262, 18643, 18659, 19337, 19389

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 set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. It is nesting if it has two blocks of the form {...x,y...} and {...z,t...} where x < z and y > t or x > z and y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The sequence of terms together with their multiset multisystems begins:
   2599: {{2,2},{1,2,3}}
   4163: {{2,2},{1,2,4}}
   5198: {{},{2,2},{1,2,3}}
   6463: {{2,2},{1,1,2,3}}
   6893: {{1,2,2},{1,2,3}}
   7291: {{2,2},{1,2,5}}
   7797: {{1},{2,2},{1,2,3}}
   8326: {{},{2,2},{1,2,4}}
   8507: {{2,3},{1,2,4}}
   9131: {{2,2},{1,2,6}}
   9959: {{2,2},{1,1,2,4}}
  10396: {{},{},{2,2},{1,2,3}}
  10649: {{2,2},{1,2,2,3}}
  11041: {{1,2,2},{1,2,4}}
  11639: {{2,2,2},{1,2,3}}
  12489: {{1},{2,2},{1,2,4}}
  12811: {{2,2},{1,2,7}}
  12926: {{},{2,2},{1,1,2,3}}
  12995: {{2},{2,2},{1,2,3}}
  13786: {{},{1,2,2},{1,2,3}}

Non-nesting set partitions are A000108.
Capturing set partitions are A326243.
Capturing, non-nesting set partitions are A326249.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of capturing multiset partitions are A326255.
Cf. A001055, A034827, A056239, A058681, A112798, A117662, A302242, A324170.
Cf. A326212, A326246, A054391, A326257, A326258, A326259.

capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;xTable[PrimePi[p],{k}]]]];
Select[Range[10000],!nesXQ[primeMS/@primeMS[#]]&&capXQ[primeMS/@primeMS[#]]&]

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Original entry on oeis.org

0, 0, 1, 9, 32, 80, 165, 301, 504, 792, 1185, 1705, 2376, 3224, 4277, 5565, 7120, 8976, 11169, 13737, 16720, 20160, 24101, 28589, 33672, 39400, 45825, 53001, 60984, 69832, 79605, 90365, 102176, 115104, 129217, 144585, 161280, 179376, 198949, 220077, 242840

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

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.

			The a(3) = 9 pairs of edges:
  {12,12}
  {12,13}
  {12,23}
  {13,12}
  {13,13}
  {13,23}
  {23,12}
  {23,13}
  {23,23}

Gus Wiseman, The a(4) = 32 pairs of edges that are neither crossing nor nesting.

The case for simple graphs (rather than multigraphs) is A095661.
Simple graphs that are neither crossing nor nesting are A326244.
The case for set partitions is A001519.
Non-crossing and non-nesting simple graphs are (both) A054726.
Cf. A000108, A002061, A006125, A117662, A324170, A326250, A326256.

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

Conjectures from Colin Barker, Jun 21 2019: (Start)
G.f.: x^2*(1 + 4*x - 3*x^2) / (1 - x)^5.
a(n) = (n*(12 - 19*n + 6*n^2 + n^3)) / 12.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
(End)

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Original entry on oeis.org

0, 0, 0, 4, 56, 1008, 32736, 2097088, 268435328, 68719476480, 35184372088320, 36028797018962944, 73786976294838204416, 302231454903657293672448, 2475880078570760549798240256, 40564819207303340847894502555648, 1329227995784915872903807060280311808

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

Number of simple graphs with vertices {1..n} containing two edges {a,b}, {c,d} that are weakly crossing, meaning a <= c < b <= d or c <= a < d <= b.

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

Cf. A000088, A000108, A002662, A006125, A016098, A054726, A324170.

Cf. A326210, A326244, A326248, A326250, A326257, A326279, A326290.

Table[If[n==0,0,2^Binomial[n,2]-2^(n-1)],{n,0,5}]

A326291 Number of unsortable factorizations of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 24 2019

nonn

A factorization into factors > 1 is unsortable if there is no permutation (c_1,...,c_k) of the factors such that the maximum prime factor of c_i is at most the minimum prime factor of c_{i+1}. For example, the factorization (6*8*27) is sortable because the permutation (8,6,27) satisfies the condition.

			The a(180) = 10 unsortable factorizations:
  (2*3*3*10)  (5*6*6)   (3*60)
              (2*3*30)  (6*30)
              (2*9*10)  (9*20)
              (3*3*20)  (10*18)
              (3*6*10)
Missing from this list are:
  (2*2*3*3*5)  (2*2*5*9)   (4*5*9)   (2*90)   (180)
               (2*3*5*6)   (2*2*45)  (4*45)
               (3*3*4*5)   (2*5*18)  (5*36)
               (2*2*3*15)  (2*6*15)  (12*15)
                           (3*4*15)
                           (3*5*12)

Unsortable set partitions are A058681.
Unsortable normal multiset partitions are A326211.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A000108, A001055, A001519, A016098, A112798, A302242, A324170, A324171.
Cf. A326209, A326212, A326243, A326256, A326257.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[facs[n],!OrderedQ[Join@@Sort[primeMS/@#,lexsort]]&]],{n,100}]

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 5, 9, 7, 7, 11, 11, 12, 16, 14, 15, 26, 22, 21, 29, 19, 30, 33, 31, 30, 66, 38, 42, 52, 56, 42, 47, 45, 57, 82, 77, 67, 77, 67, 101, 98, 135, 64, 137, 97, 176, 104, 109, 109, 118, 105, 231, 213, 97, 127, 181, 139, 297, 173, 385, 195, 269

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A multiset partition is crossing if it contains two blocks of the form {{...x...y...},{...z...t...}} where x < z < y < t or z < x < t < y.

			The a(16) = 14 non-crossing multiset partitions of the multiset {1,2,3,4}:
  {{1,2,3,4}}
  {{1},{2,3,4}}
  {{2},{1,3,4}}
  {{3},{1,2,4}}
  {{4},{1,2,3}}
  {{1,2},{3,4}}
  {{1,4},{2,3}}
  {{1},{2},{3,4}}
  {{1},{3},{2,4}}
  {{1},{4},{2,3}}
  {{2},{3},{1,4}}
  {{2},{4},{1,3}}
  {{3},{1,2},{4}}
  {{1},{2},{3},{4}}
Missing from this list is {{1,3},{2,4}}.

Cf. A000108, A001055, A001970, A016098, A054726, A099947, A181821, A305936, A306438, A318284, A318285.

Cf. A324167, A324168, A324169, A324170, A324171, A324324, A324326.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

a(n) + A324326(n) = A318284(n).

A326277 Number of crossing normal multiset partitions of weight n.

Original entry on oeis.org

0, 0, 0, 0, 1, 22, 314, 3711, 39947

Offset: 0

Gus Wiseman, Jun 22 2019

A multiset partition is normal if it covers an initial interval of positive integers.

A multiset 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.

			The a(5) = 22 crossing normal multiset partitions:
  {{1,3},{1,2,4}}  {{1},{1,3},{2,4}}
  {{1,3},{2,2,4}}  {{1},{2,4},{3,5}}
  {{1,3},{2,3,4}}  {{2},{1,3},{2,4}}
  {{1,3},{2,4,4}}  {{2},{1,4},{3,5}}
  {{1,3},{2,4,5}}  {{3},{1,3},{2,4}}
  {{1,4},{2,3,5}}  {{3},{1,4},{2,5}}
  {{2,4},{1,1,3}}  {{4},{1,3},{2,4}}
  {{2,4},{1,2,3}}  {{4},{1,3},{2,5}}
  {{2,4},{1,3,3}}  {{5},{1,3},{2,4}}
  {{2,4},{1,3,4}}
  {{2,4},{1,3,5}}
  {{2,5},{1,3,4}}
  {{3,5},{1,2,4}}

Crossing simple graphs are A326210.
Normal multiset partitions are A255906.
Non-crossing normal multiset partitions are A324171.
MM-numbers of crossing multiset partitions are A324170.
Cf. A000108, A016098, A054726, A058681.
Cf. A326211, A326212, A326255, A326256, A326258.

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]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A326292 Number of crossing integer partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 43, 57, 80, 105, 142, 186, 248, 320, 421, 539, 698, 889, 1140, 1438, 1827, 2291, 2882, 3593, 4489, 5559, 6902, 8503, 10484, 12853, 15763

Offset: 0

Gus Wiseman, Oct 03 2019

nonn

A multiset 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. An integer partition is crossing if, by replacing each part with its multiset of prime indices, we obtain a crossing multiset partition.

			The a(31) = 1 through a(36) = 7 partitions:
  21,10  21,10,1  21,10,2    21,10,3      21,10,4        21,10,5
                  21,10,1,1  21,10,2,1    21,10,2,2      21,10,3,2
                             21,10,1,1,1  21,10,3,1      21,10,4,1
                                          21,10,2,1,1    21,10,2,2,1
                                          21,10,1,1,1,1  21,10,3,1,1
                                                         21,10,2,1,1,1
                                                         21,10,1,1,1,1,1

The Heinz numbers of these partitions are given by A324170.

Cf. A000108, A002662, A016098, A056239, A112798, A324172, A324326, A326210, A326252, A326332.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

More terms from Jinyuan Wang, Jun 28 2020

cp's OEIS Frontend

A326251 Number of digraphs with vertices {1..n} whose increasing edges are not crossing.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A324326 Number of crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326260 MM-numbers of capturing, non-nesting multiset partitions (with empty parts allowed).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326291 Number of unsortable factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324325 Number of non-crossing multiset partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326277 Number of crossing normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326292 Number of crossing integer partitions of n.

Views

Author