A306438 -id:A306438 - cp's OEIS frontend

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

1, 1, 4, 16, 75, 378, 2042, 11489, 66697

Offset: 0

Gus Wiseman, Feb 17 2019

A multiset is normal if its union is an initial interval of positive integers.

A multiset partition is crossing if it has a 2-element submultiset of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The A255906(5) - a(5) = 22 crossing multiset partitions:
  {{13}{124}}  {{1}{13}{24}}
  {{13}{224}}  {{1}{24}{35}}
  {{13}{234}}  {{2}{13}{24}}
  {{13}{244}}  {{2}{14}{35}}
  {{13}{245}}  {{3}{13}{24}}
  {{14}{235}}  {{3}{14}{25}}
  {{24}{113}}  {{4}{13}{24}}
  {{24}{123}}  {{4}{13}{25}}
  {{24}{133}}  {{5}{13}{24}}
  {{24}{134}}
  {{24}{135}}
  {{25}{134}}
  {{35}{124}}

Cf. A000108 (non-crossing set partitions), A000124, A001006, A001055, A001263, A007297, A054726 (non-crossing graphs), A099947, A194560, A255906 (multiset partitions of normal multisets), A306438.

Cf. A324166, A324167, A324168, A324169, A324170, A324173.

nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_}]:=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]];
Table[Sum[Length[Select[mps[m],nonXQ]],{m,allnorm[n]}],{n,0,8}]

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.

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 19, 120, 1084, 11783, 141110, 1791156, 23646352, 321220257, 4459886776, 63000867229, 902528825332, 13080523942476, 191445447535373, 2825542818304080, 42005234042942228, 628422035415996065, 9454076958795999908, 142933849346150225253, 2170556938059142024688

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(3) = 19 non-crossing antichains:
  {}  {}     {}        {}
      {{1}}  {{1}}     {{1}}
             {{2}}     {{2}}
             {{12}}    {{3}}
             {{1}{2}}  {{12}}
                       {{13}}
                       {{23}}
                       {{123}}
                       {{1}{2}}
                       {{1}{3}}
                       {{2}{3}}
                       {{1}{23}}
                       {{2}{13}}
                       {{3}{12}}
                       {{12}{13}}
                       {{12}{23}}
                       {{13}{23}}
                       {{1}{2}{3}}
                       {{12}{13}{23}}

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

Cf. A000108 (non-crossing set partitions), A000124, A000372 (antichains), A001006, A001263, A006126 (antichain covers), A014466 (nonempty antichains), A054726 (non-crossing graphs), A099947, A261005, A306438.

Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

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

seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-2*x))/x) } \\ Andrew Howroyd, Jan 20 2023

Binomial transform of A324167.

G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - Andrew Howroyd, Jan 20 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 5, 0, 0, 0, 0, 1, 16, 4, 0, 0, 0, 0, 1, 42, 42, 0, 0, 0, 0, 0, 1, 99, 258, 27, 0, 0, 0, 0, 0, 1, 219, 1222, 465, 0, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 22 2019

A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y.

			Triangle begins:
    1
    0    1
    0    1    0
    0    1    0    0
    0    1    1    0    0
    0    1    5    0    0    0
    0    1   16    4    0    0    0
    0    1   42   42    0    0    0    0
    0    1   99  258   27    0    0    0    0
    0    1  219 1222  465    0    0    0    0    0
Row n = 6 counts the following set partitions:
  {{123456}}  {{1235}{46}}  {{13}{25}{46}}
              {{124}{356}}  {{14}{25}{36}}
              {{1245}{36}}  {{14}{26}{35}}
              {{1246}{35}}  {{15}{24}{36}}
              {{125}{346}}
              {{13}{2456}}
              {{134}{256}}
              {{1345}{26}}
              {{1346}{25}}
              {{135}{246}}
              {{1356}{24}}
              {{136}{245}}
              {{14}{2356}}
              {{145}{236}}
              {{146}{235}}
              {{15}{2346}}

Row sums are A099947. Row k = 2 is A002662.
Cf. A000108, A000110, A001263, A016098, A136653, A268814, A268815, A306438, A324011.
Cf. A324166, A324172, A324173, A324327, A324328.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[crosscmpts[#]]<=1&&Length[#]==k&]],{n,0,6},{k,0,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).

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).

cp's OEIS Frontend

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

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