2000 MAT344S Test #1

1. Suppose a codeword consists of an arrangement of the digits 1,2,3,4,5, where repetition of digits is allowed.

(a) How many codewords of length 10 can be constructed which don't end with 3 or 5?

We have C(5,1) choices for the first nine digits and C(3,1) choices for the last. By the product rule, the answer is 3*5⁹ = 5,859,375.

(b) How many codewords of length n have either two or three different digits, where n>=3 is a positive integer?

There are C(5,2)*(2ⁿ - 2) codewords with two different digits, and C(5,3)*(3ⁿ-3*2ⁿ+3) codewords with three different digits, for a total of 10*(3ⁿ - 2*2ⁿ + 1)

2. (a) Give a combinatorial proof for the identity C(2n,2) = 2*C(n,2) + n².

The left side counts the number of ways of choosing two numbers from [2n]. The right side counts the number of ways of either choosing two numbers from {1,2,...,n} or {n+1,n+2,...,2n}, or one number from each set. These describe an equivalent process, so the number of ways is equal.

2. (b) Prove the identity C(2n,n) + C(2n,n-1) = C(2n+2,n+1)/2.

C(2n,n) + C(2n,n-1) = C(2n+1,n) = C(2n+2,n+1)/2.

3. In how many ways can 24 different balls be placed in 3 distinct boxes so that there are twice as many balls in one box as in the remaining two boxes combined?

One box must have sixteen balls, the other two have eight together. There are C(3,1) ways of choosing the first box, C(24,16) ways of choosing the balls that go into it, and C(2,1)⁸ ways of choosing which box the remaining balls go into. The answer is therefore C(3,1)*C(24,16)*C(2,1)⁸.

4. Suppose there are 20 identical blue balls, 18 identical red balls, and 10 identical yellow balls. Compute the number of ways to select 16 balls.

C(16+3-1,16) - C(5+3-1,5) = 153 - 21 = 132.