A321729 - OEIS

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.

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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.

LINKS

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

FORMULA

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

EXAMPLE

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

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], Length[Select[spsu[ptnverts[#], ptnpos[#]], Function[p, Sort[Length/@p]==Sort[#]]]]>0&]], {n, 8}]

CROSSREFS

The complement is counted by A321728.