math7a-2020-11-22-file2src

Homework 9: Pascal’s triangle, applications
HW9 is Due December 6; submit to Google classroom 15 minutes before the class time.
1. Pascal’s triangle and the binomial coefficients.
Every entry in it is obtained as the sum of two entries above it. The k-th entry in the n-th
line is denoted by ( nk) , or by n C . Note that both n and k are counted from 0, not from 1:
k
for example, ( ) =15, ( )=1. Now let us think about other applications of these numbers.
6 3
2 0
2. Example applications of the binomial coefficients

a) Chessboard paths
In the previous handout we saw that these numbers appear in a problem about counting
paths from the lower left corner of the board to the upper right corner. We observed the
following:
( nk) = the number of paths on the chessboard going k units up and n − k units to the right.
For example, the number of paths that go to the upper right corner of a 6 × 6 board is equal to
(105) , as each
such path must have 5 steps to the right and 5 steps up, taken in any order. This means that we
have total of n = 10 steps made of k = 5 steps up and the rest, 10 - 5 = 5 steps to the right. Or,
form 10 possible moves we pick 5 to be up.
b) Words with Rs and Us or 1s and 0s

Each of these paths on the board going up and to the right can be written as a sequence of
steps; let R be a step to the right, and U a step up. For example, a possible path is:
RRRRRUUUUU will go five steps to the right and five steps up, eventually ending in the upper
right corner of a 6 × 6 board. Another possible sequence is RRUUURRRUU. There is a
correspondence between paths of length n and strings of length n consisting of Rs and Us only.
Now let us switch Rs to 0s and Us to 1s. We already know that ( nk) = is the number of paths
going k units up and n − k units to the right. This
corresponds to words of length n with k Us and n − k Rs, which is the same as the number of
strings of length n with k 1s and n − k Us. We have the following result:
1
( nk) = the number of words with length n that can be written using k ones and n − k
zeroes or k Us and n-k Rs.
c) Combinations: the choice of k things from a set of n things without repetition

(“replacement”) and where the order does not matter.
Consider now a set on n elements; let’s number them from 1 to n. Then, for each string of length
n with 0s and 1s, we can select those elements that correspond to 1s and omit those elements
that correspond to 0s. In this way, we will get a subset of size k. This is another property of the
binomial coefficients:
( nk) = the number of ways to choose k items out of n (order doesn’t matter)
3. Summary: binomial coefficients represent
()
n C k= n
k
= the number of paths on the chessboard going k units up and n − k to the right
= the number of words that can be written using k ones and n − k zeroes
= the number of ways to choose k items out of n (order doesn’t matter)
Homework problems
Instructions: Please always write solutions on a separate sheet of paper. Solutions
should include explanations. I want to see more than just an answer: I also want to see
how you arrived at this answer, and some justification why this is indeed the answer. So
please include sufficient explanations, which should be clearly written so that I can
read them and follow your arguments.
Note: In the problems below, you can give your answer as a binomial coefficient without
calculating it. If you want to calculate it, use the Pascal’s triangle to find the value of
n
k
, ()
where k is the k-th element in the n-th row of the Pascal triangle, counting from 0.
1. How many “words” of length 5 one can write using only letters U and R, namely 3 U’s
and 2 R’s? What if you have 5 U’s and 3 R’s? [Hint: each such “word” can describe a
path on the chessboard, U for up and R for right. . . ]
2. How many sequences of 0 and 1 of length 10 are there? sequences of length 10
containing exactly 4 ones? exactly 6 ones?
3. If we toss a coin 10 times, what is the probability that all will be heads? that there will
be exactly one tails? 2 tails? exactly 5 tails?
4. A drunkard is walking along a road from the pub to his house, which is located 1 mile
north of the pub. Every step he makes can be either to the north, taking him closer to
home, or to the south, back to the pub — and it is completely random: every step with
can be north of south, with equal chances. What is the probability that after 10 steps,
he will move:
a) 10 steps north
2
b) 10 steps south
c) 4 steps north
d) will come back to the starting position
5. If you have a group of 4 people, and you need to choose one to go to a competition,
how many ways are there to do it? if you need to choose 2? if you need to choose 3?
6. How many ways are there to select 5 students from a group of 12?
7. In a meeting of 25 people, each much shake hands with each other. How many
handshakes are there altogether?
8. (a) An artist has 12 paintings. He needs to choose 4 paintings to include in an art
show. How many ways are there of doing this?
(b) The same artist now needs to choose 4 paintings to include in a catalog. How
many ways are there to do this? (In the catalog, unlike the show, the order matters).

math7a-2020-11-22-file2src

Uploaded by

Copyright:

Available Formats

math7a-2020-11-22-file2src

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

math7a-2020-11-22-file2src

Uploaded by

Copyright:

Available Formats

Homework 9: Pascal’s triangle, applications

1. Pascal’s triangle and the binomial coefficients.

2. Example applications of the binomial coefficients

b) Words with Rs and Us or 1s and 0s

c) Combinations: the choice of k things from a set of n things without repetition

3. Summary: binomial coefficients represent

You might also like