## Test 2 Version 2

1. Consider the word
`   REARRANGEMENTS `
.
• You have capital letters and lower case letters. How many different ways can you write the word REARRANGEMENTS?

Two choices for each spot, 14 spots, so we get 2^{14}.

• How many distinct rearrangements of REARRANGEMENTS are there (but only using capital letters)?

3 R's, 2 A's, 2 N's, 3 E's, 1 M, 1 G, 1T, 1S. So we just have 14!/(3!*2!*2!*3!)
Explanation: if we treat the letters as all distinct, there are 14! rearrangements. For each of these there are 3!*2!*2!*3! identical rearrangements. Hence we divide the total by the size of each group.

Other approach: Choose 3 from 14 to place the R's, times Choose 3 from 11 to place the E's, times Choose 2 from 9 to place the A's etc.

• How many distinct rearrangements of REARRANGEMENTS (again only capitals) in which two but not three of the R's are adjacent?

We could count how many have at least two R's together and then subtract how many have all three together. We have to be careful though not to count the same arrangements twice. I.e. gluing two R's together into a new letter and taking 13!/(2!*2!*3!) would count each arrangement of 3 R's together exactly twice, i.e. RR R and R RR. So instead of subtracting the number of times 3 R's are together, we will subtract twice that number. 3 R's are together 12!/(2!*2!*3!).

Another approach would be to place 2 R's somewhere (in the 13 available positions), then place the third R somewhere and then place the remaining letters. For this though, you'd have to realize that you should split into two cases: double R's on one end versus not at an end. The reason is that the number of places available to place the third R is different. So
Two R's at the end: 2 * 11 * 11!/(2!*2!*3!)
Plus
Two R's not at the end: After placing the 2 R's in one of the 10 middle spots, we lose two more places for the third R, so there are 10 remaining spots to put it, then 11 remaining to fill. I.e. 10 * 10 * 11!/(2!*2!*3!).

Best yet: Leave one R out of the picture for a moment: arrange the double R and all the other letters in all possible ways. Clearly this is 12!/(2!*2!*3!). Now think about where you can put the remaining R. With no restrictions, there are 13 possible places. Why? Because there are 12 objects (1 double R and 11 other letters) and we can put the R between any of them, at the beginning or at the end. But two positions are not allowed of course so this gives us 11 choices. Thus 11*12!/(2!*2!*3!).

2. Prove the following instance of van der Monde's theorem by giving a combinatorial proof:

```      C(13,4) = SUM(  C(8,4-k) * C(5,k) : k=0..4 )
```

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

3. Here we have an inductively defined set S of bit strings:

• both lambda and 1 are in S (where lambda is the empty string),

• if u and w are both members of S (not necessarily distinct), then u 0 w is also in S.
Decide if it is true that S is simply the set of all strings which do not have two consecutive 1's and then prove, likely using induction, your answer. That is, first prove whether or not every member of S has this property. Then prove whether or not every string with this property is in S.

As said on the test (to get familiar with the construction) 0 is in S. Indeed, apply the generation (second) rule by taking u and w be lambda. Thus we have that u and w are in S, hence 0 = lambda 0 lambda is in S.

Let P(n) be the statement that every string in S of length n has no consecutive 1's.

Let Q(n) be the statement that every string of length n which does not have consecutive 1's in in S.

We first prove P(n) by induction. Both 0 and 1 are in S and clearly neither has consecutive 1's, hence P(1) is true. Obviously P(0) is also true.

Now suppose that P(k) is true for all k< n+1 for some positive integer n. Fix any string s in S which has length n+1. The only way for s to get into S is by the generation rule. Therefore there are strings u,w in S such that s= u 0 w. Clearly u and w are strings in S with length less then n+1 hence they do not have consecutive 1's. It is now apparent that u 0 w = s also does not have consecutive 1's.

Now we prove Q(n) by induction. We have already checked above that Q(0) and Q(1) are true (i.e. lambda, 0 and 1 are all in S). Now suppose that n is a positive integer and that Q(k) is true for all k< n+1 (i.e. the strong principle of induction).

We must take a string s which has no consecutive 1's and has length n+1 and prove that s is in S. Ok, obviously s must have a 0 in it somewhere (it has length at least 2 and no consecutive 1's). Pick one of the positions in s where it is a 0, and let u be all the bits in s before that position and let w be all the bits in s after that position. Clearly s is equal to u 0 w. What about this u and w. Each has length strictly less than s and neither will contain consecutive 1's. Therefore by the inductive assumption, each is in S. Now using the generation rule for S, we see that u 0 w must also be in S.