A059849 -id:A059849 - cp's OEIS frontend

A318394 Number of finite sets of set partitions of {1,...,n} such that any two have meet {{1},...,{n}}.

2, 4, 18, 316, 37492

Offset: 1

Gus Wiseman, Aug 25 2018

			The a(3) = 18 sets of set partitions:
        0
    {{1,2,3}}
   {{1,3},{2}}
   {{1,2},{3}}
   {{1},{2,3}}
  {{1},{2},{3}}
   {{1,2},{3}}   {{1,3},{2}}
   {{1},{2,3}}   {{1,3},{2}}
   {{1},{2,3}}   {{1,2},{3}}
  {{1},{2},{3}}   {{1,2,3}}
  {{1},{2},{3}}  {{1,3},{2}}
  {{1},{2},{3}}  {{1,2},{3}}
  {{1},{2},{3}}  {{1},{2,3}}
   {{1},{2,3}}   {{1,2},{3}}  {{1,3},{2}}
  {{1},{2},{3}}  {{1,2},{3}}  {{1,3},{2}}
  {{1},{2},{3}}  {{1},{2,3}}  {{1,3},{2}}
  {{1},{2},{3}}  {{1},{2,3}}  {{1,2},{3}}
  {{1},{2},{3}}  {{1},{2,3}}  {{1,2},{3}}  {{1,3},{2}}

Cf. A000110, A000258, A008277, A059849, A060639, A096827, A181939.

Cf. A318389, A318390, A318391, A318392, A318531, A318532, A318531, A318532.

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
spmeet[a_,b_]:=DeleteCases[Union@@Outer[Intersection,a,b,1],{}];spmeet[a_,b_,c__]:=spmeet[spmeet[a,b],c];
Table[Length[stableSets[sps[Range[n]],Max@@Length/@spmeet[#1,#2]>1&]],{n,5}]

A321661 Number of non-isomorphic multiset partitions of weight n where the nonzero entries of the incidence matrix are all distinct.

Original entry on oeis.org

1, 1, 1, 4, 4, 7, 22, 25, 40, 58, 186, 204, 347, 478, 734, 2033, 2402, 3814, 5464, 8142, 11058, 30142, 34437, 55940, 77794, 116954, 156465, 229462, 533612, 640544, 994922, 1397896, 2048316, 2778750, 3987432, 5292293, 11921070, 14076550, 21802928, 29917842, 44080285

Offset: 0

Gus Wiseman, Nov 15 2018

nonn

The incidence matrix of a multiset partition has entry (i, j) equal to the multiplicity of vertex i in part j.
Also the number of positive integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, whose nonzero entries are all distinct.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(6) = 22 multiset partitions:
  {{1}}  {{11}}  {{111}}    {{1111}}    {{11111}}    {{111111}}
                 {{122}}    {{1222}}    {{11222}}    {{112222}}
                 {{1}{11}}  {{1}{111}}  {{12222}}    {{122222}}
                 {{1}{22}}  {{1}{222}}  {{1}{1111}}  {{122333}}
                                        {{11}{111}}  {{1}{11111}}
                                        {{11}{222}}  {{11}{1111}}
                                        {{1}{2222}}  {{1}{11222}}
                                                     {{11}{1222}}
                                                     {{11}{2222}}
                                                     {{112}{222}}
                                                     {{11}{2333}}
                                                     {{1}{22222}}
                                                     {{122}{222}}
                                                     {{1}{22333}}
                                                     {{122}{333}}
                                                     {{2}{11222}}
                                                     {{22}{1222}}
                                                     {{1}{11}{111}}
                                                     {{1}{11}{222}}
                                                     {{1}{22}{222}}
                                                     {{1}{22}{333}}
                                                     {{2}{11}{222}}

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

Cf. A000219, A007716, A008289, A059201, A059849, A114736, A117433, A120733, A321653, A321659, A321660, A321662.

\\ here b(n) is A059849(n).
b(n)={sum(k=0, n, stirling(n,k,1)*sum(i=0, k, stirling(k,i,2))^2)}
seq(n)={my(B=vector((sqrtint(8*(n+1))+1)\2, n, b(n-1))); apply(p->sum(i=0, poldegree(p), B[i+1]*polcoef(p,i)), Vec(prod(k=1, n, 1 + x^k*y + O(x*x^n))))} \\ Andrew Howroyd, Nov 16 2018

a(n) = Sum_{k>=1} A059849(k)*A008289(n,k) for n > 0. - Andrew Howroyd, Nov 17 2018

Terms a(11) and beyond from Andrew Howroyd, Nov 16 2018

A318399 Number of triples of set partitions of {1,...,n} with meet {{1},...,{n}} and join {{1,...,n}}.

Original entry on oeis.org

1, 6, 84, 2226, 93246, 5616492, 459173406, 48933260388, 6595445513412, 1098326915060730, 221772386369110242, 53460963703982862534, 15185890964240671486740, 5026315912246843181692776, 1919721040169845172603949966, 838872819016448052585038291124

Offset: 1

Gus Wiseman, Aug 25 2018

nonn

			The a(2) = 6 triples:
  {{1},{2}} {{1},{2}}  {{1,2}}
  {{1},{2}}  {{1,2}}  {{1},{2}}
  {{1},{2}}  {{1,2}}   {{1,2}}
   {{1,2}}  {{1},{2}} {{1},{2}}
   {{1,2}}  {{1},{2}}  {{1,2}}
   {{1,2}}   {{1,2}}  {{1},{2}}

Cf. A000110, A000258, A001247, A008277, A048994, A059849, A060639, A181939, A318389, A318390, A318391, A318392, A318393, A318398.

nn=20;
Table[n!*SeriesCoefficient[Log[1+Sum[x^k/k!*Sum[StirlingS1[k,i]*BellB[i]^3,{i,0,k}],{k,nn}]],{x,0,n}],{n,nn}]

Logarithmic transform of A318398.

A319884 Number of unordered pairs of set partitions of {1,...,n} where every block of one is a proper subset or proper superset of some block of the other.

Original entry on oeis.org

1, 0, 1, 7, 50, 481, 5667, 78058, 1238295, 22314627, 451354476, 10148011215, 251584513215, 6831141750512, 201976943666357, 6470392653260939, 223595676728884394, 8302299221314559877, 330075531021130110015, 14006780163088113914026, 632606447496264724088803

Offset: 0

Gus Wiseman, Dec 09 2018

nonn

			The a(3) = 7 pairs of set partitions:
  (1)(2)(3)|(123)
    (1)(23)|(12)(3)
    (1)(23)|(13)(2)
    (1)(23)|(123)
    (12)(3)|(13)(2)
    (12)(3)|(123)
    (13)(2)|(123)

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

Cf. A000110, A000258, A001247, A008277, A059849, A060639, A181939, A322435, A322436, A322437, A322438, A322439, A322440, A322441, A322442.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
costabstrQ[s_,t_]:=And@@Cases[s,x_:>Select[t,x!=#&&(SubsetQ[x,#]||SubsetQ[#,x])&]!={}];
Table[Length[Select[Subsets[sps[Range[n]],{2}],And[costabstrQ@@#,costabstrQ@@Reverse[#]]&]],{n,5}]

F(x)={my(bell=(exp(y*(exp(x) - 1))  )); subst(serlaplace( serconvol(bell, bell)), y, exp(exp(x) - 1)-1)}
seq(n) = {my(x=x + O(x*x^n)); Vec(serlaplace( 1 + exp( 2*(exp(exp(x) - 1) - exp(x)) ) * F(x) )/2)} \\ Andrew Howroyd, Jan 19 2024

\\ 2nd prog, following formula - slightly slower
D(n,y) = (exp(2*y)/(1 + y)^2) * sum(k=0,n, x^k*sum(j=0, k, stirling(k,j,2) * y^j)^2/k!, O(x*x^n))
seq(n) = Vec(serlaplace((1/2)*(1 + D(n, exp(exp(x + O(x*x^n)) - 1) - 1)))) \\ Andrew Howroyd, Jan 20 2024

E.g.f.: (1/2)*(1 + D(x, exp(exp(x) - 1) - 1) ) where D(x,y) = (exp(2*y)/(1 + y)^2) * Sum_{k>=0} x^k*(Sum_{j=0..k} Stirling2(k,j)*y^j)^2/k!. - Andrew Howroyd, Jan 20 2024

a(8) onwards from Andrew Howroyd, Jan 19 2024

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Original entry on oeis.org

0, 0, 1, 7, 65, 811, 12762, 244588, 5574956, 148332645, 4538695461, 157768581675, 6167103354744, 268758895112072, 12961171404183498, 687270616305277589, 39843719438374998543, 2512873126513271758171, 171643113190082528007702, 12647168303374365311984284

Offset: 0

David Pasino, Dec 06 2008, Dec 08 2008

nonn

			From _Gus Wiseman_, Dec 09 2018: (Start)
The a(3) = 7 unordered pairs:
  {{1},{2},{3}}| {{1,2,3}}
   {{1},{2,3}} |{{1,2},{3}}
   {{1},{2,3}} |{{1,3},{2}}
   {{1,2},{3}} |{{1,3},{2}}
   {{1},{2,3}} | {{1,2,3}}
   {{1,2},{3}} | {{1,2,3}}
   {{1,3},{2}} | {{1,2,3}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From _N. J. A. Sloane_, Oct 03 2012

Cf. A000110, A000258, A001247, A008277, A048993, A059849, A060639, A181939, A193297, A318393, A322441, A322442, A320768.

a:= n-> add(binomial(n,k)*binomial(combinat[bell](k),2)*
        add(Stirling2(n-k,j)*(-1)^j, j=0..n-k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 27 2018

Array[Sum[Binomial[#, k] Sum[(-1)^j*StirlingS2[# - k, j], {j, 0, # - k}] Binomial[BellB@ k, 2], {k, 0, #}] &, 20, 0] (* Michael De Vlieger, May 27 2018 *)

a000110(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
a(n) = sum(k=0, n, binomial(n,k) * sum(j=0, n-k, (-1)^j*stirling(n-k,j, 2) * binomial(a000110(k),2))); \\ Michel Marcus, May 27 2018

a(n) = Sum_{k=0..n} binomial(n,k) * (Sum_{j=0..n-k} (-1)^j*A048993(n-k,j)) * binomial(A000110(k),2).
That is, summed on k from 0 to n, the number of k-element subsets of an n-element set, times the alternating sum of row n-k of Stirling2 numbers starting with +S(n-k, 0), times the number of pairs of partitions of k elements.
Obtained by inverting (binomial(A000110(n), 2)) = (Sum_{k=0..n} binomial(n,k)*A000110(n-k)*a(k)), which in turn is gotten by considering that a pair of conjoint partitions is gotten by choosing a partition of a subset and then choosing a pair of disjoint partitions of the complement.

A318398 Number of triples of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}}.

Original entry on oeis.org

1, 7, 103, 2707, 110857, 6517129, 521167549, 54510591469, 7235648605909, 1190181847444189, 237953165658759679, 56905537750421669449, 16059682765076576965879, 5287171379685771887014489, 2010360123437921314268936809, 875173620070717892287441139989

Offset: 1

Gus Wiseman, Aug 25 2018

nonn

			The a(2) = 7 triples:
  {{1},{2}} {{1},{2}} {{1},{2}}
  {{1},{2}} {{1},{2}}  {{1,2}}
  {{1},{2}}  {{1,2}}  {{1},{2}}
  {{1},{2}}  {{1,2}}   {{1,2}}
   {{1,2}}  {{1},{2}} {{1},{2}}
   {{1,2}}  {{1},{2}}  {{1,2}}
   {{1,2}}   {{1,2}}  {{1},{2}}

Cf. A000110, A000258, A001247, A008277, A048994, A059849, A060639, A181939, A318389, A318391, A318393, A318399.

Table[Sum[StirlingS1[n,k]*BellB[k]^3,{k,0,n}],{n,10}]

a(n) = Sum_{k = 0..n} s(n,k)*B(k)^3 where s = A048994 and B = A000110.

A318531 Number of finite sets of set partitions of {1,...,n} such that any two have join {{1,...,n}}.

Original entry on oeis.org

2, 4, 18, 450, 436270

Offset: 1

Gus Wiseman, Aug 28 2018

			The a(3) = 18 sets of set partitions:
        0
    {{1,2,3}}
   {{1,3},{2}}
   {{1,2},{3}}
   {{1},{2,3}}
  {{1},{2},{3}}
   {{1,3},{2}}   {{1,2,3}}
   {{1,2},{3}}   {{1,2,3}}
   {{1,2},{3}}  {{1,3},{2}}
   {{1},{2,3}}   {{1,2,3}}
   {{1},{2,3}}  {{1,3},{2}}
   {{1},{2,3}}  {{1,2},{3}}
  {{1},{2},{3}}  {{1,2,3}}
   {{1,2},{3}}  {{1,3},{2}}   {{1,2,3}}
   {{1},{2,3}}  {{1,3},{2}}   {{1,2,3}}
   {{1},{2,3}}  {{1,2},{3}}   {{1,2,3}}
   {{1},{2,3}}  {{1,2},{3}}  {{1,3},{2}}
   {{1},{2,3}}  {{1,2},{3}}  {{1,3},{2}}  {{1,2,3}}

Cf. A000110, A000258, A008277, A059849, A060639, A096827, A181939.

Cf. A318389, A318390, A318391, A318392, A318394, A318532.

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[stableSets[sps[Range[n]],Length[csm[Union[#1,#2]]]>1&]],{n,4}]

A318532 Number of finite sets of set partitions of {1,...,n} such that any two have meet {{1},...,{n}} and join {{1,...,n}}.

Original entry on oeis.org

2, 4, 11, 51, 635, 15591

Offset: 1

Gus Wiseman, Aug 28 2018

			The a(3) = 11 sets of set partitions:
        0
    {{1,2,3}}
   {{1,3},{2}}
   {{1,2},{3}}
   {{1},{2,3}}
  {{1},{2},{3}}
   {{1,2},{3}}   {{1,3},{2}}
   {{1},{2,3}}   {{1,3},{2}}
   {{1},{2,3}}   {{1,2},{3}}
  {{1},{2},{3}}   {{1,2,3}}
   {{1},{2,3}}   {{1,2},{3}}  {{1,3},{2}}

Cf. A000110, A000258, A008277, A059849, A060639, A096827, A181939.

Cf. A318389, A318390, A318391, A318392, A318394, A318531.

A318815 Number of triples of set partitions of {1,2,...,n} whose join is {{1,2,...,n}}.

Original entry on oeis.org

1, 7, 103, 2773, 117697, 7167619, 590978941, 63385879261, 8584707943381, 1434654097736101, 290409845948305321, 70125579500764771585, 19940633217840575968969, 6603748351832744611210549, 2522614472277243822293033719, 1102166886808604068546379343289

Offset: 1

Gus Wiseman, Sep 04 2018

nonn

			The a(2) = 7 triples:
  {{1},{2}} {{1},{2}}  {{1,2}}
  {{1},{2}}  {{1,2}}  {{1},{2}}
  {{1},{2}}  {{1,2}}   {{1,2}}
   {{1,2}}  {{1},{2}} {{1},{2}}
   {{1,2}}  {{1},{2}}  {{1,2}}
   {{1,2}}   {{1,2}}  {{1},{2}}
   {{1,2}}   {{1,2}}   {{1,2}}

Alois P. Heinz, Table of n, a(n) for n = 1..233

Cf. A000110, A000258, A001247, A008277, A048994, A059849, A060639, A181939, A318389, A318391, A318393, A318398, A318399.

nn=10;Table[n!*SeriesCoefficient[Log[1+Sum[BellB[n]^3*x^n/n!,{n,nn}]],{x,0,n}],{n,nn}]

Logarithmic transform of A000110(n)^3.

a(n) = Bell(n)^3 - (1/n) * Sum_{k=1..n-1} binomial(n,k) * Bell(n-k)^3 * k * a(k). - Ilya Gutkovskiy, Jan 17 2020

A318915 Number of joining pairs of integer partitions of n.

Original entry on oeis.org

1, 1, 3, 5, 11, 15, 33, 41, 77, 105, 173, 215, 381, 449, 699, 911, 1335, 1611, 2433, 2867, 4179, 5113, 6903, 8251, 11769, 13661, 18177, 22011, 28997, 33711, 45251

Offset: 0

Gus Wiseman, Sep 05 2018

Two integer partitions are a joining pair if they have no common cover (coarser partition) other than the maximum. For example, (221) and (311) are not a joining pair as they are both covered by (32) or (41), while (222) and (33) are a joining pair.
All terms are odd.
The same as the number of pairs of integer partitions of n without common subsums. - Mamuka Jibladze, Jun 16 2024

			The sequence of joining pairs of integer partitions begins:
  ()()   (1)(1)   (2)(2)    (3)(3)     (4)(4)      (5)(5)
                  (2)(11)   (3)(21)    (4)(31)     (5)(41)
                  (11)(2)   (3)(111)   (4)(22)     (5)(32)
                            (21)(3)    (4)(211)    (5)(311)
                            (111)(3)   (4)(1111)   (5)(221)
                                       (31)(4)     (5)(2111)
                                       (31)(22)    (5)(11111)
                                       (22)(4)     (41)(5)
                                       (22)(31)    (41)(32)
                                       (211)(4)    (32)(5)
                                       (1111)(4)   (32)(41)
                                                   (311)(5)
                                                   (221)(5)
                                                   (2111)(5)
                                                   (11111)(5)

P. Erdős, J. Nicolas and A. Sárközy, On the number of pairs of partitions of n without common subsums, Colloquium Mathematicae, 63 (1992), 61-83.

Cf. A000041, A059849, A060639, A181939, A265947, A299925, A300383, A317141, A317143.

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]]]];
ptncaps[y_]:=Union[Map[Sort[Total/@#,Greater]&,mps[y],{1}]];
Table[Select[Tuples[IntegerPartitions[n],2],Intersection@@ptncaps/@#=={{n}}&]//Length,{n,6}]

a(n) >= 2 * A000041(n) - 1. - Alois P. Heinz, Sep 06 2018

a(13)-a(30) from Alois P. Heinz, Sep 05 2018

cp's OEIS Frontend

A318394 Number of finite sets of set partitions of {1,...,n} such that any two have meet {{1},...,{n}}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A321661 Number of non-isomorphic multiset partitions of weight n where the nonzero entries of the incidence matrix are all distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A318399 Number of triples of set partitions of {1,...,n} with meet {{1},...,{n}} and join {{1,...,n}}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A319884 Number of unordered pairs of set partitions of {1,...,n} where every block of one is a proper subset or proper superset of some block of the other.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A318398 Number of triples of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A318531 Number of finite sets of set partitions of {1,...,n} such that any two have join {{1,...,n}}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A318532 Number of finite sets of set partitions of {1,...,n} such that any two have meet {{1},...,{n}} and join {{1,...,n}}.

Views

Author

Keywords

Examples

Crossrefs

A318815 Number of triples of set partitions of {1,2,...,n} whose join is {{1,2,...,n}}.

Views