Mathematics: A Discrete Introduction 3rd Edition solutions

Mathematics: A Discrete Introduction 3
Evaluate the following without using the formula from Theorem 17.12. Indeed, try to find the answer without doing any writing or arithmetic. a. 9 0
. b. 9 9
. c. 9 1
. d. 9 8
. e. 9 6
9 3
. f. 0 0
. g. 2 0
. h. 0 2

Mathematics: A Discrete Introduction 3
Write out all the 3-element subsets of f1; 2; 3; 4; 5; 6g to verify that 6 3
D 20.

Mathematics: A Discrete Introduction 3
Find the coefficient! Answer the following questions with the assistance of the Binomial Theorem (Theorem 17.8): a. What is the coefficient of x 3 in .1 C x/6 ? b. What is the coefficient of x 3 in .2x 3/6 ? c. What is the coefficient of x 3 in .x C 1/20 C .x 1/20? d. What is the coefficient of x 3y

Mathematics: A Discrete Introduction 3
Mixed Matched Marvin has a drawer full of 30 different socks (no two are the same). He reaches in and grabs two. In how many different ways can he do this? Now he puts them on his feet (presumably, one on the left and the other on the right). In how many different ways can he do that?

Mathematics: A Discrete Introduction 3
Twenty people attend a party. If everyone shakes everyone elses hand exactly once, how many handshakes take place?

Mathematics: A Discrete Introduction 3
a. How many n-digit binary (0,1) sequences contain exactly k 1s? b. How many n-digit ternary (0,1,2) sequences contain exactly k 1s?

Mathematics: A Discrete Introduction 3
How many length-12 lists can we form that contain exactly four each of the letters A, B, and C?

Mathematics: A Discrete Introduction 3
Fifty runners compete in a 10K race. How many different outcomes are possible? assume that there are no ties. The answer to this question depends on what we are judging. Find different answers to this question depending on the context. a. We want to know in what place every runner finished. b. The ra

Mathematics: A Discrete Introduction 3
Write out all the three- and four-element subsets of f1; 2; 3; 4; 5; 6; 7g in two columns. Pair each three-element subset with its complement. Your chart should have 35 rows.

Mathematics: A Discrete Introduction 3
A special type of door lock has a panel with five buttons labeled with the digits 1 through 5. This lock is opened by a sequence of three actions. Each action consists of either pressing one of the buttons or pressing a pair of them simultaneously.For example, 12-4-3 is a possible combination. The co

Mathematics: A Discrete Introduction 3
In how many different ways can we partition an n-element set into two parts if one part has four elements and the other part has all the remaining elements?

Mathematics: A Discrete Introduction 3
Look down the middle column of Pascals triangle. Notice that, except for the very top 1, all these numbers are even. Why?

Mathematics: A Discrete Introduction 3
Use Theorem 17.12 to prove Proposition 17.7

Mathematics: A Discrete Introduction 3
. Prove that the sum of the numbers in the n th row of Pascals triangle is 2 n . One easy way to do this is to substitute x D y D 1 into the Binomial Theorem (Theorem 17.8). However, please give a combinatorial proof. That is, prove that 2 n D Xn kD0 n k ! by finding a question that is correctly answ

Mathematics: A Discrete Introduction 3
Use the Binomial Theorem (Theorem 17.8) to prove n 0 ! n 1 ! C n 2 ! n 3 ! C


n n ! D 0 provided n > 0. Move all the negative terms over to the right-hand side to give n 0 ! C n 2 ! C n 4 ! C


D n 1 ! C n 3 ! C n 5 ! C


: Give a combinatorial description of what this means and convert

Mathematics: A Discrete Introduction 3
Consider the following formula: k n k ! D n n 1 k 1 ! : Give two different proofs. One proof should use the factorial formula for n k
(Theorem 17.12). The other proof should be combinatorial; develop a question that both sides of the equation answer

Mathematics: A Discrete Introduction 3
Let n  k  m  0 be integers. Consider the following formula: n k ! k m ! D n m ! n m k m ! : Give two different proofs. One proof should use the factorial formula for n k
(Theorem 17.12). The other proof should be combinatorial. Try to develop a question that both sides of the equation answer.

Mathematics: A Discrete Introduction 3
How many rectangles can be formed from an m n chess board? For example, for a 2 2 chess board, there are nine possible rectangles.

Mathematics: A Discrete Introduction 3
Let n be a natural number. Give a combinatorial proof of the following: 2n C 2 n C 1 ! D 2n n C 1 ! C 2 2n n ! C 2n n 1 ! :

Mathematics: A Discrete Introduction 3
Let n be a positive integer. Prove that n n 2
 1.

Mathematics: A Discrete Introduction 3
Use Stirlings formula (see Exercise 9.7) to develop an approximation formula for 2n n
. Without using Stirlings formula, give a direct proof that 2n n
 4 n

Mathematics: A Discrete Introduction 3
Use the factorial formula for n k
(Theorem 17.12) to prove Pascals Identity (Theorem 17.10).

Mathematics: A Discrete Introduction 3
Prove n 3 ! D 2 2 ! C 3 2 ! C 4 2 ! C


C n 1 2 ! : Hint: Mimic the argument for Proposition 17.5.

Mathematics: A Discrete Introduction 3
Continued from the previous problem. Proposition 17.5 says n 2
D 1C2C


C.n1/. Make a large copy of Pascals triangle and mark the numbers 7 2
, 6, 5, 4, 3, 2, and 1. You have several choicesdo this right. Whats the pattern? The previous exercise asks you to prove n 3
D 2 2
C 3 2
C 4 2
C

Mathematics: A Discrete Introduction 3
. Give a geometric and an algebraic proof that 1 C 2 C 3 C


C .n 1/ C n C .n 1/ C .n 2/ C


C 2 C 1 D n 2 :

Mathematics: A Discrete Introduction 3
Prove: n 0
n n
C n 1
n n1
C n 2
n n2
C


C n n1
n 1
C n n
n 0
D 2n n
.

Mathematics: A Discrete Introduction 3
How many Social Security numbers (see Exercise 8.12) have their nine digits in strictly increasing order? The following series of problems introduce the concept of multinomial coefficients

Mathematics: A Discrete Introduction 3
The binomial coefficient n k
is the number of k-element subsets of an n-element set. Here is another way to think of n k
. Let A be an n-element set and suppose we have a supply of labels; we have k labels that say good and n k labels that say bad. In how many ways can we affix exactly one label

Mathematics: A Discrete Introduction 3
. Let A be an n-element set. Suppose we have three types of labels to assign to the elements of A. We can call these labels good, bad, and ugly or give them less interesting names such as Type 1, Type 2, and Type 3. Let a; b; c 2 N. Define the symbol n a b c
to be the number of ways to label the el

Mathematics: A Discrete Introduction 3
Let n; a; b; c 2 N with a C b C c D n. Please prove the following: a. n a b c
D n a
na b
. b. n a b c
D n abc. c. If a C b C c 6D n, then n a b c
D 0.

Mathematics: A Discrete Introduction 3
Let n 2 N. Prove .x C y C z/n D X aCbCcDn n a b c! x ay b z c where the sum is over all natural numbers a; b; c with a C b C c D n.

Mathematics: A Discrete Introduction 3
A poker hand consists of 5 cards chosen from a standard deck of 52 cards. How many different poker hands are possible?

Mathematics: A Discrete Introduction 3
Poker continued. There are a variety of special hands that one can be dealt in poker. For each of the following types of hands, count the number of hands that have that type. a. Four of a kind: The hand contains four cards of the same numerical value (e.g., four jacks) and another card. b. Three of a

Mathematics: A Discrete Introduction 3
It is silly to compute .x C y/20 by expanding it to a million terms and then collecting like terms. A much better way is to calculate .x C y/2 and collect like terms. Then multiply that result by .x C y/ and collect like terms to give .x C y/3 . Now multiply that again by .x C y/ and so on until you

Mathematics: A Discrete Introduction 3
First of all, please verify that n 4
D n.n 1/.n 2/.n 3/=4. We can think of this as a polynomial expression and substitute n D 1=2 into the polynomial representation of n 4
(even though this doesnt make sense with the definition of binomial coefficient) to get 1 2 4 ! D 1 2
3 2
5 2
7 2
4 D

Mathematics: A Discrete Introduction 3
To compute n k
by generating Pascals triangle, it is not necessary to generate the entire triangle down to row n; you need only the part of the triangle in a 90 wedge above n k
. Estimate how many addition problems you would need to perform to calculate 100 30
by this method. How many addition

Mathematics: A Discrete Introduction 3
Use a computer to print out a very large copy of Pascals triangle, but with a twist. Instead of printing the number, print a dot if the number is odd and leave the location blank if the number is even. Produce at least 64 rows. Note that the computer doesnt actually need to compute the entries in Pas