# Partial sums of partitions

Suppose I have two random partitions of $N.$ ("random" really means "the cycle type of a random permutation", but if there is an answer with any definition, I am interested). The question is: what is the probability is that no subset sum of the first partition is equal to any subset sum of the second partition? I seem to have trouble finding references...

-
How are you defining subset sum? For instance $5 = 1+2+2$, do you consider all possible sums that can be generated by subsets of $\{1,2\}$ or all sums that can be generated by $1$ and two copies of $2$? –  Vidit Nanda Jul 12 '13 at 16:46
$1$ and two $2$s... –  Igor Rivin Jul 12 '13 at 19:50
As they are partitions of N their sum coincide... Should it be proper subset sums? –  V. Delecroix Jul 14 '13 at 7:32
Yes, correct, proper subset sums... –  Igor Rivin Jul 14 '13 at 14:29

Here are two trivial observations while we wait for the real experts to completely solve this problem (paging Prof. Stanley...)

First, note that there is a reformulation of this question that might appeal more directly to partition theorists. Let $P(n)$ be the set of all partitions of $n$. Given partitions $\pi \in P(n)$ and $\rho \in P(m)$, we write $\rho \subset \pi$ to indicate containment as multi-sets, meaning that each part of $\rho$ is also a part of $\pi$. Note that if $\rho \subset \pi$ then we must have $m \leq n$ for obvious reasons.

For each $n$, let $\Gamma(n)$ be the set of partition-pairs $(\pi_1,\pi_2) \in P(n) \times P(n)$ for which there exists a triple $(m,\rho_1,\rho_2)$ with $m < n$, $\rho_j \in P(m)$ and $\rho_j \subset \pi_j$. This question is asking:

What is $1 - \frac{|\Gamma(n)|}{|P(n)|^2}$, where $|\cdot|$ indicates cardinality?

Secondly, one can compute $|\Gamma(n)|$ by hand for small $n$. It helps a lot, at least for tiny $n$, to note that $|\Gamma(n)| \geq |P(n-1)|^2$: the latter quantity counts those partitions of $n$ which contain $1$, so no two such partitions can hope to be subset-independent. Here are some values resulting from my (possibly erroneous) calculations:

$$|\Gamma(2)| = 2,\\ |\Gamma(3)| = 5,\\ |\Gamma(4)| = 15, \\ |\Gamma(5)| = 35.$$

I am not happy with the unique oeis entry for this sequence, but you might find the $20$ candidates for $|P(n)|^2 - |\Gamma(n)|$ much more promising, see here.

-
Interesting, thanks! (of course, this is a different distribution from what I had mentioned, but as I said, I will take anything :)) –  Igor Rivin Jul 14 '13 at 19:55
@IgorRivin Sorry, I have no idea what it means to have the cycle type of a random permutation, but presumably you can weight subsets of $P(n) \times P(n)$ by a measure different from this uniform "cardinality-ratio" and proceed as before. –  Vidit Nanda Jul 14 '13 at 20:16