Pascal’s Arithmetical Triangle

Section 3.1 Pascal’s Arithmetical Triangle

Investigate!

In chess, a rook can move only in straight lines (not diagonally). How many ways can the rook in the top-left corner travel to the bottom right corner of the board, moving only down and to the right?

$An 8x8 checkerboard containing an image of a rook chess piece in the top left corner.$

An 8x8 checkerboard containing an image of a rook chess piece in the top left corner. The square in the third row, third column contains the number 6.

🔗

To get started answering this question, let’s find the number of paths to every square of the chess board.

🔗

(a)

🔗

The 6 in the square in the 3rd row and column represents that there are 6 different paths to that square, even though there are only four squares the rook must move through to get there. One path is DDRR (down down right right). Find the other 5.

🔗

(b)

🔗

How many paths are there to the square in row 4, column 2 (diagonally down and to the left of the 6)? List out all the paths with D/R strings.

🔗

(c)

🔗

How many paths are there to the square in row 4, column 3 (directly below the 6)? List out all the paths with D/R strings.

🔗

(d)

🔗

How do the numbers you have filled in so far relate to each other? Why does this make sense?

🔗

(e)

🔗

Continue filling in the chessboard, either counting D/R strings directly or using your observation from the previous step.

🔗

In the 1653, Blaise Pascal, concerned with questions that would lay the foundation of probability theory, collected a number of facts about a triangular array of numbers in his Treatise on Arithmetical Triangle. This arrangement of numbers appeared as early as the 10th century in China, India, and Persia. The Chinese and Persian treatment of the triangle was in service of what we would now consider algebra: finding

n

th roots, essentially solving polynomial equations. The numbers in the triangle appear as solutions to counting problems in Indian texts: from six tastes, how many combinations of one, or two, or three,... can you make? European mathematicians in the 14th century presented the triangle as a table of figurate numbers (numbers that can be arranged in a geometric shape), which were the themselves the centerpiece of the work of Pythagoras and his followers.

🔗

So what is this remarkable triangle that holds the secrets of so many different mathematical problems? Behold, Pascal’s Triangle:

The first 17 rows of Pascal’s Triangle. — 🔗
Figure 3.1.1. Pascal’s Triangle

🔗

Spend some time gazing at the beauty of this triangle. What do you notice? What do you wonder? Look specifically at the 5th row (we call the 1 on the top row 0, so row 5 is 1, 5, 10, 10, 5, 1). How do the numbers in this row relate to the numbers above them? Notice that

5 = 1 + 4

and

10 = 4 + 6 .

Does this occur anywhere else in the triangle?

🔗

Indeed, every number in the triangle is the sum of the two numbers above it. Let’s take this as our definition of Pascal’s Triangle. We can then generate as many rows of the triangle as we like. It is this additive definition that was used in China and Persia to find

n

th roots, and we will briefly mention this use at the end of this section. However, we are interested in counting questions, so our main goal now is to observe how the numbers of Pascal’s triangle are answers to a variety of counting questions.

🔗

Here are some apparently different discrete objects we can count: lattice paths, bit strings, subsets, and pizzas. We will give an example of each type of counting problem (and say what these things even are). As we will see, the numbers in Pascal’s triangle are the answers to all of these questions.

🔗

Before we jump in, a little bit of notation. Let’s give each number in Pascal’s triangle a name, based on its position. Think of each number as being in a row and a column: rows are counted down, starting at 0, and columns are counted in from the left, also starting at 0. The entry in row

n

and column

k

will be denoted

(\binom{n}{k}) .

For example, the

(\binom{6}{3}) = 20,

since that is the value in row 6, column 3. For reasons that will become clear soon, we pronounce

(\binom{n}{k})

as “

n

choose

k .

” We can rewrite the triangle with these names:

$Triangular array of binomial coefficients. Each lower row extends equally on both sides beyond the row above. Top row contains 0 choose 0. Second row contains 1 choose 0 and 1 choose 1 (from left to right). Third row contains 2 choose 0, 2 choose 1, and 2 choose 2. Below that the row contains 3 choose 0, 3 choose 1, 3 choose 2, and 3 choose 3. The bottom row contains 4 choose 0 through 4 choose 4.$

🔗

Subsection Lattice Paths

🔗

The integer lattice is the set of all points in the Cartesian plane for which both the

x

and

y

coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines.

🔗

A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the point

(0, 0)

(3, 2) :

$A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the third dot on the bottom row, then turns up and runs to the top dot in that column, then turns right and runs to the top-right dot.$

$A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom up to the top left dot, and then to the top-right dot.$

$A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the second dot on the bottom row, then turns up and runs to the next dot above it, then turns right and runs to the middle right dot, and finally turns up and runs to the top-right dot.$

🔗

Notice to ensure the path is the shortest possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be five steps. Thus each path has length five.

🔗

The counting question we will ask is this: how many lattice paths are there between

(0, 0)

and

(3, 2) ?

In this case, drawing all the paths wouldn’t take too long. Or we could list each path as a string of “directions” such as

x x y y x,

y y x x x,

x y x x y,

which correspond to the three paths draw above, where an

x

means travel one unit in the

x

direction, and similarly for

y .

We would get the following ten paths:

\begin{matrix} x x x y y x x y x y x y x x y y x x x y \\ x x y y x x y x y x y x x y x x y y x x y x y x x y y x x x . \end{matrix}

🔗

As the points we are traveling between get further apart though, we will want to find a more efficient way to count the paths.

🔗

Let’s take what we learned from the rook paths (which are, gasp, actually lattice paths). Consider the lattice shown below:

$A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). The dot on the top row directly to the left of (3,2) is labeled A; the dot directly below (3,2) is labeled B.$

🔗

Any lattice path from (0,0) to (3,2) must pass through exactly one of

A

and

B .

The point

A

is 4 steps away from (0,0) and two of them are in the

x

direction. The last step is also in the

x

direction, so the paths from (0,0) to (3,2) that pass through

A

are exactly the six strings we listed above that end in an

x .

For the paths that pass through point

B,

the last step will be in the

y

direction, so the paths from (0,0) to (3,2) that pass through

B

are exactly the four strings we listed above that end in a

y .

So the total number of paths to (3,2) is just

6 + 4 .

🔗

The general observation here is that to find the number of paths that start at

(0, 0)

and end at

(m, n),

we can find the number of paths to the point directly to the left of the end point,

(m - 1, n)

and add the number of paths to the point directly below the end point,

(m, n - 1) .

This is exactly the same way that Pascal’s triangle is generated! Indeed, if we rotate the lattice appropriately, so the point

(0, 0)

is at the top of the triangle and the axes along the sides of the triangle, we see that the numbers in Pascal’s triangle give us exactly the number of paths to each lattice point.

$Integer lattice overlayed on Pascal’s triangle$

🔗

To make this observation helpful for actually finding the number of paths from the origin to a given point, we note that it is the length of the path that determines the row of Pascal’s triangle, and the number of steps in the

y

direction that says how far into the triangle we are: the column of Pascal’s triangle.

🔗

Example 3.1.2.

🔗

How many lattice paths are there from

(0, 0)

(4, 7) ?

Solution.

The length of these paths is

4 + 7 = 11 .

Look at the 11th row of Pascal’s triangle:

1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1 .

Count in to the 7th position (remembering that the 1 is in position 0) give us

(\binom{11}{7}) = 330

different paths.

🔗

Subsection Bit Strings

🔗

“Bit” is short for “binary digit,” so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings:

1001 0 1111 1010101010 .

🔗

The number of bits (0’s or 1’s) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1’s. The number of 1’s in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.

🔗

Definition 3.1.3. Bit Strings.

🔗

An $n$ -bit string is a bit string of length $n .$ That is, it is a string containing $n$ symbols, each of which is a bit, either 0 or 1.
The weight of a bit string is the number of 1’s in it.
$B_{k}^{n}$ is the set of all $n$ -bit strings of weight $k .$

🔗

For example, the elements of the set

B_{2}^{3}

are the bit strings 011, 101, and 110. Those are the only strings containing three bits exactly two of which are 1’s.

🔗

The counting questions: How many 5-bit strings have weight 3? In other words, we are asking for the cardinality

| B_{3}^{5} | .

🔗

Let’s just list them and see how many there are.

\begin{matrix} 11100 11010 10110 01110 \\ 11001 10101 01101 10011 01011 00111 . \end{matrix}

🔗

Great. Ten of them. Actually, I have a confession: I didn’t type all of these from scratch. Instead I just modified the list of 10 lattice paths from (0,0) to (3,2) that we found earlier. Each

x

became a 1 and each

y

became a 0. After all, any lattice path with length

n

that requires

k

steps in the

x

direction can be represented by a string of

n

symbols of two types, with

k

of those symbols being of one type. Whether we call the two symbols

x

and

y

or we call them

1

and

0

will not change how many strings we get.

🔗

It is not surprising then that the same relationship between Pascal’s triangle and lattice paths holds for bit strings. Look at the 10 strings above. The first row contains all the bit strings of

B_{3}^{5}

that end in a 0. Before that ending 0, we have a string in

B_{3}^{4},

since it must have length 4 and weight 3 (the ending 0 adds one to the length, but adds zero to the weight). The second row contains all the bit strings of

B_{3}^{5}

that end in a 1. Before that ending 1, we have a string in

B_{2}^{4},

since it must have length 4 and weight 2 (the ending 1 adds one to the length, but adds one to the weight). So the number of 5-bit strings of weight 3 is the sum of the number of 4-bit strings of weight 3 and the number of 4-bit strings of weight 2. In symbols:

| B_{3}^{5} | = | B_{3}^{4} | + | B_{2}^{4} | .

🔗

Now we have two good reasons to believe that Pascal’s triangle tells us the number of bit strings of a given weight: there is a one-to-one correspondence between lattice paths and bit strings, and the same recursive relationship holds for bit strings as it does for generating Pascal’s triangle. So we can now use the triangle to count bit strings.

🔗

Example 3.1.4.

🔗

How many 11-bit strings have weight 5?

Solution.

There will be

(\binom{11}{5})

such strings. From Pascal’s triangle, we see that

(\binom{11}{5}) = 462

🔗

Subsection Subsets and Pizzas

🔗

A subset of a set

A

is any set all of whose elements are also in

A .

Think of starting with the set

A

and removing some (or none or all) of its elements: the resulting set is a subset of

A .

(More information about sets can be found in Section 0.2 and Section 5.1.)

🔗

Suppose we look at the set

A = {1, 2, 3, 4, 5} .

How many subsets of

A

contain exactly 3 elements? Let’s list them all:

\begin{matrix} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4} \\ {1, 2, 5} {1, 3, 5} {2, 3, 5} {1, 4, 5} {2, 4, 5} {3, 4, 5} . \end{matrix}

🔗

Again, we see there are ten. In fact, we have listed them in the same order as we listed the ten 5-bit strings of weight 3 and the ten lattice paths from (0,0) to (3,2). Wait, does this even make sense? In what way is a subset the same as a bit-string?

🔗

Think of each bit in a bit string as representing one of the elements in a set. So the set

A

has five elements, so we need five bits to represent a subset of

A .

If the bit in position

n

is a 0, that means we do not include

n

in our subset, while a 1 in that position tells us that

n

is in the subset. Three 1’s means we have said, “yes” to three elements.

🔗

Example 3.1.5.

🔗

Which subsets of

{1, 2, 3, 4, 5, 6}

correspond to the bit strings below?

101011 001000 111111 000000

Solution.

Here we are not fixing the weight of the strings, so our subsets will not all have the same size. Here is the correspondence:

$101011$	${1, 3, 4, 6}$
$001000$	${3}$
$111111$	${1, 2, 3, 4, 5, 6}$
$000000$	$\emptyset$

The last subset is the empty set: the set that contains no elements (we could have also written

{}

). This is a subset of every set!

🔗

Remark 3.1.6.

🔗

What we have done here is give a bijection between the set of 5-bit strings of weight 3 and the set of 3-element subsets of

A .

A bijection is a function

f : X \to Y

such that each element of

Y

is the image of exactly one element from

X .

You can prove that if there is a bijection between two sets, then they have the same number of elements. This is a common counting technique we will use in the upcoming sections.

🔗

This example illustrates that once again, Pascal’s triangle can give us the answer to a counting question. The number of

k

-element subsets of a set with

n

elements is the same as the number of

n

-bit strings of weight

k,

and that is the number in row

n,

column

k

of the triangle:

(\binom{n}{k}) .

🔗

Example 3.1.7.

🔗

How many subsets of the set

{a, b, c, d, e, f, g}

exactly 4 elements?

Solution.

The set contains 7 elements, so the number of 4-element subsets is the same as the number of 7-bit strings of weight 4, namely

(\binom{7}{4}) = 35 .

🔗

At this point I’m sure we are all getting pretty hungry, so let’s get some pizza. But which pizza shall we order? Let’s not overdue it and just choose three toppings from the ten available. How many different pizzas can we order?

🔗

Aha! So that’s why we care about counting subsets!! Each pizza choice is nothing more than a 3-element subset of the set of 10 toppings. We now know how to count this:

(\binom{10}{3}) = 120

different pizzas.

🔗

What if we want an Italian soda with dinner? Let’s say we want to add two different flavored syrups from the 13 available. How many different sodas are possible? This is just the number of 2-element subsets of a set with 13 elements:

(\binom{13}{2}) = 78 .

🔗

This is why we pronounce

(\binom{n}{k})

as “

n

choose

k

”. It is the number of ways to choose

k

items from a collection of

n

items, since choosing

k

elements is exactly how you build a

k

-element subset.

🔗

We can view counting lattice paths as choosing

k

out of

n

things: of the

n

steps on the path, we choose

k

of them to be in the

x

direction. Bit strings can also be thought of in this way: of the

n

bits in the string, we choose

k

of them to be 1’s.

🔗

We now know ho to answer all sorts of real world counting problems, as long as they are really nothing more than asking for the number of subsets of a set. Pascal’s triangle contains all these answers.

🔗

Counting Subsets.

🔗

The number of

k

-element subsets of a set with

n

elements is the number in row

n,

column

k

of Pascal’s triangle:

(\binom{n}{k}),

which we read as “

n

choose

k .

” This is the number of ways to choose

k

items from a collection of

n

items.

🔗

Subsection Algebra?

🔗

Earlier we said that one of the original uses for Pascal’s triangl was to solve problems in algebra. What does counting subsets (or bit strings or lattice paths) have to do with algebra?

🔗

Suppose you expand the binomial expression

(x + 1)^{6}

(i.e., multiply the binomial

x + 1

by itself six times). This can be tedious to do by hand, but a computer algebra system such a sage can do this easily.


    
        
xxxxxxxxxx
 
1
expand((x+1)^6)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Do the coefficients look familiar? Consider the 6th row of Pascal’s triangle:

1 6 15 20 15 6 1 .

🔗

Why are these the coefficients?

🔗

Checkpoint 3.1.8.

🔗

Modify the sage code above to expand

(x + 1)^{10} .

What is the coefficient of

x^{6} ?

🔗

To see why this is more than just a coincidence, let’s look at the expansion of

(x + y)^{3}

and do it very carefully. We are really multiplying out

(x + y) (x + y) (x + y) .

🔗

This means we must distribute the binomials, which looks like the following.

\begin{aligned} (x + y)^{3} = & (x + y) (x + y) (x + y) \\ = & [(x + y) (x + y)] x + [(x + y) (x + y)] y \\ = & [(x + y) x + (x + y) y] x + [(x + y) x + (x + y) y] y \\ = & [x x + y x + x y + y y] x + [x x + y x + x y + y y] y \\ = & x x x + y x x + x y x + y y x + x x y + y x y + x y y + y y y . \end{aligned}

🔗

This repeated distribution results in a sum of terms, each the product of three variables. We see that each term is the result of choosing either the

x

or the

y

from each of the binomials. For example, the term

x y x

is the result of choosing the

x

from the first binomial, the

y

from the second, and the

x

from the third.

🔗

When we collect like terms, to find the coefficient for the

x^{2} y

term, for example, we collect all the terms in which we have chosen

x

two times (and

y

the other one time). Alternatively, the

x^{2} y

term comes from all the strings with two

x

and one

y,

just like a bit string or lattice path. No matter how you think of it, the result is that we have

(\binom{3}{2}) = 3

terms with the form

x^{2} y .

🔗

Hopefully it is clear that this generalizes to the expansion of

(x + y)^{n}

for any positive integer

n .

This is known as the Binomial Theorem.

🔗

Theorem 3.1.9. Binomial Theorem.

🔗

The

n

th row of Pascal’s triangle gives the coefficients of the expansion of

(x + y)^{n} .

That is, for any positive integer

n,

(x + y)^{n} = (\binom{n}{0}) x^{n} + (\binom{n}{1}) x^{n - 1} y + \dots + (\binom{n}{n - 1}) x y^{n - 1} + (\binom{n}{n}) y^{n} .,

🔗

so the coefficient of

x^{k} y^{n - k}

(\binom{n}{k}) .

🔗

For this reason, the number in Pascal’s Triangle are often called binomial coefficients.

🔗

Example 3.1.10.

🔗

Without multiplying out the binomial, give the exapnsion of

(x + y)^{5} .

Solution.

We take the 5th row of Pascal’s triangle:

1, 5, 10, 10, 5, 1 .

The expansion is then,

(x + y)^{5} = x^{5} + 5 x^{4} y + 10 x^{3} y^{2} + 10 x^{2} y^{3} + 5 x y^{4} + y^{5} .

🔗

Reading Questions Reading Questions

🔗

1.

🔗

Why is the number of lattice paths from

(0, 0)

(3, 5)

the same as the number of

8

-bit strings with weight 5?

🔗

2.

🔗

Which of the following counting questions have the answer

(\binom{11}{5}) ?

Select all that apply.

How many lattice paths are there from $(0, 0)$ to $(11, 5) ?$
Careful, paths from $(0, 0)$ to $(11, 5)$ will have length $11 + 5 = 16,$ so the answer to this question would be $(\binom{16}{5}) .$
How many subsets of ${1, 2, \dots, 11}$ contain exactly 5 elements?
Correct. We must choose 5 out of 11 elements.
How many 11-bit strings have weight 5?
Exactly. Of the 11 bits in the string, we must choose 5 to be 1’s.
How many ways can you select 5 flavors of ice cream for a giant sundae from 11 available flavors?
Yes. This is the same as choosing 5 elements from a set of 11.

🔗

3.

🔗

The number of subsets of

{1, 2, \dots, 8}

of size 3 is the same as the number of subsets of

{1, 2, \dots, 7}

of size either

2

3 .

Explain why this makes sense.

🔗

Exercises Practice Problems

🔗

1.

🔗

Use Pascal’s triangle to find the numeric values of the following:

🔗

2.

🔗

Compute the following sums of the rows of Pascal’s triangle: Now based on your work in the above calculations, give a guess for the sum of the 10th row of Pascal’s triangle.

🔗

3.

🔗

A pizza parlor offers 10 different toppings, one of which is pineapple. How many 4-toppings pizzas are there that have pineapple as one of their toppings? How many 4-topping pizzas are there that do not have pineapple as a topping? How many 4-topping pizzas are there in total?

🔗

4.

🔗

The same question as above, but with sets.

🔗

5.

🔗

Consider the lattice paths from (3,4) to (8,10). How long is each such path? How many steps are in the x-direction? How many different paths are there?

🔗

6.

🔗

How many lattice paths are there from (a,b) to (c,d)?

🔗

7.

🔗

Let

S = {1, 2, 3, 4, 5, 6, 7}

How many subsets are there total?
How many subsets have ${2, 3, 5}$ as a subset?
How many subsets contain at least one odd number?
How many subsets contain exactly one even number?

Solution.

$2^{7} = 128$ subsets. We need to select yes/no for each of the 7 elements.
$2^{4} = 16$ subsets. We need to select yes/no for each of the remaining 4 elements.
$2^{7} - 2^{3} = 120$ subsets. We subtract the number of subsets which do not contain any odd numbers ( $2^{3}$ -select yes or no for each even element) from the total number of possible subsets.
$(\binom{3}{1}) \cdot 2^{4} = 48$ subsets. First pick the even number. Then say yes or no to each of the odd numbers.

🔗

8.

🔗

Let

S = {1, 2, 3, 4, 5, 6}

How many subsets are there of cardinality 4?

(Note: you can enter “C(n,k)” for $(\binom{n}{k}) .$ )
How many subsets of cardinality 4 have ${2, 3, 5}$ as a subset?
How many subsets of cardinality 4 contain at least one odd number?
How many subsets of cardinality 4 contain exactly one even number?

Solution.

$(\binom{6}{4}) = 15$ subsets.
$(\binom{3}{1}) = 3$ subsets. We need to select 1 of the 3 remaining elements of $S$ to be in the subset.
$(\binom{6}{4}) = 15$ subsets. All subsets of cardinality 4 must contain at least one odd number.
$(\binom{3}{1}) = 3$ subsets. Select 1 of the 3 even numbers. The remaining 3 odd numbers of $S$ must all be in the set.

🔗

9.

🔗

Let

A = {1, 2, 3, 4, 5} .

How many subsets of $A$ are there? That is, find $| P (A) | .$
How many subsets of $A$ contain exactly 4 elements?
How many subsets of $A$ contain only even numbers?
How many subsets of $A$ contain an even number of elements?

Solution.

There are $32$ subsets. This is $2^{5},$ which makes sense because we are deciding yes or no on whether to include each element of $A$ in the subset.
Of the 5 elements in $A,$ we must choose 4 of them to be in the subset. So $(\binom{5}{4}) = 5 .$
For each of the 5 elements from $A,$ we must decide yes or no on whether to include them in the subset. However, for the odd numbers, we only have one choice: no. So there are only 2 elements we have two choices for, so the answer is $2^{2} = 4 .$ (Note, if you wish to exclude the empty set - it does not contain odd numbers, but no evens either - then you could subtract 1).
Count the number of subsets with each possible even cardinality:

$(\binom{5}{0}) + (\binom{5}{2}) + \dots . . . = 16$

🔗

10.

🔗

How many

11

-bit strings (that is, bit strings of length 11) are there which:

Start with the sub-string 011?
Have weight 8 (i.e., contain exactly 8 1’s) and start with the sub-string 011?
Either start with $011$ or end with $01$ (or both)?
Have weight 8 and either start with $011$ or end with $01$ (or both)?

Solution.

$2^{8} = 256 .$ You have 2 choices for each of the remaining 8 bits.
$(\binom{8}{6}) = 28 .$ You need to choose 6 of the remaining 8 bits to be 1’s.
704. There are $2^{8}$ strings that start with 011, and another $2^{9}$ which end with 01 (we choose 1 or 0 for 9 bits). However, we count the strings that start with 011 and end with 01 twice - there are $2^{6}$ such strings. So using PIE, we have $2^{8} + 2^{9} - 2^{6} = 704$
58. There are $(\binom{8}{6}) = 28$ strings of weight 8 which start with 011, and another $(\binom{9}{7}) = 36$ which end with 01. We have over counted again - there are weight 8 strings which both start with 011 and end with 01, in fact $(\binom{6}{5}) = 6$ of them. So all together we have $28 + 36 - 6 = 58$ strings.

🔗

11.

🔗

You break your piggy-bank to discover lots of pennies and nickels. You start arranging these in rows of 10 coins.

You find yourself making rows containing an equal number of pennies and nickels. For fun, you decide to lay out every possible such row. How many coins will you need?
How many coins would you need to make all possible rows of 10 coins (not necessarily with equal number of pennies and nickels)?

Solution.

We can think of each row as a 10-bit string of weight 5 (since of the 10 coins, we require 5 to be pennies). Thus there are $(\binom{10}{5}) = 252$ rows possible. Each row requires 10 coins, so if we want to make all the rows at the same time, we will need 2520 coins, half of them nickels and half of them pennies.
Now there are $2^{10} = 1024$ rows possible, which is also $(\binom{10}{0}) + (\binom{10}{1}) + (\binom{10}{2}) + \dots + (\binom{10}{10}),$ if you break them up into rows containing 0, 1, 2, etc. pennies. Thus, since there are 10 coins in each row, we need $10 \cdot 1024 = 10240$ total coins.

🔗

12.

🔗

How many 11-bit strings contain 5 or more 1’s?

Solution.

Count the number of strings with each permissible number of 1’s separately, then add them up. So there are

(\binom{11}{5}) + (\binom{11}{6}) + \dots (\binom{11}{11}) = 1486

strings.

🔗

13.

🔗

How many subsets of

{0, 1, \dots, 9}

have cardinality 7 or more?

Hint.

Break the question into 4 cases.

Solution.

This is the same as a question about 7-bit strings, since we can think of each subset as a 7-bit string with a 1 representing that we include that element in the subset.

(\binom{10}{7}) + (\binom{10}{8}) + \dots + (\binom{10}{10}) = 176

subsets.

🔗

14.

🔗

What is the coefficient of

x^{14}

(x + 3)^{19} ?

Solution.

To get an

x^{14},

we must pick 14 of the 19 factors to contribute an

x,

leaving the other 5 to contribute a 3. There are

(\binom{19}{14})

ways to select these 14 factors. So the term containing an

x^{14}

will be

(\binom{19}{14}) x^{14} 3^{5} .

In other words, the coefficient of

x^{14}

(\binom{19}{14}) 3^{5} = 2.8256 \times 10^{6} .

🔗

15.

🔗

What is the coefficient of

x^{5}

in the expansion of

(x + 2)^{19} + x^{4} (x + 3)^{20} ?

Solution.

To get an

x^{5}

from the first term, we must pick 5 of the 19 factors to contribute an

x,

leaving the other 14 to contribute a 2. There are

(\binom{19}{5})

ways to select these 5 factors, so the coefficient will be

(\binom{19}{5}) * 2^{14} .

Now we must choose 1 of the factors in the second term to contribute an

x,

leaving the other 19 terms to contribute a 3. This gives us

(\binom{20}{1}) * 3^{19}

for the coefficient resulting from this term. In total, the term containing an

x^{5}

will be

(\binom{19}{5}) * 2^{14} + (\binom{20}{1}) * 3^{19} = 2.34357 \times 10^{10} .

🔗

16.

🔗

How many shortest lattice paths start at

(1, 1)

and

end at $(15, 15) ?$
end at $(15, 15)$ and pass through $(7, 2) ?$
end at $(15, 15)$ and avoid $(7, 2) ?$

Solution.

$(\binom{28}{14}) = 4.01166 \times 10^{7}$ paths. The paths all have length 28 (14 steps up and 14 steps right), we just select which 14 of those 28 should be right.
$(\binom{7}{6}) (\binom{21}{8}) = 1.42443 \times 10^{6}$ paths. First travel to $(7, 2),$ and then continue on to $(15, 15)$ ) .
$(\binom{28}{14}) - (\binom{7}{6}) (\binom{21}{8}) = 3.86922 \times 10^{7}$ paths. Remove all the paths that you found in part (b).

🔗

17.

🔗

Gridtown USA, besides having excellent donut shops, is known for its precisely laid out grid of streets and avenues. Streets run east-west, and avenues north-south, for the entire stretch of the town, never curving and never interrupted by parks or schools or the like.

🔗

Suppose you live on the corner of 4th and 4th and work on the corner of 18th and 18th. Thus you must travel 28 blocks to get to work as quickly as possible.

How many different routes can you take to work, assuming you want to get there as quickly as possible?

🔗

Now suppose you want to stop and get a donut on the way to work, from your favorite donut shop on the corner of 17th ave and 14th st. How many routes to work, stopping at the donut shop, can you take (again, ensuring the shortest possible route)?

🔗

Disaster Strikes Gridtown: there is a pothole on 5th ave between 7th st and 8th st. How many routes to work can you take avoiding that unsightly (and dangerous) stretch of road?

🔗

The pothole has been repaired (phew) and a new donut shop has opened on the corner of 5th ave and 7th st. How many routes to work drive by one or the other (or both) donut shops? Hint: the donut shops serve PIE.

🔗

18.

🔗

Suppose you are ordering a calzone from D.P. Dough. You want 4 distinct toppings, chosen from their list of 10 vegetarian toppings.

How many choices do you have for your calzone?
How many choices do you have for your calzone if you refuse to have green pepper as one of your toppings?
How many choices do you have for your calzone if you insist on having green pepper as one of your toppings?

🔗

How do the three questions above relate to each other? Do you see why this makes sense?

Solution.

$(\binom{10}{4}) = 210$ choices, since you have to select a 4-element subset of the set of 10 toppings.
$(\binom{9}{4}) = 126$ choices, since you must select 4 of the 9 non-green pepper toppings.
$(\binom{9}{3}) = 84$ choices, since you must select 3 of the remaining 9 non-green pepper toppings to have in addition to the green pepper.

Note that

210 = 126 + 84

choices, which makes sense because every 4-topping pizza either has green pepper or does not have green pepper as a topping.

🔗

Exercises Additional Exercises

🔗

1.

🔗

How many lattice paths are there from

(0, 0)

(8, 3) .

How many lattice paths are there from

(0, 0)

(3, 8) ?

Why does it make sense that these two numbers are the same? Explain your reasoning.

🔗

2.

🔗

Suppose you are counting lattice paths from

(0, 0)

(4, 3) .

We know that the number of such paths is

(\binom{4 + 3}{4}) = (\binom{7}{6}) = 35 .

Here is another way to count these paths: consider the cases for where your first step in the

y

-direction is. There are five differnt options here; compute the number of paths for each case.

🔗

(a)

🔗

How many paths are there from

(0, 0)

(4, 3)

where the first step is in the

y

-direction (i.e., paths that pass through the point

(0, 1)

🔗

(b)

🔗

How many paths are there from

(0, 0)

(4, 3)

that first move one step in the

x

-direction, then one step in the

y

-direction (so they pass through the points

(1, 0)

and then

(1, 1)

🔗

(c)

🔗

List the remaining three cases and how many paths there are for each case.

🔗

(d)

🔗

Verify that the sum of the paths in each case is 35. Then describe where all these numbers are in Pascal’s triangle. Find another instance of this pattern and verify that it works.

🔗