1
$\begingroup$

First of all sorry if this has been asked before, I could find "similiar" questions which seem to be harder but not quite this specific question.

You are given P white balls and Q black balls, how many ways can you put them into N different boxes?

My idea was to put first the P white balls into the N different boxes which can be done in $\binom{P+N-1}{P}$ ways (right?) then for each of these you do the same with the black balls so overall the answer is $\binom{P+N-1}{P}\binom{Q+N-1}{Q}$

Is this correct? If so is there a way to do it so you get a nicer form?

$\endgroup$

3 Answers 3

2
$\begingroup$

Your answer is indeed correct, assuming that your bins are distiguishable and the balls of same color are identical. For those browsing, the OP arrived at his answer using Theorem 2 at the link below:

http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Also, I'm fairly sure this is the nicest form you'll get. If you attempt to expand this into factorials and try to get a single $\binom{n}{k}$ expression, I think you'll simply end up with a mess of factorials.

$\endgroup$
1
$\begingroup$

Putting first the P white balls in the boxes, then the black ball seems the right way to do it. The formula for this would rather be P(k,n) though: The number of partitions of the integer k into n parts.

Oh ! Are your bins distinguishable or not ? Here I assume the bins do all look the same...

So final formula would be P(P,N) * P(Q, N)

See here for an explanation about k balls in n boxes, and here for the calculation of P(k,n)

$\endgroup$
5
  • $\begingroup$ I think this would be the case if the balls were distinguishable and bins were identical. $\endgroup$
    – Kaj Hansen
    Apr 8, 2014 at 20:03
  • $\begingroup$ Ah! I see your edit now. OP does use the phrase "different boxes", but I admit that the question is unclear. $\endgroup$
    – Kaj Hansen
    Apr 8, 2014 at 20:04
  • $\begingroup$ @Kaj_H both identical, actually, the balls and the bins. Yes, are "different boxes" meant to be "distinguishable boxes" ? Probably, as this is the formula that was proposed in the first hand. $\endgroup$
    – mika
    Apr 8, 2014 at 20:05
  • $\begingroup$ I'm not quite sure, it was an exam question and the question was phrased as "How many ways are there to place p white and q black balls into n different boxes?" and I assumed the boxes were labelled. From my answer could I divide it by n! to account for all the labels that n boxes can have and arrive at the same answer, $P(P,N)*P(Q,N)$? $\endgroup$
    – HBeel
    Apr 8, 2014 at 20:08
  • $\begingroup$ You are indeed correct, mika. It's been a while since I've taken combinatorics! $\endgroup$
    – Kaj Hansen
    Apr 8, 2014 at 20:09
0
$\begingroup$

You can use numeric representation. For each ball, you write the box that it is in.

For example, if $P = 2$, $Q = 3$ and $N = 3$ than for each ball, you have 3 different choices. You write all the numbers from $11111$ (all in box number 1) to $33333$ (all in box number 3). That is $3^5$ ($N^{(P+Q)}$.

If none of the boxes should be emtpty, you subtract the cases that two of the boxes are empty. That covers the cases where at least two of the numbers are different. For $N$ boxes, that is $\binom{P+Q}{N} \times \binom{P + Q - N}{N}$

Although, if the boxes are identical, you need to eliminate symmetrical solutions as well.

Your result is $(\frac{(P+Q)!}{P!Q!})$ $\times$ $(\frac{1}{K!(P+Q-K)!)})$ $+$ $(\frac{1}{(K-1)!(P+Q-K+1)!})$ $+$ $(\frac{1}{(K-2)!(P+Q-K+2)!})$ $...$

$\endgroup$
2
  • $\begingroup$ The boxes are allowed to be empty. Also the balls are indistinguishable other than colour so using the string representation you suggested if the first 2 digits where the white balls and the following 3 were black balls then strings 12111 and 21111 would count the same thing twice would it not? $\endgroup$
    – HBeel
    Apr 8, 2014 at 20:19
  • $\begingroup$ The last solution eliminiates all the symmetrical solutions such as 12111, 21111 and boxes are allowed to be empty. $\endgroup$
    – padawan
    Apr 8, 2014 at 20:36

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.