Discrete Structures
Test #2
November 17 , 2003
Name____________________
R.  Hammack
Score ______



(1) Use induction to prove the following statements.

(a)  (10 points)  If n is a natural number, then 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n = 2^(n + 1) - 1.

Proof.
Basis step. If n = 0, then the statement is  2^0 = 2^(0 + 1) - 1, which is just the (true) statement 1 = 1.
Inductive step. Suppose k is a natural number and the statement is true for n = k.
This means  2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k = 2^(k + 1) - 1.
Now add 2^(k + 1)to both sides to get:
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k + 2^(k + 1) = 2^(k + 1) + 2^(k + 1) - 1
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k + 2^(k + 1) = 2 · 2^(k + 1) - 1
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k + 2^(k + 1) = 2^(k + 2) - 1
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k + 2^(k + 1) = 2^((k + 1) + 1) - 1.
Thus the statement is true for k+1, so the theorem is proved.  �

 


Note: Here is a simple non-inductive proof.
In binary form, 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n is just the n-digit binary number 1111111...111  consisting of n ones.
Any computer science student knows that this is 2^(n + 1) - 1.


(b)  (10 points)   If n is a natural number, then  7 | (2^(3n) - 1).

Proof.
Basis step. If n = 0, then the statement is  7 | (2^(3 · 0) - 1), which is just the (true) statement 7 | 0.
Inductive step. Suppose k is a natural number and the statement is true for n = k.
This means   7 | (2^(3k) - 1), so there is an integer c for which 7 c = 2^(3k) - 1.
Hence 2^(3k) = 7c + 1. (This equation will be used in the next line.)

Now notice that 2^(3 (k + 1)) - 1 =2^(3k + 3) - 1 = 2^(3k) 2^3 - 1 = (7c + 1) 2^3 - 1 = 56c + 8 - 1 = 7 (8c + 1).
Thus we have determined that there is an integer d = 8c + 1  for which 7d = 2^(3 (k + 1)).
This means 7 | 2^(3 (k + 1)), and the statement for k+1 is true. �



(2)  The questions on this page are about the set  A = {a, b, c, d}.


(a)  (6 points)    How many different relations are there on A?

A relation is just a subset of A × A, so the question is the same as aking how many subsets of  A × A there are.
Answer: | 2^(A × A) | = 2^(| A × A |) =2^16 =65,536


(b) (6 points)    How many different equivalence relations are there on A?

This is the same as asking how many partitions there are on A, for the parts of a partition correspond to equivalence classes of an equivalence relation. It's not hard to list all partitions of A.

{{a}, {b}, {c}, {d}} {{a, b}, {c}, {d}} {{a, b}, {c, d}} {{a, b, c}, {d}}
{{a, c}, {b}, {d}} {{a, c}, {b, d}} {{a, b, d}, {c}}
{{a, d}, {b}, {c}} {{a, d}, {b, c}} {{a, c, d}, {b}}
{{b, c}, {a}, {d}} {{b, c, d}, {a}}
{{b, d}, {a}, {c}}
{{c, d}, {a}, {b}} {a, b, c, d}

Answer: There are 15 equivalence relations.



(c) (6 points)     How many different functions f : AA are there that satisfy f(a) = f(c)?

(4)(4)(1)(4) = 64


(d) (6 points)       How many different functions f : 2^AA × A are there?

16^16 =18,446,744,073,709,551,616



(e)  (6 points)    How many different injective functions f : 2^AA × A are there?

16! = 20,922,789,888,000

(3)  The problems on this page concern length-6 lists made from the letters A, B, C, D, with repetition allowed.


(a)  (6 points)     How many such lists contain exactly 3  A's?

There are (6) = 20 3 ways to choose the positions of the 3 A's.
Then there are 3 slots left and you have 3 choices for each, so 3^3 = 27ways to fill them in.
By  the multiplication principle, there are (20)(27) = 540 such lists.



(b) (6 points)     How many such lists contain exactly 3  A's  and 1  B?

There are (6) = 20 3 ways to choose the positions of the 3 A's.
Then there are 3 slots left and you have 3 choices for where to put the B (3 ways to do this).
Finally there are 2 slots left and you have 2 choices for each. There are (2)(2) = 4 ways to fill them in.
By  the multiplication principle, there are (20)(3)(4) = 240 such lists.


(c) (6 points)     How many such lists are in alphabetical order?

Such a list could be encoded in stars-and-bars form.
Examples:
AABCCD ----> **|*|**|*
BBBCDD ----> |***|*|**
CCCCCC  ---> ||******|

Thus the number of such lists is
(6 + 3) = (9) = 9 !/(3 ! 6 !) = (9 · 8 · 7)/(3 · 2) = 84 6 6


(d) (6 points)     How many such lists are not in alphabetical order?

There are 4^6 =4096 lists all together.
As above, only 84 are in alphabetical order.
Thus 4096 - 84 = 4012 are not in alphabetical order.


(e)  (6 points)  How many such lists are there if the first, second, or third entry must be an A?

Let A be the set of lists of form   A _ _ _ _ _ ,  and so | A | = 4^5
Let B be the set of lists of form   _ A _ _ _ _ ,  and so | B | = 4^5
Let C be the set of lists of form   _ _ A _ _ _ ,  and so | B | = 4^5
So A⋂B is all the lists of form  A A _ _ _ _ ,  and so | A⋂B | = 4^4
So A⋂C is all the lists of form  A _ A _ _ _ ,  and so | A⋂C | = 4^4
So B⋂C is all the lists of form  _ A A _ _ _ ,  and so | B⋂C | = 4^4
A⋂B⋂C is the lists of form    A A A _ _ _ ,  and so | A⋂B⋂C | = 4^3

By the inclusion-exclusion formula, the answer is
| A⋃B⋃C | = | A | +| B | +| C | -| A⋂B | -| A⋂C | -| B⋂C | +| A⋂B⋂C |
= 3 · 4^5 - 3 · 4^4 + 4^3 = 4^3 (3 · 4^2 - 3 · 4 + 1) = 64 (48 - 12 + 1) = 2368


Here's another way of looking at it.
(# of lists with 1st 2nd or 3rd element A) = (total # of lists) - (# of lists with 1st 2nd and 3rd element NOT A)
= (4)(4)(4)(4)(4)(4) - (3)(3)(3)(4)(4)(4) = 2368

The number of lists where the first, second or third element is NOT an A  is (3)(3)(3)(4)(4)(4)
then the
(4)  

(a)  (5 points)     Find the coefficient of x^2y^3 in the expansion of (3x + 2y)^5.
            1
          1  1
        1  2  1
      1  3  3  1
   1  4  6  4  1
1  5 10 10  5  1

Looking at Pascal's Triangle, and applying the Binomial Theorem,
you can see that the relevant term is 10 (3x)^2 (2y)^3 = 720x^2y^3.
Answer: 720


(b) (5 points)   How many anagrams of the word BANANA are there?

6 !/(3 ! 2 !) = (6 · 5 · 4)/2 = 60


(c) (5 points)     In how many ways can a group of 12 people be divided into 3 teams of 4 each? (In this problem, the teams are distinct. Call them Team A, Team B, and Team C.)

First choose 4 out of 12 people for Team A. There are (12) 4ways of doing this.
Next, there are 8 people left. Choose 4 of them for Team B.  There are (8) 4ways of doing this.
This leaves 4 people unchosen. Put them on Team C.
By the multiplication principle, the total number of ways to choose the teams is
(12) (8) = 12 !/(4 ! 8 !) 8 !/(4 ! 4 !) = 12 !/(4 ! 4 ! 4 !) = (12 · 11 · 10 · 9 · 8 · 7 · 6 · 5)/(4 ! 4 !) = 34, 650 4 4different ways.


(d) (5 points)     A coffee shop sells 8 different kinds of bagels. How many ways are there to order a dozen bagels?

((8 )) = (8 + 12 - 1) = (19) = 19 !/(7 ! 12 !) = 50, 388 12 12 12