A147878 -id:A147878 - cp's OEIS frontend

A339620 Heinz numbers of non-multigraphical partitions of even numbers.

3, 7, 10, 13, 19, 21, 22, 28, 29, 34, 37, 39, 43, 46, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 88, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 155, 156, 159, 163, 166, 171, 172, 173

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

An integer partition is non-multigraphical if it does not comprise the multiset of vertex-degrees of any multigraph (multiset of non-loop edges). Multigraphical partitions are counted by A209816, non-multigraphical partitions by A000070.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime indices of n can be partitioned into strict pairs (a multiset of edges);
(2) n can be factored into squarefree semiprimes;
(3) the unordered prime signature of n is multigraphical.

			The sequence of terms together with their prime indices begins:
      3: {2}         53: {16}          94: {1,15}
      7: {4}         55: {3,5}        101: {26}
     10: {1,3}       57: {2,8}        102: {1,2,7}
     13: {6}         61: {18}         107: {28}
     19: {8}         62: {1,11}       111: {2,12}
     21: {2,4}       66: {1,2,5}      113: {30}
     22: {1,5}       71: {20}         115: {3,9}
     28: {1,1,4}     76: {1,1,8}      116: {1,1,10}
     29: {10}        79: {22}         117: {2,2,6}
     34: {1,7}       82: {1,13}       118: {1,17}
     37: {12}        85: {3,7}        129: {2,14}
     39: {2,6}       87: {2,10}       130: {1,3,6}
     43: {14}        88: {1,1,1,5}    131: {32}
     46: {1,9}       89: {24}         133: {4,8}
     52: {1,1,6}     91: {4,6}        134: {1,19}
For example, a complete lists of all loop-multigraphs with degrees (5,2,1) is:
  {{1,1},{1,1},{1,2},{2,3}}
  {{1,1},{1,1},{1,3},{2,2}}
  {{1,1},{1,2},{1,2},{1,3}},
but since none of these is a multigraph (they have loops), the Heinz number 66 belongs to the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A000070 counts these partitions.
A300061 is a superset.
A320891 has image under A181819 equal to this set of terms.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620 [this sequence]).
- A209816 counts multigraphical partitions (A320924).
- A147878 counts connected multigraphical partitions (A320925).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A005117, A007717, A030229, A050320, A056239, A112798, A320655, A338899, A339113, A339661.

prpts[m_]:=If[Length[m]==0,{{}},Join@@Table[Prepend[#,ipr]&/@prpts[Fold[DeleteCases[#1,#2,{1},1]&,m,ipr]],{ipr,Select[Subsets[Union[m],{2}],MemberQ[#,m[[1]]]&]}]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],EvenQ[Length[nrmptn[#]]]&&prpts[nrmptn[#]]=={}&]

Equals A300061 \ A320924.

For all n, both A181821(a(n)) and A304660(a(n)) belong to A320891.

A339659 Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 2, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 5, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 7, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 4, 9, 11, 11, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 2, 11, 15, 17, 15, 11, 7, 5, 3, 2, 1, 1

Offset: 0

Gus Wiseman, Dec 18 2020

Conjecture: The column sums 1, 0, 1, 2, 7, 20, 67, ... are given by A304787.

An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. Graphical partitions are counted by A000569.

			Triangle begins:
  1
  0 0 1
  0 0 0 1 1
  0 0 0 1 2 1 1
  0 0 0 0 2 3 2 1 1
  0 0 0 0 1 4 5 3 2 1 1
  0 0 0 0 1 4 7 7 5 3 2 1 1
For example, row n = 5 counts the following partitions:
  3322  22222  222211  2221111  22111111  211111111  1111111111
        32221  322111  3211111  31111111
        33211  331111  4111111
        42211  421111
               511111

A000569 gives the row sums.
A004250 is the central column.
A005408 gives the row lengths.
A008284/A072233 is the version counting all partitions.
A259873 is the left half of the triangle.
A309356 is a universal embedding.
A027187 counts partitions of even length.
A339559 = partitions that cannot be partitioned into distinct strict pairs.
A339560 = partitions that can be partitioned into distinct strict pairs.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A000569 counts graphical partitions (A320922).
- A058696 counts partitions of 2n (A300061).
- A147878 counts connected multigraphical partitions (A320925).
- A209816 counts multigraphical partitions (A320924).
- A320921 counts connected graphical partitions (A320923).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
- A339617 counts non-graphical partitions of 2n (A339618).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
Cf. A000219, A002100, A006881, A007717, A025065, A320656, A320894, A338914, A338916, A339561, A339661.

prpts[m_]:=If[Length[m]==0,{{}},Join@@Table[Prepend[#,ipr]&/@prpts[Fold[DeleteCases[#1,#2,{1},1]&,m,ipr]],{ipr,Subsets[Union[m],{2}]}]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Length[Union[#]]==k&&Select[prpts[#],UnsameQ@@#&]!={}&]],{n,0,5},{k,0,2*n}]

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Original entry on oeis.org

1, 1, 2, 6, 20, 103, 759

Offset: 1

Gus Wiseman, Nov 21 2018

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions p of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).

			The a(4) = 6 connected chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                    m(1111)
           m(211) + m(1111)
          2m(211) + m(1111)
  m(22) + 2m(211) + m(1111)
  m(22) + 3m(211) + m(1111)
  m(31) + 3m(211) + m(1111)

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Gus Wiseman, A partition of connected graphs, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].

First differs from A079457 at a(7) = 759, A079457(7) = 706.

Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
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[Union[chromSF/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,6}]

A320925 Heinz numbers of connected multigraphical partitions.

Original entry on oeis.org

4, 9, 12, 25, 27, 30, 36, 40, 49, 63, 70, 75, 81, 84, 90, 100, 108, 112, 120, 121, 147, 154, 165, 169, 175, 189, 196, 198, 210, 220, 225, 243, 250, 252, 264, 270, 273, 280, 286, 289, 300, 324, 325, 336, 343, 351, 352, 360, 361, 363, 364, 385, 390, 400, 441

Offset: 1

Gus Wiseman, Oct 24 2018

nonn

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

An integer partition is connected and multigraphical if it comprises the multiset of vertex-degrees of some connected multigraph.

			The sequence of all connected multigraphical partitions begins: (11), (22), (211), (33), (222), (321), (2211), (3111), (44), (422), (431), (332), (2222), (4211), (3221), (3311), (22211), (41111), (32111).

Cf. A000070, A000569, A007717, A056239, A112798, A147878, A209816, A300061, A320459, A320911, A320921, A320923, A320924.

prptns[m_]:=Union[Sort/@If[Length[m]==0,{{}},Join@@Table[Prepend[#,m[[ipr]]]&/@prptns[Delete[m,List/@ipr]],{ipr,Select[Prepend[{#},1]&/@Select[Range[2,Length[m]],m[[#]]>m[[#-1]]&],UnsameQ@@m[[#]]&]}]]];
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]]]]]]]]];
Select[Range[1000],Select[prptns[Flatten[MapIndexed[Table[#2,{#1}]&,If[#==1,{},Flatten[Cases[FactorInteger[#],{p_,k_}:>Table[PrimePi[p],{k}]]]]]]],Length[csm[#]]==1&]!={}&]

A321176 Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 5, 7, 10, 15, 21, 28

Offset: 0

Gus Wiseman, Oct 29 2018

A set system is a finite set of finite nonempty sets.

			The a(2) = 1 through a(9) = 15 partitions:
  (11)  (111)  (211)   (221)    (222)     (322)      (2222)      (333)
               (1111)  (2111)   (2211)    (2221)     (3221)      (3222)
                       (11111)  (3111)    (3211)     (3311)      (3321)
                                (21111)   (22111)    (22211)     (4221)
                                (111111)  (31111)    (32111)     (22221)
                                          (211111)   (41111)     (32211)
                                          (1111111)  (221111)    (33111)
                                                     (311111)    (42111)
                                                     (2111111)   (222111)
                                                     (11111111)  (321111)
                                                                 (411111)
                                                                 (2211111)
                                                                 (3111111)
                                                                 (21111111)
                                                                 (111111111)
The a(8) = 10 integer partitions together with a realizing set system for each (the parts of the partition count the appearances of each vertex in the set system):
     (41111): {{1,2},{1,3},{1,4},{1,5}}
      (3311): {{1,2},{1,2,3},{1,2,4}}
      (3221): {{1,2},{1,3},{1,2,3,4}}
     (32111): {{1,2},{1,3},{1,2,4,5}}
    (311111): {{1,2},{1,3},{1,4,5,6}}
      (2222): {{1,2},{3,4},{1,2,3,4}}
     (22211): {{1,2,3},{1,2,3,4,5}}
    (221111): {{1,2},{1,2,3,4,5,6}}
   (2111111): {{1,2},{1,3,4,5,6,7}}
  (11111111): {{1,2,3,4,5,6,7,8}}

Cf. A000070, A000569, A147878, A209816, A283877, A306005, A318361, A320922, A320923, A320924, A321177.

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]]]];
hyp[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,UnsameQ@@#,Min@@Length/@#>1]&];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[n],hyp[#]!={}&]],{n,8}]

A147877 The number of degree sequences with degree sum 2n representable by a non-separable graph (with multiple edges allowed).

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 15, 25, 43, 70, 113, 181, 283, 436, 666, 999, 1483, 2179, 3166, 4556, 6504, 9200, 12918, 18011, 24938, 34308, 46928, 63815, 86324, 116187, 155626, 207502, 275491, 364226, 479660, 629305, 822655, 1071694, 1391531, 1801041, 2323958, 2989883

Offset: 1

James Sellers, Nov 16 2008

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
O. J. Rodseth, J. A. Sellers and H. Tverberg, Enumeration of the Degree Sequences of Non-Separable Graphs and Connected Graphs, European Journal of Combinatorics 30 (2009), 1301-1317.

Cf. A147878.

with(combinat): seq(numbpart(2*m) - numbpart(2*m - 1) - add(numbpart(j), j = 0 .. m-2), m=1..60);

a(n) = numbpart(2*n) - numbpart(2*n-1) - sum(j=0, n-2, numbpart(j)); \\ Michel Marcus, Nov 04 2016

a(n) = p(2n) - p(2n-1) - Sum_{j=0..n-2} p(j).
a(n) = A000041(2*n) - A000041(2*n-1) - A000070(n) + A000041(n) + A000041(n-1). - Vaclav Kotesovec, Nov 05 2016
a(n) ~ exp(2*Pi*sqrt(n/3))*Pi/(48*n^(3/2)) * (1 - (3*sqrt(3)/(2*Pi) + 13*Pi/(48*sqrt(3)))/sqrt(n)). - Vaclav Kotesovec, Nov 05 2016

Offset corrected by Michel Marcus, Nov 04 2016

A321184 Number of integer partitions of n that are the vertex-degrees of some multiset of nonempty sets, none of which is a proper subset of any other, with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 3, 2, 7, 6, 15, 15, 30

Offset: 0

Gus Wiseman, Oct 29 2018

			The a(2) = 1 through a(8) = 15 partitions:
  (11)  (111)  (22)    (2111)   (33)      (2221)     (44)
               (211)   (11111)  (222)     (3211)     (332)
               (1111)           (321)     (22111)    (422)
                                (2211)    (31111)    (431)
                                (3111)    (211111)   (2222)
                                (21111)   (1111111)  (3221)
                                (111111)             (3311)
                                                     (4211)
                                                     (22211)
                                                     (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)
The a(6) = 7 integer partitions together with a realizing multi-antichain of each (the parts of the partition count the appearances of each vertex in the multi-antichain):
      (33): {{1,2},{1,2},{1,2}}
     (321): {{1,2},{1,2},{1,3}}
    (3111): {{1,2},{1,3},{1,4}}
     (222): {{1,2,3},{1,2,3}}
    (2211): {{1,2,3},{1,2,4}}
   (21111): {{1,2},{1,3,4,5}}
  (111111): {{1,2,3,4,5,6}}

Cf. A000070, A000569, A006126, A096827, A147878, A209816, A283877, A318360, A319719, A319721, A320799, A320921, A321176.

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]]]];
multanti[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,Min@@Length/@#>1,stableQ[#]]&];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[n],multanti[#]!={}&]],{n,8}]

cp's OEIS Frontend

A339620 Heinz numbers of non-multigraphical partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339659 Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A320925 Heinz numbers of connected multigraphical partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A321176 Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A147877 The number of degree sequences with degree sum 2n representable by a non-separable graph (with multiple edges allowed).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A321184 Number of integer partitions of n that are the vertex-degrees of some multiset of nonempty sets, none of which is a proper subset of any other, with no singletons.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica