[seqfan] Summing partitions

[franktaw at netscape.net]

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 
addends, the
      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.

Franklin T. Adams-Watters

Incidentally, someone else may have pointed this out, but:
>This leads to the observation
>a000041(2n) - a002219(n) >= sum_{k=0..n-1} a000041(k)
>(and the two sides of this inequality could themselves be added to the 
OEIS).

The right hand side is A000070 (right-shifted).