Given a labeling of the set of partitions of $n$ with $k\leq n$ parts (numbering choose$(n,k)$), and comparing all pairs of partitions from this set (numbering choose$(n,k)^2$ since we allow a partition to be repeated in the pair, and we count distinct orderings (e.g. partition pair 1,2 is distinct from partition pair 2,1)), how many of these pairs have exactly $m$ elements in common, where $1 \leq m \leq k$, irrespective of the position of these common elements within the two compared partitions?

There are of course only choose$(n,k)$ pairs of partitions that have $m=k$ elements in common (i.e. the pairs of identical partitions!). What about for other values of $m$? I.e. I would like the function $Number$($m$-elements in common$)=f_{m}(n,k)$, where $f_m$ is some closed-form function giving the number of pairs of partitions.

Any help appreciated! Also, this is my first post so advice on better question formatting if needed would also be appreciated.

Bonus: compute the same function but for comparison of pairs of partitions with unequal parts $k_1\neq k_2$, where in this case $\max(m)=\min(k_1,k_2)$.


1 Answer 1


Take one of the subsets. Fix $m$ of its elements that will be shared, and fill in the rest with elements not in this subset. By symmetry, this will be true for all of the left subsets of the pairs.

$$f_m(n,k) = \binom{n}{k}\binom{n-k}{k-m}\binom{k}{m}$$

Apply identical reasoning to the second part, where $k_1$ is smaller to obtain


You seem unclear on whether these are ordered or unordered subsets, but most of your math suggests that they are unordered, and that is reflected in the solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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