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,5

Comments

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.

Links

Table of n, a(n) for n=0..13.

Eric Weisstein's World of Mathematics, Degree Sequence.

Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Formula

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

Example

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

Mathematica

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}]

Crossrefs

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.

Sequence in context: A027340 A000701 A123975 * A214077 A094984 A107332

Adjacent sequences: A321725 A321726 A321727 * A321729 A321730 A321731

Keyword

nonn,more

Author

Gus Wiseman, Nov 18 2018

Status

approved