[seqfan] Summing partitions

franktaw at netscape.net franktaw at netscape.net
Mon Jul 9 21:49:28 CEST 2012

The discussion last month about A002219 brought to mind something
I was playing with a while ago, but didn't get far enough to start
submitting sequences.

We can define a non-deterministic sum of two partitions as a partition
where each part is either one of the parts of one the two addends, or
the sum of a part from each addend, with each addend part being used
exactly once. Alternatively, one can view this as splitting a partition
into
two, with each part either split between the two new partitions, or put
entirely into one of them. (This is again a non-deterministic
operation.)

Note that a partition P can be an addend to partition Q precisely when
P <= Q in the standard ordering.

A number of sequences suggest themselves:
* A table where T(n,k) is the number of possible sums of the n-th and
the k-th partition (in one of the canonical orderings).
* A table where T(n,k) is the number of ways to generate the n-th
partition as the sum of two partitions, one of size k.
- There are two variants of this: one with k from 0 to sum(P(n)), and
one with k from 0 to floor(sum(P(n))/2). These will differ for
T(2*k,k),
the first counts ordered pairs, the second counts unordered pairs.
- One could also look at the sums in more detail, e.g. for a sum
part
of size 3, if there are parts of size 3, 2, and 1 in both
part could be generated as 3+0, 2+1, 1+2, or 0+3.
* The row sums of the above: total ways to split the n-th partition.
* Row sums of these row sums: total ways to split all partitions of n.

Incidentally, someone else may have pointed this out, but: