[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
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).
More information about the SeqFan
mailing list