A339659 -id:A339659 - cp's OEIS frontend

A321728 Number of integer partitions of n whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition.

0, 0, 1, 1, 2, 3, 5, 7, 10, 14, 20, 28, 37, 50

Offset: 0

Gus Wiseman, Nov 18 2018

First differs from A000701 at a(11) = 28, A000701(11) = 27
A vertical section is a partial Young diagram with at most one square in each row.
Conjecture: a(n) is the number of non-half-loop-graphical partitions of n. An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex, to be distinguished from a full loop, which has two equal vertices.

			The a(2) = 1 through a(9) = 14 partitions whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition are the same as the non-half-loop-graphical partitions up to n = 9:
  (2)  (3)  (4)   (5)   (6)    (7)    (8)     (9)
            (31)  (32)  (33)   (43)   (44)    (54)
                  (41)  (42)   (52)   (53)    (63)
                        (51)   (61)   (62)    (72)
                        (411)  (331)  (71)    (81)
                               (421)  (422)   (432)
                               (511)  (431)   (441)
                                      (521)   (522)
                                      (611)   (531)
                                      (5111)  (621)
                                              (711)
                                              (4311)
                                              (5211)
                                              (6111)
For example, a complete list of all half/full-loop-graphs with degrees y = (4,3,1) is the following:
  {{1,1},{1,2},{1,3},{2,2}}
  {{1},{2},{1,1},{1,2},{2,3}}
  {{1},{2},{1,1},{1,3},{2,2}}
  {{1},{3},{1,1},{1,2},{2,2}}
None of these is a half-loop-graph, as they have full loops (x,x), so y is counted under a(8).

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

The complement is counted by A321729.
Cf. A000110, A000258, A000700, A000701, A008277, A046682, A319616, A321730, A321737, A321738.
The following pertain to the conjecture.
Half-loop-graphical partitions by length are A029889 or A339843 (covering).
The version for full loops is A339655.
A027187 counts partitions of even length, with Heinz numbers A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs, ranked by A340018/A340019.
A339659 counts graphical partitions of 2n into k parts.
Cf. A006129, A025065, A062740, A095268, A096373, A167171, A320461, A338915, A339842, A339844, A339845.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
ptnpos[y_]:=Position[Table[1,{#}]&/@y,1];
ptnverts[y_]:=Select[Join@@Table[Subsets[ptnpos[y],{k}],{k,Reverse[Union[y]]}],UnsameQ@@First/@#&];
Table[Length[Select[IntegerPartitions[n],Select[spsu[ptnverts[#],ptnpos[#]],Function[p,Sort[Length/@p]==Sort[#]]]=={}&]],{n,8}]

a(n) is the number of integer partitions y of n such that the coefficient of m(y) in e(y) is zero, where m is monomial and e is elementary symmetric functions.

a(n) = A000041(n) - A321729(n).

A339844 Number of distinct sorted degree sequences among all n-vertex loop-graphs.

Original entry on oeis.org

1, 2, 6, 16, 51, 162, 554, 1918, 6843, 24688, 90342, 333308, 1239725

Offset: 0

Gus Wiseman, Dec 27 2020

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as loop-graphical partitions (A339656). An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct pairs, i.e. into a set of loops and edges;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The a(0) = 1 through a(3) = 16 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)
      (2)  (0,2)  (0,0,2)
           (1,1)  (0,1,1)
           (1,3)  (0,1,3)
           (2,2)  (0,2,2)
           (3,3)  (0,3,3)
                  (1,1,2)
                  (1,1,4)
                  (1,2,3)
                  (1,3,4)
                  (2,2,2)
                  (2,2,4)
                  (2,3,3)
                  (2,4,4)
                  (3,3,4)
                  (4,4,4)
For example, the loop-graphs
  {{1,1},{2,2},{3,3},{1,2}}
  {{1,1},{2,2},{3,3},{1,3}}
  {{1,1},{2,2},{3,3},{2,3}}
  {{1,1},{2,2},{1,3},{2,3}}
  {{1,1},{3,3},{1,2},{2,3}}
  {{2,2},{3,3},{1,2},{1,3}}
all have degrees y = (3,3,2), so y is counted under a(3).

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross references.
The version without loops is A004251, with covering case A095268.
The half-loop version is A029889, with covering case A339843.
Loop-graphs are counted by A322661 and ranked by A320461 and A340020.
The covering case (no zeros) is A339845.
A007717 counts unlabeled multiset partitions into pairs.
A027187 counts partitions of even length, with Heinz numbers A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A101048 counts partitions into semiprimes.
A339655 counts non-loop-graphical partitions of 2n.
A339656 counts loop-graphical partitions of 2n.
A339659 counts graphical partitions of 2n into k parts.
Cf. A001358, A006125, A006129, A062740, A338898, A339841.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Subsets[Subsets[Range[n],{1,2}]/.{x_Integer}:>{x,x}]]],{n,0,5}]

a(7)-a(12) from Andrew Howroyd, Jan 10 2024

A321729 Number of integer partitions of n whose Young diagram can be partitioned into vertical sections of the same sizes as the parts of the original partition.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 8, 12, 16, 22, 28, 40, 51

Offset: 0

Gus Wiseman, Nov 18 2018

First differs from A046682 at a(11) = 28, A046682(11) = 29.
A vertical section is a partial Young diagram with at most one square in each row. For example, a suitable partition (shown as a coloring by positive integers) of the Young diagram of (322) is:
  1 2 3
  1 2
  2 3
Conjecture: a(n) is the number of half-loop-graphical partitions of n. An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex, to be distinguished from a full loop, which has two equal vertices.

			The a(1) = 1 through a(8) = 12 partitions whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition are the same as the half-loop-graphical partitions up to n = 8:
  (1)  (11)  (21)   (22)    (221)    (222)     (322)      (332)
             (111)  (211)   (311)    (321)     (2221)     (2222)
                    (1111)  (2111)   (2211)    (3211)     (3221)
                            (11111)  (3111)    (4111)     (3311)
                                     (21111)   (22111)    (4211)
                                     (111111)  (31111)    (22211)
                                               (211111)   (32111)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(7).

The complement is counted by A321728.
Cf. A000110, A000258, A000700, A000701, A006052, A007016, A008277, A046682, A319056, A319616, A321730, A321737, A321738.
The following pertain to the conjecture.
Half-loop-graphical partitions by length are A029889 or A339843 (covering).
The version for full loops is A339656.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs, ranked by A340018/A340019.
A339659 is a triangle counting graphical partitions by length.
Cf. A006129, A025065, A062740, A095268, A096373, A167171, A320461, A338915, A339842, A339844, A339845.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
ptnpos[y_]:=Position[Table[1,{#}]&/@y,1];
ptnverts[y_]:=Select[Join@@Table[Subsets[ptnpos[y],{k}],{k,Reverse[Union[y]]}],UnsameQ@@First/@#&];
Table[Length[Select[IntegerPartitions[n],Length[Select[spsu[ptnverts[#],ptnpos[#]],Function[p,Sort[Length/@p]==Sort[#]]]]>0&]],{n,8}]

a(n) is the number of integer partitions y of n such that the coefficient of m(y) in e(y) is nonzero, where m is monomial symmetric functions and e is elementary symmetric functions.

a(n) = A000041(n) - A321728(n).

A339845 Number of distinct sorted degree sequences among all n-vertex loop-graphs without isolated vertices.

Original entry on oeis.org

1, 1, 4, 10, 35, 111, 392, 1364, 4925, 17845, 65654, 242966, 906417

Offset: 0

Gus Wiseman, Dec 27 2020

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as loop-graphical partitions (A339656). An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct pairs, i.e. into a set of loops and edges;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The a(0) = 1 through a(3) = 10 sorted degree sequences:
  ()  (2)  (1,1)  (1,1,2)
           (1,3)  (1,1,4)
           (2,2)  (1,2,3)
           (3,3)  (1,3,4)
                  (2,2,2)
                  (2,2,4)
                  (2,3,3)
                  (2,4,4)
                  (3,3,4)
                  (4,4,4)
For example, the loop-graphs
  {{1,1},{2,2},{3,3},{1,2}}
  {{1,1},{2,2},{3,3},{1,3}}
  {{1,1},{2,2},{3,3},{2,3}}
  {{1,1},{2,2},{1,3},{2,3}}
  {{1,1},{3,3},{1,2},{2,3}}
  {{2,2},{3,3},{1,2},{1,3}}
all have degrees y = (3,3,2), so y is counted under a(3).

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross references.
The version without loops is A004251, with covering case A095268.
The half-loop version is A029889, with covering case A339843.
Loop-graphs are counted by A322661 and ranked by A320461 and A340020.
Counting the same partitions by sum gives A339656.
These partitions are ranked by A339658.
The non-covering case (zeros allowed) is A339844.
A007717 counts unlabeled multiset partitions into pairs.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A101048 counts partitions into semiprimes.
A339655 counts non-loop-graphical partitions of 2n.
A339659 counts graphical partitions of 2n into k parts.
Cf. A001358, A006125, A006129, A062740, A338898, A339841.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{1,2}]/.{x_Integer}:>{x,x}],Union@@#==Range[n]&]]],{n,0,5}]

a(n) = A339844(n) - A339844(n-1) for n > 0. - Andrew Howroyd, Jan 10 2024

a(7)-a(12) from Andrew Howroyd, Jan 10 2024

A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

Original entry on oeis.org

1, 1, 3, 9, 29, 97, 336, 1188, 4275, 15579, 57358, 212908, 795657, 2990221, 11291665, 42814783, 162920417, 621885767, 2380348729

Offset: 0

Gus Wiseman, Dec 27 2020

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as half-loop-graphical partitions (A321729). An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops or edges;
(2) n can be factored into distinct primes or squarefree semiprimes;
(3) the prime signature of n is half-loop-graphical.

			The a(0) = 1 through a(3) = 9 sorted degree sequences:
  ()  (1)  (1,1)  (1,1,1)
           (2,1)  (2,1,1)
           (2,2)  (2,2,1)
                  (2,2,2)
                  (3,1,1)
                  (3,2,1)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(3).

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross references.
The version for simple graphs is A004251, covering: A095268.
The non-covering version (it allows isolated vertices) is A029889.
The same partitions counted by sum are conjectured to be A321729.
These graphs are counted by A006125 shifted left, covering: A322661.
The version for full loops is A339844, covering: A339845.
These graphs are ranked by A340018 and A340019.
A006125 counts labeled simple graphs, covering: A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A339659 counts graphical partitions of 2n into k parts.
Cf. A062740, A096373, A167171, A320461, A320893, A320921, A320923, A338915, A339560, A339841, A339842.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{1,2}]],Union@@#==Range[n]&]]],{n,0,5}]

a(n) = A029889(n) - A029889(n-1) for n > 0. - Andrew Howroyd, Jan 10 2024

a(7)-a(18) added (using A029889) by Andrew Howroyd, Jan 10 2024

A339842 Heinz numbers of non-graphical, multigraphical integer partitions of even numbers.

Original entry on oeis.org

9, 25, 30, 49, 63, 70, 75, 84, 100, 121, 147, 154, 165, 169, 175, 189, 196, 198, 210, 220, 250, 264, 273, 280, 286, 289, 325, 343, 351, 361, 363, 364, 385, 390, 441, 442, 462, 468, 484, 490, 495, 507, 520, 525, 529, 550, 561, 588, 594, 595, 616, 624, 637, 646

Offset: 1

Gus Wiseman, Dec 27 2020

nonn

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

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The sequence of terms together with their prime indices begins:
      9: {2,2}        189: {2,2,2,4}      363: {2,5,5}
     25: {3,3}        196: {1,1,4,4}      364: {1,1,4,6}
     30: {1,2,3}      198: {1,2,2,5}      385: {3,4,5}
     49: {4,4}        210: {1,2,3,4}      390: {1,2,3,6}
     63: {2,2,4}      220: {1,1,3,5}      441: {2,2,4,4}
     70: {1,3,4}      250: {1,3,3,3}      442: {1,6,7}
     75: {2,3,3}      264: {1,1,1,2,5}    462: {1,2,4,5}
     84: {1,1,2,4}    273: {2,4,6}        468: {1,1,2,2,6}
    100: {1,1,3,3}    280: {1,1,1,3,4}    484: {1,1,5,5}
    121: {5,5}        286: {1,5,6}        490: {1,3,4,4}
    147: {2,4,4}      289: {7,7}          495: {2,2,3,5}
    154: {1,4,5}      325: {3,3,6}        507: {2,6,6}
    165: {2,3,5}      343: {4,4,4}        520: {1,1,1,3,6}
    169: {6,6}        351: {2,2,2,6}      525: {2,3,3,4}
    175: {3,3,4}      361: {8,8}          529: {9,9}
For example, a complete list of all multigraphs with degrees (4,2,2,2) is:
  {{1,2},{1,2},{1,3},{1,4},{3,4}}
  {{1,2},{1,3},{1,3},{1,4},{2,4}}
  {{1,2},{1,3},{1,4},{1,4},{2,3}}
Since none of these is strict, i.e., a graph, the Heinz number 189 is in the sequence.

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross references.
Distinct prime shadows (images under A181819) of A340017.
A000070 counts non-multigraphical partitions (A339620).
A000569 counts graphical partitions (A320922).
A027187 counts partitions of even length (A028260).
A058696 counts partitions of even numbers (A300061).
A096373 cannot be partitioned into strict pairs.
A209816 counts multigraphical partitions (A320924).
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A320893 can be partitioned into distinct pairs but not into strict pairs.
A339560 can be partitioned into distinct strict pairs.
A339617 counts non-graphical partitions of 2n (A339618).
A339659 counts graphical partitions of 2n into k parts.
Cf. A004251, A006129, A007717, A056239, A095268, A112798, A181821, A305936, A318284, A339559.

strr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strr[n/d],Min@@#>=d&]],{d,Select[Divisors[n],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
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[#]]]&& Select[strr[Times@@Prime/@nrmptn[#]],UnsameQ@@#&]=={}&&strr[Times@@Prime/@nrmptn[#]]!={}&]

Equals A320924 /\ A339618.

Equals A320924 \ A320922.

cp's OEIS Frontend

A321728 Number of integer partitions of n whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339844 Number of distinct sorted degree sequences among all n-vertex loop-graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A321729 Number of integer partitions of n whose Young diagram can be partitioned into vertical sections of the same sizes as the parts of the original partition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A339845 Number of distinct sorted degree sequences among all n-vertex loop-graphs without isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339842 Heinz numbers of non-graphical, multigraphical integer partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula