A326259 -id:A326259 - cp's OEIS frontend

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

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

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]]&]

A326255 MM-numbers of capturing multiset partitions.

Original entry on oeis.org

667, 989, 1334, 1633, 1769, 1817, 1978, 2001, 2021, 2323, 2461, 2599, 2623, 2668, 2967, 2987, 3197, 3266, 3335, 3538, 3634, 3713, 3749, 3956, 3979, 4002, 4042, 4163, 4171, 4331, 4379, 4429, 4439, 4577, 4646, 4669, 4747, 4819, 4859, 4899, 4922, 4945, 5029, 5198

Offset: 1

Gus Wiseman, Jun 20 2019

nonn

First differs from A326256 in having 2599.
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 capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and t < y or z < x and y < t. This 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:
   667: {{2,2},{1,3}}
   989: {{2,2},{1,4}}
  1334: {{},{2,2},{1,3}}
  1633: {{2,2},{1,1,3}}
  1769: {{1,3},{1,2,2}}
  1817: {{2,2},{1,5}}
  1978: {{},{2,2},{1,4}}
  2001: {{1},{2,2},{1,3}}
  2021: {{1,4},{2,3}}
  2323: {{2,2},{1,6}}
  2461: {{2,2},{1,1,4}}
  2599: {{2,2},{1,2,3}}
  2623: {{1,4},{1,2,2}}
  2668: {{},{},{2,2},{1,3}}
  2967: {{1},{2,2},{1,4}}
  2987: {{1,3},{2,2,2}}
  3197: {{2,2},{1,7}}
  3266: {{},{2,2},{1,1,3}}
  3335: {{2},{2,2},{1,3}}
  3538: {{},{1,3},{1,2,2}}

MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of crossing capturing multiset partitions are A326259.
Capturing set partitions are A326243.
Cf. A001055, A034827, A058681, A112798, A117662, A122880, A302242.
Cf. A326211, A326249, A054391, A326257, A326258.

capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xt||x>z&&yTable[PrimePi[p],{k}]]]];
Select[Range[10000],capXQ[primeMS/@primeMS[#]]&]

A122880 Catalan numbers minus odd-indexed Fibonacci numbers.

Original entry on oeis.org

0, 0, 0, 1, 8, 43, 196, 820, 3265, 12615, 47840, 179355, 667875, 2478022, 9180616, 34011401, 126120212, 468411235, 1743105373, 6500874434, 24300686879, 91049069203, 341924710480, 1286932932251, 4854167659403, 18346988061078

Offset: 1

Gary W. Adamson, Sep 16 2006

nonn

From Emeric Deutsch, Aug 21 2008: (Start)
Number of Dyck paths of height at least 4 and of semilength n. Example: a(5)=8 because we have UUUUUDDDDD, UUUUDUDDDD, UUUDUUDDDD, UUDUUUDDDD, UDUUUUDDDD and the reflection of the last three in a vertical axis.
Number of ordered trees of height at least 4 and having n edges. (End)
From Gus Wiseman, Jun 22 2019: (Start)
Also the number of non-crossing, capturing set partitions of {1..n}. 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 capturing if it has two blocks of the form {...x...y...}, {...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 a(4) = 1 and a(5) = 8 non-crossing, capturing set partitions are:
  {{1,4},{2,3}}  {{1,2,5},{3,4}}
                 {{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}}
(End)

			a(5) = 8 = A000108(5) - A001519(5) = 42 - 34.

E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325. [_Emeric Deutsch_, Aug 21 2008]

Cf. A000108, A001519, A122881.
Non-crossing set partitions are A000108.
Capturing set partitions are A326243.
Crossing, not capturing set partitions are A326245.
Crossing, capturing set partitions are A326246.
Cf. A000110, A054391, A099947, A326255, A326259.

with(combinat): seq(binomial(2*n,n)/(n+1)-fibonacci(2*n-1), n=1..27); # Emeric Deutsch, Aug 21 2008

With[{nn=30},#[[1]]-#[[2]]&/@Thread[{CatalanNumber[Range[nn]], Fibonacci[ Range[ 1,2nn,2]]}]] (* Harvey P. Dale, Nov 07 2016 *)

A000108(n) - A001519(n), n > 0; A000108 = Catalan numbers, A001519 = odd-indexed Fibonacci numbers.

More terms from Emeric Deutsch, Aug 21 2008

A326246 Number of crossing, capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 37, 307, 2173, 14344, 92402, 596688

Offset: 0

Gus Wiseman, Jun 20 2019

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

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

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

MM-numbers of crossing, capturing multiset partitions are A326259.
Crossing set partitions are A016098.
Capturing set partitions are A326243.
Crossing, nesting set partitions are A326248.
Crossing, non-capturing set partitions are A326245.
Non-crossing, capturing set partitions are A122880 (conjecture).
Cf. A000108, A000110, A058681, A099947, A324170, A326211, A326249, A054391, A326255.

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

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[#]]&]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326255 MM-numbers of capturing multiset partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A122880 Catalan numbers minus odd-indexed Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A326246 Number of crossing, capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica