## Answers to Test 2 Version 1

1. There is a long rectangular table seating 1 at each end and 5 on each side in the President's dining hall.
• The President and Vice-President are hosting a dinner for 10 guests. How many ways to seat everyone if the President and Vice-President must be seated at the end.

2 places to put President * 1 place to put VP * 10! ways to arrange the 10 guests = 2*10!.

• The serving staff is told to set the table for a dinner using Blue napkins for the 3 representatives from the University of Toronto, Purple napkins for the 5 from McMaster University and White napkins for the 2 student representatives. There is also a Presidential napkin and a Vice-Presidential napkin. How many ways are there to arrange the napkins if again, the President and Vice-President are to sit at the ends?

Leave aside the President and VP at the ends for a moment. We must place the other 10 colored napkins in the 10 possible spots. Clearly we have 3 identical Blue, 5 identical Purple and 2 identical White. For each of the 10! ways of placing the 10 physically separate napkins there are 3!*5!*2! (-1) other placements which appear identical. Therefore there are 10!/(3!*5!*2!) ways of arranging the 10 colored napkins. This should be multiplied by the ways of placing the Presidential and VP napkins.

• Now the staff is told that they should not seat any two of the University of Toronto representatives across from one another. How many ways to arrange the napkins with this additional restriction.

Just count how many arrangements do involve having two Blue napkins directly across from one another and then subtract this quantity from answer in the previous part.
We can argue this way. Again 2 ways to place Presidential napkins. Five ways to place 2 Blue napkins across from each other. 8 ways to place the remaining Blue napkin (these are all distinguishable by the location of where there are two facing Blue napkins). 7 seats remain without napkins, so we have 7!/(5!*2!) of placing remaining. Therefore there are 2*5*8*(7!/(5!*2!)) ways of placing the napkins so there are 2 Blues across from each other.

2. Recall that Pascal's Identity is the assertion that for integers
`  n>= k > 0  `

C(n+1,k) = C(n,k-1) + C(n,k) .

Give a combinatorial proof of this identity.

Well you have seen the proofs. Your proof must adequately mention sets, partitions, and correspondences between sets.

3. In this question we will have a recursively defined function H which will assign to every bit string w some other bit string H(w). Your ultimate goal is to simply tell me what the value of
w = H(01001100011100001111000001111100000011111100000001111111).

However I certainly do not want you to carry out the operation of H on the above string, rather I want you to formulate a verbal description of what H does to a string and prove, by induction, that this is the case.

Here is the definition of H:

H(lambda)= lambda where lambda is the empty string,

for a string s, here are the values of H(s 0) and H(s 1):
H(s 0) = H(s)

`  and   `
H(s 1) = 1 H(s) 1

If you didn't figure out what H is doing you haven't yet come to grips with recursion. Or more to the point you are not thinking of bit strings recursively. A bit string is a sequence of 0's and 1's (of course). The rules for H are telling you that if a bit string ends in a 0, then erase the 0 and compute H applied to the shorter string. If a string ends in a 1, figure out what H applied to the shorter string (with the 1 removed from the end) gives you, take that result and surround it by 1's. Hence, as stated on the test:
H(101) = 1 H(10) 1 = 1 H(1) 1 = 1 11 1

Thinking about this a bit more: H simply erases all the 0's in a bit string and doubles the number of 1's. Well this is our conjecture. Let P(n) denote the statement
If s is a bit string with n bits, then H(s) is the bit string consisting of 2j 1's where j is the number of occurences of 1 in s

We prove P(n) is true by induction. P(0) is true by inspection. Assume P(n) is true and let w be an arbitrary bit string of length n+1. There are two cases: First w could have the form s 0 and Second, w could have the form s 1. Clearly in both cases, s has length n, hence we know about H(s).

Let j be the number of occurences of 1 in w. In the first case j is also the number of occurences of 1 in s. By definition, H(w) = H(s) and by inductive assumption, we know that H(s) consists of the string of 2j 1's. This is exactly what we want to prove about H(w).

Now in the second case, we notice that s has exactly j-1 occurences of 1. Therefore H(s) is the string consisting of 2(j-1) 1's. Since H(w)= 1 H(s) 1, we see that H(w) consists of 2+ 2(j-1) = 2j 1's as required.