1
$\begingroup$

I believe it's likely this question has been asked before, but I lack the skill to search for it. Suppose I have an indefinite supply of red and green balls. I have $n$ bins, and I want to know the number of ways I can place either 0 balls, one red, one green, or both red and green into each bin (each bin will be in one of these four states). Order does matter. I know this involves using the binomial theorem, but I don't know how to account for the fact that each bin may contain at most one of each color ball. I feel like the number of balls doesn't actually matter, since it's "enough" to maximally fill each bin.

$\endgroup$
1
$\begingroup$

Consider the $2n$ symbols

$$ 1_{\text{red}}, \dots, n_{\text{red}}, 1_{\text{green}}, \dots, n_{\text{green}} $$

where $i_{\text{red}}$ or $i_{\text{green}}$ means place a red ball or a green ball into bin $i$, respectively.

If order matters, and we are only allowed to put at most one red and one green ball into any given bin, then we are just taking a string of these $2n$ symbols without duplicates.

There are $$ \frac{(2n)!}{k!} $$ strings (permutations) of length $k$ so the total is

$$ \sum_{k = 0}^{2n} \frac{(2n)!}{k!}. $$

This is the even index part of sequence A000522 in the OEIS if you want to look for more information such as alternative formulae. For instance,

$$ \sum_{k = 0}^{2n} \frac{(2n)!}{k!} = \lfloor (2n)! e \rfloor $$

for $n \ge 1$.

$\endgroup$

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.