My Math Forum Counting
 User Name Remember Me? Password

 Probability and Statistics Basic Probability and Statistics Math Forum

 May 2nd, 2018, 01:24 AM #1 Member   Joined: Nov 2012 Posts: 74 Thanks: 1 Counting The question is “in how many possible ways can 8 identical balls be distributed to 3 distinct boxes so that every box contains at least one ball?” There is a hint saying that the case can be considered as putting two bars on a row of eight balls, like o o l o o o l o o o the answer is 21. My calculation is 9C2 - (1 + 7 x 2) = 21 Could anyone explain the reason why the hint states so? Moreover, if 8 different balls are used, would the calculation become 3^8 - ( 3C1 x 1^8 + 3C2 x 2^8 ) ?
 May 2nd, 2018, 10:25 AM #2 Senior Member     Joined: Sep 2015 From: USA Posts: 2,264 Thanks: 1198
 May 2nd, 2018, 01:59 PM #3 Math Team   Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,791 Thanks: 970 Since each box has a least 1 ball, then there are 5 balls left to distribute: 0 0 5 0 1 4 0 2 3 0 3 2 0 4 1 0 5 0 : 6 1 0 4 1 1 3 1 2 2 1 3 1 1 4 0 : 5 2 0 3 2 1 2 2 2 1 2 3 0 : 4 3 0 2 3 1 1 3 2 0 : 3 4 0 1 4 1 0 : 2 5 0 0 : 1 Using n(n+1)/2 formula: SUM 1 to 6 = 6*7/2 = 21 Just aNUTter way of looking at it!
 May 3rd, 2018, 08:51 AM #4 Senior Member   Joined: May 2016 From: USA Posts: 1,250 Thanks: 516 Because the boxes are distinguishable, let's call them red, white, and blue. $r = \text {# of balls in red box} \implies r \in \mathbb Z \text { and } 1 \le r \le 8 - 2 = 6.$ $w = \text {# of balls in white box} \implies w \in \mathbb Z \text { and } 1 \le w \le 8 - r - 1 = 7 - r.$ $b = \text {# of balls in blue box} \implies b \in \mathbb Z \text { and } b = 8 - r - w.$ In other words, b is fully determined by r and w. Clearly, there are 6 possible values for r. Given any of one those values for r, there just as clearly are 7 - r possible values for w. And given any pair of values for r and w, there is only one possible value for b. $\displaystyle \left ( \sum_{r=1}^6 w * b \right ) = \left ( \sum_{r =1} (7 - r) * 1 \right) = \left ( \sum_{r=1}^6 7 \right ) - \sum_{r = 1}^6 r =$ $\displaystyle 7 * \left ( \sum_{r=1}^6 1 \right ) - \dfrac{6 * 7}{2} = 7 * 6 - 21 = 42 - 21 = 21.$ The trick here is seeing that you must combine addition and multiplication.
May 3rd, 2018, 09:37 AM   #5
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,264
Thanks: 1198

Quote:
 Originally Posted by JeffM1 The trick here is seeing that you must combine addition and multiplication.
The real trick uses the diagram in the OP.

If you've got $N$ balls, there are $N-1$ "slots" between them. If you've got $K$ bags to fill with at least one ball, then you have $K-1$ "walls" to fill slots with to partition the identical balls into bags.

so there are $\dbinom{N-1}{K-1}$ ways to place these walls into slots and achieve at least one ball per bag.

 May 3rd, 2018, 09:40 AM #6 Math Team   Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,791 Thanks: 970 I like mine better: distribute 5 balls only...3 cheers for me!!
May 3rd, 2018, 09:50 AM   #7
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,264
Thanks: 1198

Quote:
 Originally Posted by Denis I like mine better: distribute 5 balls only...3 cheers for me!!
So if I try to apply this method to general $N$ balls and $K$ boxes I think i'd do

$d=N-K$

$s = \dfrac{(d+1)(d+2)}{2}$

In this problem we have $d=8-3=5$

$s = \dfrac{(6)(7)}{2} = 21$

If I have $4$ boxes however.

$d = 4$

$s = \dfrac{(5)(6)}{2}=15 \neq \dbinom{7}{3}=35$

So Brave Sir Denis how to generalize your method?

 May 3rd, 2018, 10:06 AM #8 Math Team   Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,791 Thanks: 970 Mine applies to the OP, not general cases...AHEM! I respect your opinion, but if it ain't same as mine, then it's wrong

 Tags counting

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post USAMO Reaper Probability and Statistics 2 February 9th, 2015 02:21 PM jbergin Advanced Statistics 1 December 28th, 2014 04:02 PM jbergin Probability and Statistics 1 December 23rd, 2014 08:58 AM panky Algebra 4 October 24th, 2012 11:02 AM soulsister5 Applied Math 5 May 10th, 2010 03:44 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top