Skip to main content
MathOverflow

Return to Question

spelling + two tags
Source Link
Jukka Kohonen
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

I am interested in a possible generalization of the following fact from combinatorics:

If $n<m$ then there are at least as many ways to partition a set of size $nm$ into $m$ sets each of size $n$ as there are ways to partition it into $n$ sets of size $m$.

Explicitly this just says that $\binom{nm}{n,n,\dots n}\frac{1}{m!} \ge \binom{nm}{m,m,\dots m}\frac{1}{n!}$ and the proof I know is using Sterling'sStirling's approximation (I'd be interested in seeing a more combinatorial proof if someone knows one).

Anyway the question I have is does this still hold if I instead have a multiset of size $nm$ and my partitions are multiset partitions in the sense that each element appears in total as many times as it did in the original multiset?

I am interested in a possible generalization of the following fact from combinatorics:

If $n<m$ then there are at least as many ways to partition a set of size $nm$ into $m$ sets each of size $n$ as there are ways to partition it into $n$ sets of size $m$.

Explicitly this just says that $\binom{nm}{n,n,\dots n}\frac{1}{m!} \ge \binom{nm}{m,m,\dots m}\frac{1}{n!}$ and the proof I know is using Sterling's approximation (I'd be interested in seeing a more combinatorial proof if someone knows one).

Anyway the question I have is does this still hold if I instead have a multiset of size $nm$ and my partitions are multiset partitions in the sense that each element appears in total as many times as it did in the original multiset?

I am interested in a possible generalization of the following fact from combinatorics:

If $n<m$ then there are at least as many ways to partition a set of size $nm$ into $m$ sets each of size $n$ as there are ways to partition it into $n$ sets of size $m$.

Explicitly this just says that $\binom{nm}{n,n,\dots n}\frac{1}{m!} \ge \binom{nm}{m,m,\dots m}\frac{1}{n!}$ and the proof I know is using Stirling's approximation (I'd be interested in seeing a more combinatorial proof if someone knows one).

Anyway the question I have is does this still hold if I instead have a multiset of size $nm$ and my partitions are multiset partitions in the sense that each element appears in total as many times as it did in the original multiset?

Source Link
Nate
Nate
  • 2.2k
  • 14
  • 16

Partitions of a multiset into equal parts

I am interested in a possible generalization of the following fact from combinatorics:

If $n<m$ then there are at least as many ways to partition a set of size $nm$ into $m$ sets each of size $n$ as there are ways to partition it into $n$ sets of size $m$.

Explicitly this just says that $\binom{nm}{n,n,\dots n}\frac{1}{m!} \ge \binom{nm}{m,m,\dots m}\frac{1}{n!}$ and the proof I know is using Sterling's approximation (I'd be interested in seeing a more combinatorial proof if someone knows one).

Anyway the question I have is does this still hold if I instead have a multiset of size $nm$ and my partitions are multiset partitions in the sense that each element appears in total as many times as it did in the original multiset?