Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.