2 places to put President * 1 place to put VP * 10! ways to arrange the 10 guests = 2*10!.
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.
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.
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.
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 0) = H(s)
andH(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.