**Possible Solutions
Semester Exam: Summer 1994**

(100 points total:4 points each part of each question, except 6 points on #15 and #16c)

1. P(7,7) = 7!

Consider all permutations of the 7 distinct letters.

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.

Grade Distribution on this exam:

A (89-100) 6

B (79-88) 4

C (67-78) 3

D (55-66) 1