Problem: In how many ways can ten identical books be distributed to four students such that
(a) Each student gets at most five books.
(b) Each student gets at least one book and at most five books.
(c) No student gets exactly three books. Hint: A or B or C or D!
The problem corresponds to finding the number of nonnegative integer solutions
to the equation X1+X2+X3+X4 = 10 (where Xi is # of books given to the i-th student)
under the restrictions specified as parts(a), (b) or (c).
The Javascript solution utilizes this fact (view the HTML (Frame) source).
Note: The JavaScript code given here is not the most efficient.
a) Each student gets at most five books. This is a combination-with-repetition because what matters is how many books each student gets. We use 3 bars (one less than # of students) and 10 stars. With the given restriction, it is easier to solve as: N = All possible selections - Selections where at least one student gets 6 or more books |All possible selections| = C(10+3,3) = (13*12*11)/(3*2*1) = 286 The case for “selections where at least one student gets 6 or more books” actually corresponds to “exactly one student gets 6 or more books” (because we cannot have more than one student getting 6 books when there is a total of 10 books) 1. Exactly one student gets 6 or more books For 1: choose the student, reserve 6 books for him and distribute remaining 4 books among all ⇒ C(4,1) * C(4+3,3) = 4 * (7*6*5)/(3*2*1) = 140 Thus, N = 286 - 140 = 146 b) Each student gets at least one book and at most five books. Reserve one book for each student then distribute the remaining 6 books such that each student gets at most 4 books. N = All possible selections - Selections where at least one student gets 5 or more books = C(6+3,3) - (Cases where at least one student gets 5 or more books from 6 books)* = C(9,3) - 4 * C(1+3,3) = (9*8*7)/(3*2*1) - 4*4 = 84 - 16 = 68. * These correspond to the cases where exactly one student gets 5 or more books c) No student gets exactly three books. Hint: A or B or C or D! Let A (B,C,D) be student #1 (#2, #3, #4) get 3 books Answer: N = |All selections | - |A∪B∪C∪D| By inclusion-exclusion and because of symmetry, |A∪B∪C∪D| = 4*|A| - C(4,2)*|A∩B| + C(4,3)*|A∩B∩C| - |A∩B∩C∩D| |A| = assign student #1 three books and distribute rest among three students, C(7+2,2) = 36 |A∩B| = assign student #1 and student #2 three books each and distribute rest among two students, = C(4+1,1) = 5 |A∩B∩C| = assign student #1, student #2, and student #3 three books each and distribute remaining books among one student ⇒ 1 way Thus, N = 286 - 4 * 36 + C(4,2)*5 - C(4,3)*1 = 286 - 144 + 6*5 - 4 = 168