1
$\begingroup$

From the first answer by Brian M. Scott in How many ways can 10 teachers be divided among 5 schools? I am getting a sense that there are 4 cases

Objects | containers

distinguishable | distinguishable

indistinguishable | distinguishable -> stars and bars

distinguishable | indistinguishable

indistinguishable | indistinguishable

My doubt is the second one .

If I say teachers are indistinguishable but schools are distinguishable and look at the question as "In how many ways 5 schools be allotted to 10 teachers " instead of seeing this as "In how many ways can ten teachers be divided among five schools?". Because I feel both mean the same.Then now Will I apply stars and bars and say answer is $\displaystyle\binom{10 + 5 -1}{9} $

But $\displaystyle\binom{10 + 5 -1}{9} \neq \displaystyle\binom{10 + 5 -1}{4}$

RHS is the correct answer posted by brian M scott in that question

LHS is my way when I exchange n and r due to confusion

In other words if $n =5 , r = 10 ,it\ is\ 14C4 $ <- Brians answer

if $n =10 , r = 5 , it\ is\ 14C9$ <- my confused interpretation lead to this

Question 1: so what is that factor which decides which is n and which is r ? Give me some examples to illustrate this

Question 2: If this is the confusion , there are chances that I can even mix up Stirling number of the second kind and stars and bars concept usage .So please give me example to show when these two can be used .

$\endgroup$
  • $\begingroup$ You do realize that 10+5-1=14 while 9+4=13 and these aren't the same values. N choose r is equal to N choose (n-r) but that isn't what you have here. $\endgroup$ – JB King Aug 7 '13 at 20:33
  • $\begingroup$ no the stars and bars formula is $n+r-1 C r-1 $ en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – Harish Kayarohanam Aug 7 '13 at 20:35
  • $\begingroup$ actually in that question it is n =10 , r =4 $\endgroup$ – Harish Kayarohanam Aug 7 '13 at 20:35
  • $\begingroup$ That formula you give isn't there. n+r-1Cr is given as is n+r-1Cn-1 which is the same as if you sum the values on the right side of the C you get n+r-1 which is the key to the identity. $\endgroup$ – JB King Aug 7 '13 at 20:49
  • 3
    $\begingroup$ I don't think that you should think in terms of formulas here (e.g. "Which is 'n', which is 'r'?). If you understand the method, you can easily figure each problem out from first principles each time without resorting to memorizing formulas. $\endgroup$ – Potato Aug 7 '13 at 21:13
2
$\begingroup$

This answer probably adds nothing to the linked answer in the other question, but in case it helps:

One way to think of these problems is in terms of "urns and balls". Each ball goes into one urn (this determines the mapping), analogy: each teacher is assigned to one school.

Assume first that all balls are distinguishable (say, 5 balls: 1, 2 ... 5) and so the urns (say, 3 urns: A, B, C). Here are some possible assigments

   I         |     II         |    III        |    IV        |     V
 ------------ ---------------- --------------- -------------- --------------
A <- {1,3}   |  A <- {3,1}    |  A <- {1,3}   |  A <- {4,5}  | A <- {1,3,4} 
B <- {2,4,5} |  B <- {2,4,5}  |  B <- {2}     |  B <- {2}    | B <- {2}
C <- {}      |  C <- {}       |  C <- {4,5}   |  C <- {1,3}  | C <- {5}   

In all "urns and balls" scenarios (and in your four cases), there is no "order inside the urn". So, case II should never be counted as distinct from I - we'll always skip that.

Case 0: If we allow empty urns, (and if the balls and urns are distinguishable), all assignments are valid (I, III, IV, V ...), we have a total of $3^5=243$. You don't seem interested in this case.

Case 1: If we disallow empty urns (each school must have at least one teacher), we must remove colum I from the count. Now (remembering that we have distinguishable balls and urns) the Stirling numbers of the second kind come into play: the total count is given by $3! \, S(5,3) = 6 \times 25 = 150$ (the factor $3!$ , permutations of the urns, takes into account that SN counts indistinguishable urns).

Case 2: If the urns are indistinguishable, (in the example, III and IV must be counted as one) we have instead the plain Stirling number of the second kind: $ S(5,3)=25 $

Notice that it's easy to go from urns indistinguishable to distinguishable (just multiply by the permutation of urns, $3!$). That's because, when urns turn distinguishable, each permutation maps to a new set of counts. That doesn't happen for the balls indistinguishable to distinguishable, because the order of balls does not matter (even if the balls are distinguishable) for balls that are inside the same urn, we must think it differently. And that's when stars-and-bars appears.

Case 3: If the balls are indistinguishable and the urns distinguishable what matters is how many balls go inside each urn (case III and IV are counted as one, again, but for other motive). This is a fixed size (size=3) composition of the 5 balls, which by the stars-and-bars argument, is ${5-1 \choose 3-1}=6$.

Case 4: If the balls and urns are indistinguishable we have a fixed size (size=3) partition of the 5 balls. This doesn't have a closed formula, in this case the count is 2 (3-1-1 ; 2-2-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.