Possible Solutions
Semester Exam: Summer 1994
(100 points total:4 points each part of each question, except 6 points on #15 and #16c)

An alternative solution is sigma(k,1,7;P(7,k)). Under what assumptions is this correct?

2. 26 + (26*10*2) = 546
By letter alone, there are 26 possible variables. Using a letter-digit pair, there are 26*10 possible variables, multiplied by 2 because order restrictions (letter-digit or digit-letter) are not stipulated. We add the two cases because they are disjoint.

3. T(n) = T(n-1) + 3, where T(1) = 5

4. C(13,6)
Use the relationship C(n-1,k-1), where n=14 represents the total number of items and k=7 represents the number of different items.

5. 45 books
Apply the pigeonhole principle: Consider 4 bins into which we place the books according to subject. It is possible to get 11 books in each bin and not yet have 12 of one subject. This represents 44 books. The 45th books, however, will force one bin to have at least 12 books.

6. 2!*2! = 4
Because these are scrabble tiles, we assume they are distinguishable. Under this condition, to arrange the tiles to spell TOTO, there are 2! ways to place the Ts and 2! ways to place the Os.

7.
(a-i) P(13,13) = 13!
Consider the number of ways to permute 13 distinct objects.

(a-ii) 9!*C(10,4)*4! = 9!*P(10,4)
First arrange the mathematics books, in P(9,9)=9! ways. There now are 10 places for the science books. Choose 4 of those places and then consider the permutations of the 4 science books that can go in those places. Another way to look at the last step, once the mathematics books have been placed, is to recognize there are 10 ways to place the first science book, 9 for the second, 8 for the third, and 7 for the fourth. This is P(10,4).

(b-i) C(13,9)
We now have two types of books to be arranged in 13 spots on a shelf. Choose 9 of the 13 spots for the mathematics books.

(b-ii) C(10,9)
Consider the 4 indistinguishable science books as a unit. There now are 10 units to be placed, 9 of which are mathematics books.

8. 99 business students
Apply the I-E P, but solve for the number of elements in the universe: Let U represent the set of all business students in Whitmer Dorm, B represent the property "subscribe to Business Weekly," N represent "subscribe to Newsweek," and T represent "subscribe to Time." Then by the I-E P,

|~B ^ ~N ^ ~T| = |U| - {|B| + |N| + |T|} + {|B ^ N| + |B ^ T| + |N ^ T|} - |B ^ N ^ T|.

Substitute the known values into this relationship:
8 = |U| - (47 + 44 + 32) + (11 + 12 + 12) - 3.

Solve this for |U| to get the solution.

9. 11 friends
The description states that Joan drew from her pool of friends with no pairs repeating. Assuming there are 52 weekends in a year, we need C(n,2) >= 52. Over the positive integers, the smallest value n can take is 11.

10. C(11,3)
We need to know how many non-negative integer solutions exist for sigma(i,1,4; x(i)), where x(i) represents the exponent for the ith variable. We use C(n+k-1,k-1) with n=8 and k=4.

11.
To use the PHP, we need to know the population P of San Francisco and the maximum number H of hairs on a human head. If P > H, it must be the case, by the PHP, that at least two San Francisco residents have the same number of head hairs.

12.
(a) a + b = t
(b) C(t,a) = C(t,b) = t!/(a!b!)
Assuming that a + b = t, we determine the number of solutions to that equation over the non-negative integers.

13.
(a) s - r + 1 (b) 2^(s-r+1) (c) C(s-r+1,2)

14. 12!/(5!5!2!) + 12!/(7!2!3!) + 12!/(6!4!)
It is 8 blocks by the shortest street route. To use 12 blocks, we must include one of only three route possibilities:
(I) include 2 extra blocks E and 2 extra blocks W (a 2-block horizontal double back)
(II) include 2 extra blocks N and 2 extra blocks S (a 2-block vertical double back)
(III) include 1 extra block in each of the 4 directions (a 1-block horizontal double back and a 1-block vertical double back)

Here are the blocks traveled under each of these distinct cases:
N S E W
(I) 5 0 5 2
(II) 7 2 3 0
(III) 6 1 4 1

Now consider the number of ways to arrange each of these possibilities:
(I) 12!/(5!5!2!)
(II) 12!/(7!2!3!)
(III) 12!/(6!4!)

In each of these cases, we consider the total blocks traveled (12!) and divide by the number of blocks traveled in each direction. This is similar to arranging the letters in a word within which there are identical letters.

15.
(I) Begin with the left-side expression and attempt to rewrite and simplify using equivalent forms:
r*C(n,r) = r*[n!/(r!(n-r)!)] = n!/[(r-1)!(n-r)!] = [n*(n-1)!]/[(r-1)!(n-r)!]
= n*[(n-1)!]/{(r-1)![(n-1)-(r-1)]!} = n*C(n-1,r-1)
This last expression is the expression we sought.

(II) Begin with the left-side expression and attempt to rewrite and simplify using equivalent forms:
2C(n,2) + n^2 = [2*n*(n-1)]/2 + n^2 = n^2 - n + n^2 = 2n^2 - n = n(2n-1)
= [2n(2n-1)]/2 = (2n)!/[2!(2n-2)!] = C(2n,2)
This last expression is the expression we sought.

16.
(a) C(6,2)
There are 4 total responses (4 judges) and 3 different responses (A, D, N). We therefore seek the number of ways to solve the equation X(1) + X(2) + X(3) = 4 over the non-negative integers. Apply the relationship C(n+k-1,k-1) with n=4 and k=3.

(b) 3^4
Each of 4 judges has 3 responses to offer. This results in 3*3*3*3 ways for the judges to respond when we account for each specific judge's response.

(c)
For n judges having k response options, there are:
(i) C(n+k-1,k-1) possible aggregate responses
(ii) k^n possible responses when we account for each specific judge's response.