Improving clarity and argumentation with hard-to-describe combinatorial proof

126 Views Asked by At

I'm doing undergraduate research and the content of my paper depends on the following lemma. I tried something like a combinatorial proof, but it is clearly not rigorous, partly because my argument is hard to describe. How can I improve my proof?

Lemma. Let $p_i$ give the $i$th prime. Then the number of ways we can uniquely distribute $k_1$ [color-one] balls, $k_2$ [color-two] balls, $k_3$ [color-three] balls, ... $k_f$ [color-$f$] balls into $n$ indistinguishable boxes is equal to the number of ways to factor $$\prod_{i=1}^f p_i^{k_i}$$ into $n$ distinct factors.

Before we begin our proof, we start with a demonstration.

Suppose we sought to uniquely distribute 2 blue balls and 1 red ball into 3 indistinguishable boxes. We'd have the following distributions (each distribution has its own row):

$$[\color{blue}{* *}\color{red}{*}] \, \, \, []\, \, \,[] $$

$$[\color{blue}{* *}] \, \, \, [\color{red} *] \, \, \, []$$

$$[\color{blue} *] \, \, \, [\color{blue} * \color{red} *] \, \, \, []$$

$$[\color{blue} *] \, \, \, [ \color{blue} * ] \, \, \, [ \color{red} *]$$

Now suppose we sought to generate unique factorizations of $12=2^2 \cdot 3^1$ into $3$ factors. We'd have the following factorizations (each factorization has its own row, and blanks spaces represent multiplications by $1$):

$$\color{blue}{2 \cdot 2} \cdot \color{red} 3 * \, \, \, * $$

$$\color{blue}{2 \cdot 2} * \color{red} 3 * \, \, \,$$

$$\color{blue} 2 * \color{blue} 2 \cdot \color{red} 3 * $$

$$\color{blue} 2 * \color{blue} 2 * \color{red} 3$$

Note that the number of factorizations we have is the same as the number of distributions. Our factorization process is identical to the distribution process, except we replace blue balls with $2$s, replace red balls with $3$s, and consider groups of balls as products of factors.

We generalize this observation below.

Proof. Consider a ball distribution for some $k_1, k_2, ..., k_f$. Recall that within each box, the order of the balls does not matter. Likewise, in a product of primes, a clear "order" of its factors does not exist. In each box, balls of the same color are indistinguishable. Likewise, in a product of primes, repeats of the same factor are not distinguishable (as a consequence of the previous remark about prime products). Furthermore, in each box, balls are immutable; they cannot be broken up into more balls, and so each group of balls is unique. Likewise, as each "ball" (i.e. factor) in each group of factors is prime, no factor group can be broken up into an syntactically different factor group, and so each group of separated factors (e.g. $2^1, 2^1 \cdot 3^1, \emptyset$) are separated factors in the third row in the example above) is unique. Lastly, the order of groups between each of the boxes does not matter. Likewise, the order of each of the separated factors does not matter, as a clear "order" of its factors does not exist. Therefore, each color of balls can be replaced by a specific prime number, and the product of these prime numbers is $\prod_{i=1}^f p_i^{k_i}$, which we seek to separate into $n$ separated factor groups, i.e. $n$ distinct factors.

If there's a way to prove this that isn't explicitly combinatorial, I would appreciate that as well, especially if it is simpler.