A319752 -id:A319752 - cp's OEIS frontend

A328673 Number of integer partitions of n in which no two distinct parts are relatively prime.

1, 1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 15, 2, 17, 10, 23, 2, 39, 2, 46, 18, 58, 2, 95, 8, 103, 31, 139, 2, 219, 3, 232, 59, 299, 22, 452, 4, 492, 104, 645, 5, 920, 5, 1006, 204, 1258, 8, 1785, 21, 1994, 302, 2442, 11, 3366, 71, 3738, 497, 4570, 18, 6253, 24, 6849

Offset: 0

Gus Wiseman, Oct 29 2019

nonn

A partition with no two distinct parts relatively prime is said to be intersecting.

			The a(1) = 1 through a(10) = 9 partitions (A = 10):
  1  2   3    4     5      6       7        8         9          A
     11  111  22    11111  33      1111111  44        63         55
              1111         42               62        333        64
                           222              422       111111111  82
                           111111           2222                 442
                                            11111111             622
                                                                 4222
                                                                 22222
                                                                 1111111111

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350

The Heinz numbers of these partitions are A328867 (strict case is A318719).
The relatively prime case is A328672.
The strict case is A318717.
The version for non-isomorphic multiset partitions is A319752.
The version for set-systems is A305843.
The version involving all parts (not just distinct ones) is A200976.
Cf. A000837, A202425, A305148, A305854, A306006, A316476, A326910.

Table[Length[Select[IntegerPartitions[n],And@@(GCD[##]>1&)@@@Subsets[Union[#],{2}]&]],{n,0,20}]

a(n > 0) = A200976(n) + 1.

A200976 Number of partitions of n such that each pair of parts (if any) has a common factor.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 1, 38, 1, 45, 17, 57, 1, 94, 7, 102, 30, 138, 1, 218, 2, 231, 58, 298, 21, 451, 3, 491, 103, 644, 4, 919, 4, 1005, 203, 1257, 7, 1784, 20, 1993, 301, 2441, 10, 3365, 70, 3737, 496, 4569, 17, 6252, 23, 6848

Offset: 0

Alois P. Heinz, Nov 29 2011

nonn

a(n) is different from A018783(n) for n = 0, 31, 37, 41, 43, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, ... .

Every pair of (possibly equal) parts has a common factor > 1. These partitions are said to be (pairwise) intersecting. - Gus Wiseman, Nov 04 2019

			a(0) = 1: [];
a(4) = 2: [2,2], [4];
a(9) = 3: [3,3,3], [3,6], [9];
a(31) = 2: [6,10,15], [31];
a(41) = 4: [6,10,10,15], [6,15,20], [6,14,21], [41].

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350 (terms 0..250 from Alois P. Heinz)
L. Naughton, G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8

Cf. A018783.
The version with only distinct parts compared is A328673.
The relatively prime case is A202425.
The strict case is A318717.
The version for non-isomorphic multiset partitions is A319752.
The version for set-systems is A305843.
Cf. A000837, A305148, A305854, A306006, A316476, A328672, A328867, A328868.

b:= proc(n, j, s) local ok, i;
      if n=0 then 1
    elif j<2 then 0
    else ok:= true;
         for i in s while ok do ok:= evalb(igcd(i, j)<>1) od;
         `if`(ok, add(b(n-j*k, j-1, [s[], j]), k=1..n/j), 0) +b(n, j-1, s)
      fi
    end:
a:= n-> b(n, n, []):
seq(a(n), n=0..62);

b[n_, j_, s_] := Module[{ok, i, is}, Which[n == 0, 1, j < 2, 0, True, ok = True; For[is = 1, is <= Length[s] && ok, is++, i = s[[is]]; ok = GCD[i, j] != 1]; If[ok, Sum[b[n-j*k, j-1, Append[s, j]], {k, 1, n/j}], 0] + b[n, j-1, s]]]; a[n_] := b[n, n, {}]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 26 2013, translated from Maple *)
Table[Length[Select[IntegerPartitions[n],And[And@@(GCD[##]>1&)@@@Select[Tuples[Union[#],2],LessEqual@@#&]]&]],{n,0,20}] (* Gus Wiseman, Nov 04 2019 *)

a(n > 0) = A328673(n) - 1. - Gus Wiseman, Nov 04 2019

A319765 Number of non-isomorphic intersecting multiset partitions of weight n whose dual is also an intersecting multiset partition.

Original entry on oeis.org

1, 1, 3, 6, 15, 31, 74, 156, 358, 792, 1821

Offset: 0

Gus Wiseman, Sep 27 2018

The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
A multiset partition is intersecting iff no two parts are disjoint. The dual of a multiset partition is intersecting iff every pair of distinct vertices appear together in some part.
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(4) = 15 multiset partitions:
1: {{1}}
2: {{1,1}}
   {{1,2}}
   {{1},{1}}
3: {{1,1,1}}
   {{1,2,2}}
   {{1,2,3}}
   {{1},{1,1}}
   {{2},{1,2}}
   {{1},{1},{1}}
4: {{1,1,1,1}}
   {{1,1,2,2}}
   {{1,2,2,2}}
   {{1,2,3,3}}
   {{1,2,3,4}}
   {{1},{1,1,1}}
   {{1},{1,2,2}}
   {{2},{1,2,2}}
   {{3},{1,2,3}}
   {{1,1},{1,1}}
   {{1,2},{1,2}}
   {{1,2},{2,2}}
   {{1},{1},{1,1}}
   {{2},{2},{1,2}}
   {{1},{1},{1},{1}}

Cf. A007716, A281116, A283877, A305854, A306006, A316980, A316983, A317757, A319616.

Cf. A319752, A319766, A319767, A319768, A319769, A319773, A319774.

A319759 Number of non-isomorphic intersecting multiset partitions of weight n with empty intersection.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 2, 13, 49, 199

Offset: 0

Gus Wiseman, Sep 27 2018

A multiset partition is intersecting if no two parts are disjoint. 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(6) = 1 through a(8) = 13 multiset partitions:
6: {{1,2},{1,3},{2,3}}
7: {{1,2},{1,3},{2,3,3}}
   {{1,3},{1,4},{2,3,4}}
8: {{1,2},{1,3},{2,2,3,3}}
   {{1,2},{1,3},{2,3,3,3}}
   {{1,2},{1,3},{2,3,4,4}}
   {{1,2},{1,3,3},{2,3,3}}
   {{1,2},{1,3,4},{2,3,4}}
   {{1,3},{1,4},{2,3,4,4}}
   {{1,3},{1,1,2},{2,3,3}}
   {{1,3},{1,2,2},{2,3,3}}
   {{1,4},{1,5},{2,3,4,5}}
   {{2,3},{1,2,4},{3,4,4}}
   {{2,4},{1,2,3},{3,4,4}}
   {{2,4},{1,2,5},{3,4,5}}
   {{1,2},{1,3},{2,3},{2,3}}

Cf. A007716, A283877, A305854, A306006, A317757, A318715, A318717.

Cf. A319752, A319762, A319763, A319764, A319765, A319779, A319781.

A327039 Number of set-systems covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 2, 7, 88, 25421, 2077323118, 9221293242272922067, 170141182628636920942528022609657505092

Offset: 0

Gus Wiseman, Aug 17 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence counts set-systems that are cointersecting, meaning their dual is pairwise intersecting.

			The a(0) = 1 through a(2) = 7 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

The unlabeled multiset partition version is A319752.
The BII-numbers of these set-systems are A326853.
The pairwise intersecting case is A327038.
The covering case is A327040.
The case where the dual is strict is A327052.
Cf. A058891, A306006, A319765, A327020, A327053.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,3}]

Binomial transform of A327040.

a(5)-a(7) from Christian Sievers, Oct 22 2023

A327040 Number of set-systems covering n vertices, every two of which appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 4, 72, 25104, 2077196832, 9221293229809363008, 170141182628636920877978969957369949312

Offset: 0

Gus Wiseman, Aug 18 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence counts covering set-systems that are cointersecting, meaning their dual is pairwise intersecting.

			The a(0) = 1 through a(2) = 4 set-systems:
  {}  {{1}}  {{1,2}}
             {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

The unlabeled multiset partition version is A319752.
The BII-numbers of these set-systems are A326853.
The antichain case is A327020.
The pairwise intersecting case is A327037.
The non-covering version is A327039.
The case where the dual is strict is A327053.
Cf. A003465, A305843, A305844, A306006, A319774, A327052.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,3}]

Inverse binomial transform of A327039.

a(5)-a(7) from Christian Sievers, Oct 22 2023

A328867 Heinz numbers of integer partitions in which no two distinct parts are relatively prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 21, 23, 25, 27, 29, 31, 32, 37, 39, 41, 43, 47, 49, 53, 57, 59, 61, 63, 64, 65, 67, 71, 73, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 111, 113, 115, 117, 121, 125, 127, 128, 129, 131, 133, 137, 139, 147, 149

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

A partition with no two distinct parts relatively prime is said to be intersecting.

			The sequence of terms together with their prime indices begins:
    1: {}
    2: {1}
    3: {2}
    4: {1,1}
    5: {3}
    7: {4}
    8: {1,1,1}
    9: {2,2}
   11: {5}
   13: {6}
   16: {1,1,1,1}
   17: {7}
   19: {8}
   21: {2,4}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   32: {1,1,1,1,1}

These are the Heinz numbers of the partitions counted by A328673.
The strict case is A318719.
The relatively prime version is A328868.
A ranking using binary indices is A326910.
The version for non-isomorphic multiset partitions is A319752.
The version for divisibility (instead of relative primality) is A316476.
Cf. A000837, A056239, A112798, A200976, A289509, A303283, A305843, A318715, A318716, A328336.

Select[Range[100],And@@(GCD[##]>1&)@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A337667 Number of compositions of n where any two parts have a common divisor > 1.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 38, 1, 65, 19, 128, 1, 284, 1, 518, 67, 1025, 1, 2168, 16, 4097, 256, 8198, 1, 16907, 7, 32768, 1027, 65537, 79, 133088, 19, 262145, 4099, 524408, 25, 1056731, 51, 2097158, 16636, 4194317, 79, 8421248, 196, 16777712

Offset: 0

Gus Wiseman, Oct 05 2020

nonn

First differs from A178472 at a(31) = 7, a(31) = 1.

			The a(2) = 1 through a(10) = 17 compositions (A = 10):
   2   3   4    5   6     7   8      9     A
           22       24        26     36    28
                    33        44     63    46
                    42        62     333   55
                    222       224          64
                              242          82
                              422          226
                              2222         244
                                           262
                                           424
                                           442
                                           622
                                           2224
                                           2242
                                           2422
                                           4222
                                           22222

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..290

A101268 = 1 + A337462 is the pairwise coprime version.
A328673 = A200976 + 1 is the unordered version.
A337604 counts these compositions of length 3.
A337666 ranks these compositions.
A337694 gives Heinz numbers of the unordered version.
A337983 is the strict case.
A051185 counts intersecting set-systems, with spanning case A305843.
A318717 is the unordered strict case.
A319786 is the version for factorizations, with strict case A318749.
A327516 counts pairwise coprime partitions.
A333227 ranks pairwise coprime compositions.
A333228 ranks compositions whose distinct parts are pairwise coprime.
Cf. A051424, A082024, A178472, A284825, A319752, A327039, A337599, A337605, A337665.

stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],stabQ[#,CoprimeQ]&]],{n,0,15}]

A319755 Number of non-isomorphic intersecting set multipartitions (multisets of sets) of weight n.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 19, 30, 60, 107, 212

Offset: 0

Gus Wiseman, Sep 27 2018

A set multipartition is intersecting if no two parts are disjoint. The weight of a set multipartition 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(5) = 9 set multipartitions:
1: {{1}}
2: {{1,2}}
   {{1},{1}}
3: {{1,2,3}}
   {{2},{1,2}}
   {{1},{1},{1}}
4: {{1,2,3,4}}
   {{3},{1,2,3}}
   {{1,2},{1,2}}
   {{1,3},{2,3}}
   {{2},{2},{1,2}}
   {{1},{1},{1},{1}}
5: {{1,2,3,4,5}}
   {{4},{1,2,3,4}}
   {{1,4},{2,3,4}}
   {{2,3},{1,2,3}}
   {{2},{1,2},{1,2}}
   {{3},{3},{1,2,3}}
   {{3},{1,3},{2,3}}
   {{2},{2},{2},{1,2}}
   {{1},{1},{1},{1},{1}}

Cf. A007716, A049311, A283877, A305854, A306006, A316980, A319616.

Cf. A319748, A319752, A319759, A319760, A319765, A319779, A319787, A319789.

A324166 Number of totally crossing set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 18, 57, 207, 842, 3673, 17062, 84897

Offset: 0

Gus Wiseman, Feb 17 2019

A set partition is totally crossing if every pair of distinct blocks is of the form {{...x...y...}, {...z...t...}} for some x < z < y < t or z < x < t < y.

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

Cf. A000108 (non-crossing partitions), A000110, A000296, A002662, A016098 (crossing partitions), A054726, A099947 (topologically connected partitions), A305854, A306006, A306418, A306438, A319752.

Cf. A324170, A324171, A324172, A324173.

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

cp's OEIS Frontend

A328673 Number of integer partitions of n in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A200976 Number of partitions of n such that each pair of parts (if any) has a common factor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A319765 Number of non-isomorphic intersecting multiset partitions of weight n whose dual is also an intersecting multiset partition.

Views

Author

Keywords

Comments

Examples

Crossrefs

A319759 Number of non-isomorphic intersecting multiset partitions of weight n with empty intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327039 Number of set-systems covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327040 Number of set-systems covering n vertices, every two of which appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A328867 Heinz numbers of integer partitions in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337667 Number of compositions of n where any two parts have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319755 Number of non-isomorphic intersecting set multipartitions (multisets of sets) of weight n.