I'm trying to figure out how to uniquely distribute 2 red balls and 2 blue balls into 3 indistinguishable boxes.

My mind leapt to the general case, and I've found that there is a bijection between 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$ boxes and the number of ways to factor a product of primes into $n$ distinct factors.

More clearly, let $p_i$ give the $i$th prime. Then I'm looking for the number of ways to factor $$\prod_{i=1}^f p_i^{k_i}$$ into $n$ distinct factors. Call this number $\Phi$.

How can I approach this?

Edit: A bit more research revealed the following:

Let $\eta(k_1,k_2,...,k_f) = \prod_{i=1}^f p_i^{k_i}$. Also, let $Q(x)$ give the number of multiplicative partitions of a non-squarefree number $x$. Then we have

$$\Phi=\mu^2(\eta)\cdot B(f) + (1-\mu^2(\eta))\cdot Q(\eta)$$ where $\mu(n)$ denotes the Möbius function and $B(f)=\sum_{k=0}^n S(n,k) $ is the $f$th Bell number.

Now I just need to find a formula for $Q(x)$; could someone help me in this regard?

  • 1
    $\begingroup$ Not sure the analogy is helpful. The different colored balls (or different primes) are effectively independent of each other. There are $\binom {n+k_i-1}{k_i}$ ways to place the $i^{th}$ balls...just multiply those. $\endgroup$ – lulu Jan 11 '18 at 0:02
  • $\begingroup$ Note: I am assuming that order matters...is that what you intended? That is, for your first example, I am assuming that $(RR),(BB),\emptyset$ is different from $(BB),(RR),\emptyset$. Is that what you meant? $\endgroup$ – lulu Jan 11 '18 at 0:03
  • 1
    $\begingroup$ No, the same issue arises in both descriptions. Is $24=2\times 2\times 6$ different from $24=12\times 2\times 2$, say. My method (Stars and Bars) retains order. That simplifies things a lot. To see the problem, note that my factoring of $24$ is equivalent to exactly $3$ factorings...according to where the $6$ is placed. But the factoring $24=1\times 3\times 8$ is equivalent to $6$ factorings. And the factoring $2\times 2\times 2$ is equivalent only to itself. $\endgroup$ – lulu Jan 11 '18 at 0:11
  • 1
    $\begingroup$ As André Nicolas points out in this answer (math.stackexchange.com/questions/185990/…), this is an insanely hard problem. If you came up with a formula for this, you'd have as just a special case with one colour, where $n=p^k$, a formula for the number of partitions of $k$. This alone is a hugely challenging and well studied problem: en.wikipedia.org/wiki/Partition_(number_theory). That said, your question alone is a nice proof of a connection between seemingly disparate things! $\endgroup$ – Colm Bhandal Jan 13 '18 at 12:47
  • 1
    $\begingroup$ @TiwaAina It's just straight Stars and Bars. Note that the variables here are the opposite of the ones used in the wiki article (i.e., $k's$ and $n's$ are reversed). Here we are looking to count $n-$tuples of non-negative numbers that add to $k_i$. $\endgroup$ – lulu Jan 31 '18 at 20:27

Your Answer

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

Browse other questions tagged or ask your own question.