1.E: Counting (Exercises)

\( \def\d{\displaystyle}\)
\( \newcommand{\f}[1]{\mathfrak #1}\)
\( \newcommand{\s}[1]{\mathscr #1}\)
\( \def\N{\mathbb N}\)
\( \def\B{\mathbf{B}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\Z{\mathbb Z}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\Q{\mathbb Q}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\R{\mathbb R}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\C{\mathbb C}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\F{\mathbb F}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\A{\mathbb A}\)
\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)
\( \def\X{\mathbb X}\)
\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)
\( \def\E{\mathbb E}\)
\( \def\O{\mathbb O}\)
\( \def\U{\mathcal U}\)
\( \def\pow{\mathcal P}\)
\( \def\inv{^{-1}}\)
\( \def\nrml{\triangleleft}\)
\( \def\st{:}\)
\( \def\~{\widetilde}\)
\( \def\rem{\mathcal R}\)
\( \def\sigalg{$\sigma$-algebra }\)
\( \def\Gal{\mbox{Gal}}\)
\( \def\iff{\leftrightarrow}\)
\( \def\Iff{\Leftrightarrow}\)
\( \def\land{\wedge}\)
\( \def\And{\bigwedge}\)
\( \def\entry{\entry}\)
\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)
\( \def\Vee{\bigvee}\)
\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)
\( \def\imp{\rightarrow}\)
\( \def\Imp{\Rightarrow}\)
\( \def\Fi{\Leftarrow}\)
\( \def\var{\mbox{var}}\)
\( \def\Th{\mbox{Th}}\)
\( \def\entry{\entry}\)
\( \def\sat{\mbox{Sat}}\)
\( \def\con{\mbox{Con}}\)
\( \def\iffmodels{\bmodels\models}\)
\( \def\dbland{\bigwedge \!\!\bigwedge}\)
\( \def\dom{\mbox{dom}}\)
\( \def\rng{\mbox{range}}\)
\( \def\isom{\cong}\)
\(\DeclareMathOperator{\wgt}{wgt}\)
\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)
\( \newcommand{\va}[1]{\vtx{above}{#1}}\)
\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)
\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)
\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)
\( \renewcommand{\v}{\vtx{above}{}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)
\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)
\( \def\ansfilename{practice-answers}\)
\( \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\)
\( \renewcommand{\bar}{\overline}\)
\( \newcommand{\card}[1]{\left| #1 \right|}\)
\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\( \newcommand{\lt}{<}\)
\( \newcommand{\gt}{>}\)
\( \newcommand{\amp}{&}\)

\( \newcommand{\hexbox}[3]{
  \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
  \def\y{-\r*#1-sin{30}*\r*#1}
  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
  \draw (\x,\y) node{#3};
}\)

\(\renewcommand{\bar}{\overline}\)
\(\newcommand{\card}[1]{\left| #1 \right|}\)
\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\(\newcommand{\lt}{<}\)
\(\newcommand{\gt}{>}\)
\(\newcommand{\amp}{&}\)

1.1: Additive and Multiplicative Principles

1

Your wardrobe consists of 5 shirts, 3 pairs of pants, and 17 bow ties. How many different outfits can you make?

Answer

There are 255 outfits. Use the multiplicative principle.

2

For your college interview, you must wear a tie. You own 3 regular (boring) ties and 5 (cool) bow ties.

1. How many choices do you have for your neck-wear?
2. You realize that the interview is for clown college, so you should probably wear both a regular tie and a bow tie. How many choices do you have now?
3. For the rest of your outfit, you have 5 shirts, 4 skirts, 3 pants, and 7 dresses. You want to select either a shirt to wear with a skirt or pants, or just a dress. How many outfits do you have to choose from?

Answer

1. 8 ties. Use the additive principle.
2. 15 ties. Use the multiplicative principle
3. \(5 \cdot (4+3) + 7 = 42\) outfits.

3

Your Blu-ray collection consists of 9 comedies and 7 horror movies. Give an example of a question for which the answer is:

1. 16.
2. 63.

Answer

1. For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick.
2. For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror.

4

We usually write numbers in decimal form (or base 10), meaning numbers are composed using 10 different “digits” \(\{0,1,\ldots, 9\}\text{.}\) Sometimes though it is useful to write numbers hexadecimal or base 16. Now there are 16 distinct digits that can be used to form numbers: \(\{0, 1, \ldots, 9, \mathrm{A, B, C, D, E, F}\}\text{.}\) So for example, a 3 digit hexadecimal number might be 2B8.

1. How many 2-digit hexadecimals are there in which the first digit is E or F? Explain your answer in terms of the additive principle (using either events or sets).
2. Explain why your answer to the previous part is correct in terms of the multiplicative principle (using either events or sets). Why do both the additive and multiplicative principles give you the same answer?
3. How many 3-digit hexadecimals start with a letter (A-F) and end with a numeral (0-9)? Explain.
4. How many 3-digit hexadecimals start with a letter (A-F) or end with a numeral (0-9) (or both)? Explain.

5

Suppose you have sets \(A\) and \(B\) with \(\card{A} = 10\) and \(\card{B} = 15\text{.}\)

1. What is the largest possible value for \(\card{A \cap B}\text{?}\)
2. What is the smallest possible value for \(\card{A \cap B}\text{?}\)
3. What are the possible values for \(\card{A \cup B}\text{?}\)

Answer

1. To maximize the number of elements in common between \(A\) and \(B\text{,}\) make \(A \subset B\text{.}\) This would give \(\card{A \cap B} = 10\text{.}\)
2. \(A\) and \(B\) might have no elements in common, giving \(\card{A\cap B} = 0\text{.}\)
3. \(15 \le \card{A \cup B} \le 25\text{.}\) In fact, when \(\card{A \cap B} = 0\) then \(\card{A \cup B} = 25\) and when \(\card{A \cap B} = 10\) then \(\card{A \cup B} = 15\text{.}\)

6

If \(\card{A} = 8\) and \(\card{B} = 5\text{,}\) what is \(\card{A \cup B} + \card{A \cap B}\text{?}\)

Answer

\(\card{A \cup B} + \card{A \cap B} = 13\text{.}\) Use PIE: we know \(\card{A \cup B} = 8 + 5 - \card{A \cap B}\text{.}\)

7

A group of college students were asked about their TV watching habits. Of those surveyed, 28 students watch The Walking Dead, 19 watch The Blacklist, and 24 watch Game of Thrones. Additionally, 16 watch The Walking Dead and The Blacklist, 14 watch The Walking Dead and Game of Thrones, and 10 watch The Blacklist and Game of Thrones. There are 8 students who watch all three shows. How many students surveyed watched at least one of the shows?

Answer

39 students. Use PIE or a Venn diagram.

8

In a recent survey, 30 students reported whether they liked their potatoes Mashed, French-fried, or Twice-baked. 15 liked them mashed, 20 liked French fries, and 9 liked twice baked potatoes. Additionally, 12 students liked both mashed and fried potatoes, 5 liked French fries and twice baked potatoes, 6 liked mashed and baked, and 3 liked all three styles. How many students hate potatoes? Explain why your answer is correct.

9

For how many \(n \in \{1,2, \ldots, 500\}\) is \(n\) a multiple of one or more of 5, 6, or 7?

Hint:

To find out how many numbers are divisible by 6 and 7, for example, take \(500/42\) and round down.

10

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets.

1. Find \(\card{(A \cup C)\setminus B}\) provided \(\card{A} = 50\text{,}\) \(\card{B} = 45\text{,}\) \(\card{C} = 40\text{,}\) \(\card{A\cap B} = 20\text{,}\) \(\card{A \cap C} = 15\text{,}\) \(\card{B \cap C} = 23\text{,}\) and \(\card{A \cap B \cap C} = 12\text{.}\)
2. Describe a set in terms of \(A\text{,}\) \(B\text{,}\) and \(C\) with cardinality 26.

11

Consider all 5 letter “words” made from the letters \(a\) through \(h\text{.}\) (Recall, words are just strings of letters, not necessarily actual English words.)

1. How many of these words are there total?
2. How many of these words contain no repeated letters?
3. How many of these words start with the sub-word “aha”?
4. How many of these words either start with “aha” or end with “bah” or both?
5. How many of the words containing no repeats also do not contain the sub-word “bad”?

Answer

1. \(8^5 = 32768\) words, since you select from 8 letters 5 times.
2. \(8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720\) words. After selecting a letter, you have fewer letters to select for the next one.
3. \(8 \cdot 8 =64\) words: you need to select the 4th and 5th letters.
4. \(64 + 64 - 0 = 128\) words. There are 64 words which start with “aha” and another 64 words that end with “bah.” Perhaps we over counted the words that both start with “aha” and end with “bah”, but since the words are only 5 letters long, there are no such words.
5. \((8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\) words. All the words minus the bad ones. The taboo word can be in any of three positions (starting with letter 1, 2, or 3) and for each position we must choose the other two letters (from the remaining 5 letters).

12

For how many three digit numbers (100 to 999) is the sum of the digits even? (For example, \(343\) has an even sum of digits: \(3+4+3 = 10\) which is even.) Find the answer and explain why it is correct in at least two different ways.

13

The number 735000 factors as \(2^3 \cdot 3 \cdot 5^4 \cdot 7^2\text{.}\) How many divisors does it have? Explain your answer using the multiplicative principle.

1.2: Binomial Coefficients

1

Let \(S = \{1, 2, 3, 4, 5, 6\}\)

1. How many subsets are there total?
2. How many subsets have \(\{2,3,5\}\) as a subset?
3. How many subsets contain at least one odd number?
4. How many subsets contain exactly one even number?

Answer

1. \(2^6 = 64\) subsets. We need to select yes/no for each of the six elements.
2. \(2^3 = 8\) subsets. We need to select yes/no for each of the remaining three elements.
3. \(2^6 - 2^3 = 56\) subsets. There are 8 subsets which do not contain any odd numbers (select yes/no for each even number).
4. \(3\cdot 2^3 = 24\) subsets. First pick the even number. Then say yes or no to each of the odd numbers.

2

Let \(S = \{1, 2, 3, 4, 5, 6\}\)

1. How many subsets are there of cardinality 4?
2. How many subsets of cardinality 4 have \(\{2,3,5\}\) as a subset?
3. How many subsets of cardinality 4 contain at least one odd number?
4. How many subsets of cardinality 4 contain exactly one even number?

Answer

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

3

Let \(A = \{1,2,3,\ldots,9\}\text{.}\)

1. How many subsets of \(A\) are there? That is, find \(|\pow(A)|\text{.}\) Explain.
2. How many subsets of \(A\) contain exactly 5 elements? Explain.
3. How many subsets of \(A\) contain only even numbers? Explain.
4. How many subsets of \(A\) contain an even number of elements? Explain.

4

How many \(9\)-bit strings (that is, bit strings of length 9) are there which:

1. Start with the sub-string 101? Explain.
2. Have weight 5 (i.e., contain exactly five 1's) and start with the sub-string 101? Explain.
3. Either start with \(101\) or end with \(11\) (or both)? Explain.
4. Have weight 5 and either start with 101 or end with 11 (or both)? Explain.

5

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

1. 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?
2. How many coins would you need to make all possible rows of 6 coins (not necessarily with equal number of pennies and nickels)?

Answer

1. We can think of each row as a 6-bit string of weight 3 (since of the 6 coins, we require 3 to be pennies). Thus there are \({6 \choose 3} = 20\) rows possible. Each row requires 6 coins, so if we want to make all the rows at the same time, we will need 120 coins (60 of each).
2. Now there are \(2^6 = 64\) rows possible, which is also \({6 \choose 0} + {6\choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}\text{,}\) if you break them up into rows containing 0, 1, 2, etc. pennies. Thus we need \(6 \cdot 64 = 384\) coins (192 of each).

6

How many 10-bit strings contain 6 or more 1's?

Answer

\({10 \choose 6} + {10\choose 7} + {10\choose 8} + {10 \choose 9} + {10\choose 10} = 386\) strings. Count the number of strings with each permissible number of 1's separately, then add them up.

7

How many subsets of \(\{0,1,\ldots, 9\}\) have cardinality 6 or more?

Hint:

Break the question into five cases.

8

What is the coefficient of \(x^{12}\) in \((x+2)^{15}\text{?}\)

Answer

To get an \(x^{12}\text{,}\) we must pick 12 of the 15 factors to contribute an \(x\text{,}\) leaving the other 3 to contribute a 2. There are \({15 \choose 12}\) ways to select these 12 factors. So the term containing an \(x^{12}\) will be \({15 \choose 12}x^{12}2^{3}\text{.}\) In other words, the coefficient of \(x^{12}\) is \({15\choose 12}2^3 = 3640\text{.}\)

9

What is the coefficient of \(x^9\) in the expansion of \((x+1)^{14} + x^3(x+2)^{15}\text{?}\)

10

How many shortest lattice paths start at (3,3) and

1. end at (10,10)?
2. end at (10,10) and pass through (5,7)?
3. end at (10,10) and avoid (5,7)?

Answer

1. \({14 \choose 7} = 3432\) paths. The paths all have length 14 (7 steps up and 7 steps right), we just select which 7 of those 14 should be up.
2. \({6 \choose 2}{8\choose 5} = 840\) paths. First travel to (5,7), and then continue on to (10,10).
3. \({14 \choose 7} - {6\choose 2}{8 \choose 5}\) paths. Remove all the paths that you found in part (b).

11

Gridtown USA, besides having excellent donut shoppes, 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 1st and 1st and work on the corner of 12th and 12th. Thus you must travel 22 blocks to get to work as quickly as possible.

1. How many different routes can you take to work, assuming you want to get there as quickly as possible?
2. Now suppose you want to stop and get a donut on the way to work, from your favorite donut shoppe on the corner of 8th st and 10th ave. How many routes to work, via the donut shoppe, can you take (again, ensuring the shortest possible route)?
3. Disaster Strikes Gridtown: there is a pothole on 4th avenue between 5th and 6th street. How many routes to work can you take avoiding that unsightly (and dangerous) stretch of road?
4. How many routes are there both avoiding the pothole and visiting the donut shoppe?

12

Suppose you are ordering a large pizza from D.P. Dough. You want 3 distinct toppings, chosen from their list of 11 vegetarian toppings.

1. How many choices do you have for your pizza?
2. How many choices do you have for your pizza if you refuse to have pineapple as one of your toppings?
3. How many choices do you have for your pizza if you insist on having pineapple as one of your toppings?
4. How do the three questions above relate to each other?

13

Explain why the coefficient of \(x^5y^3\) the same as the coefficient of \(x^3y^5\) in the expansion of \((x+y)^8\text{?}\)

1.3: Combinations and Permutations

1

A pizza parlor offers 10 toppings.

1. How many 3-topping pizzas could they put on their menu? Assume double toppings are not allowed.
2. How many total pizzas are possible, with between zero and ten toppings (but not double toppings) allowed?
3. The pizza parlor will list the 10 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?

Answer

1. \({10 \choose 3} = 120\) pizzas. We must choose (in no particular order) 3 out of the 10 toppings.
2. \(2^{10} = 1024\) pizzas. Say yes or no to each topping.
3. \(P(10,5) = 30240\) ways. Assign each of the 5 spots in the left column to a unique pizza topping.

2

A combination lock consists of a dial with 40 numbers on it. To open the lock, you turn the dial to the right until you reach a first number, then to the left until you get to second number, then to the right again to the third number. The numbers must be distinct. How many different combinations are possible?

Answer

Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \(P(40,3) = 40\cdot 39 \cdot 38\) different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(40^3\)).

3

Using the digits 2 through 8, find the number of different 5-digit numbers such that:

1. Digits can be used more than once.
2. Digits cannot be repeated, but can come in any order.
3. Digits cannot be repeated and must be written in increasing order.
4. Which of the above counting questions is a combination and which is a permutation? Explain why this makes sense.

4

How many triangles are there with vertices from the points shown below? Note, we are not allowing degenerate triangles - ones with all three vertices on the same line, but we do allow non-right triangles. Explain why your answer is correct.

Hint:

You need exactly two points on either the \(x\)- or \(y\)-axis, but don't over-count the right triangles.

5

How many quadrilaterals can you draw using the dots below as vertices (corners)?

Answer

\({7\choose 2}{7\choose 2} = 441\) quadrilaterals. We must pick two of the seven dots from the top row and two of the seven dots on the bottom row. However, it does not make a difference which of the two (on each row) we pick first because once these four dots are selected, there is exactly one quadrilateral that they determine.

6

How many of the quadrilaterals possible in the previous problem are:

1. Squares?
2. Rectangles?
3. Parallelograms?
4. Trapezoids?²Here, as in calculus, a trapezoid is defined as a quadrilateral with at least one pair of parallel sides. In particular, parallelograms are trapezoids.
5. Trapezoids that are not parallelograms?

Answer

1. 5 squares. You need to skip exactly one dot on the top and on the bottom to make the side lengths equal. Once you pick a dot on the top, the other three dots are determined.
2. \({7 \choose 2}\) rectangles. Once you select the two dots on the top, the bottom two are determined.
3. This is tricky since you need to worry about running out of space. One way to count: break into cases by the location of the top left corner. You get \({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) parallelograms.
4. All of them
5. \({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\) All of them, except the parallelograms.

7

An anagram of a word is just a rearrangement of its letters. How many different anagrams of “uncopyrightable” are there? (This happens to be the longest common English word without any repeated letters.)

8

How many anagrams are there of the word “assesses” that start with the letter “a”?

Answer

After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \({7 \choose 2} = 21\) anagrams starting with “a”.

9

How many anagrams are there of “anagram”?

10

On a business retreat, your company of 20 businessmen and businesswomen go golfing.

1. You need to divide up into foursomes (groups of 4 people): a first foursome, a second foursome, and so on. How many ways can you do this?
2. After all your hard work, you realize that in fact, you want each foursome to include one of the five Board members. How many ways can you do this?

Answer

1. \({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\) ways. Pick 4 out of 20 people to be in the first foursome, then 4 of the remaining 16 for the second foursome, and so on (use the multiplicative principle to combine).
2. \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\) ways. First determine the tee time of the 5 board members, then select 3 of the 15 non board members to golf with the first board member, then 3 of the remaining 12 to golf with the second, and so on.

11

How many different seating arrangements are possible for King Arthur and his 9 knights around their round table?

Answer

\(9!\) (there are 10 people seated around the table, but it does not matter where King Arthur sits, only who sits to his left, two seats to his left, and so on).

12

Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 17\text{.}\)

1. How many functions \(f: A \to B\) are there?
2. How many functions \(f: A \to B\) are injective?

Answer

1. \(17^{10}\) functions. There are 17 choices for the image of each element in the domain.
2. \(P(17, 10)\) injective functions. There are 17 choices for image of the first element of the domain, then only 16 choices for the second, and so on.

13

Consider functions \(f: \{1,2,3,4\} \to \{1,2,3,4,5,6\}\text{.}\)

1. How many functions are there total?
2. How many functions are injective?
3. How many of the injective functions are increasing? To be increasing means that if \(a \lt b\) then \(f(a) \lt f(b)\text{,}\) or in other words, the outputs get larger as the inputs get larger.

14

We have seen that the formula for \(P(n,k)\) is \(\dfrac{n!}{(n-k)!}\text{.}\) Your task here is to explain why this is the right formula.

1. Suppose you have 12 chips, each a different color. How many different stacks of 5 chips can you make? Explain your answer and why it is the same as using the formula for \(P(12,5)\text{.}\)
2. Using the scenario of the 12 chips again, what does \(12!\) count? What does \(7!\) count? Explain.
3. Explain why it makes sense to divide \(12!\) by \(7!\) when computing \(P(12,5)\) (in terms of the chips).
4. Does your explanation work for numbers other than 12 and 5? Explain the formula \(P(n,k) = \frac{n!}{(n-k)!}\) using the variables \(n\) and \(k\text{.}\)

1.4: Combinatorial Proofs

1

Prove the identity \({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) using a question about subsets.

Answer

Proof

Question: How many subsets of size \(k\) are there of the set \(\{1,2,\ldots, n\}\text{?}\)

Answer 1: You must choose \(k\) out of \(n\) elements to put in the set, which can be done in \({n \choose k}\) ways.

Answer 2: First count the number of \(k\)-element subsets of \(\{1,2,\ldots, n\}\) which contain the number \(n\text{.}\) We must choose \(k-1\) of the \(n-1\) other element to include in this set. Thus there are \({n-1\choose k-1}\) such subsets. We have not yet counted all the \(k\)-element subsets of \(\{1,2,\ldots, n\}\) though. In fact, we have missed exactly those subsets which do NOT contain \(n\text{.}\) To form one of these subsets, we need to choose \(k\) of the other \(n-1\) elements, so this can be done in \({n-1 \choose k}\) ways. Thus the answer to the question is \({n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

Since the two answers are both answers tot eh same question, they are equal, establishing the identity \({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

\(\square\)

2

Give a combinatorial proof of the identity \(2+2+2 = 3\cdot 2\text{.}\)

Answer

Proof

Question: How many 2-letter words start with a, b, or c and end with either y or z?

Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of \(2+2+2\text{.}\)

Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \(3 \cdot 2\text{.}\)

Since the two answers are both answers to the same question, they are equal. Thus \(2 + 2 + 2 = 3\cdot 2\text{.}\)

\(\square\)

3

Give a combinatorial proof for the identity \(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)

Answer

Proof

Question: How many subsets of \(A = {1,2,3, \ldots, n+1}\) contain exactly two elements?

Answer 1: We must choose 2 elements from \(n+1\) choices, so there are \({n+1 \choose 2}\) subsets.

Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can't be 1, since we need at least one element smaller than it.

Larger element is 2: there is 1 choice for the smaller element.

Larger element is 3: there are 2 choices for the smaller element.

Larger element is 4: there are 3 choices for the smaller element.

And so on. When the larger element is \(n+1\text{,}\) there are \(n\) choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is \(1 + 2 + 3 + \cdots + n\text{.}\)

Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore,

\begin{equation*} 1 + 2 + 3 + \cdots + n = {n+1 \choose 2} \end{equation*}

\(\square\)

4

A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?

1. What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
2. What if she first selects her maid of honor, and then 5 other bridemaids?
3. Explain why \(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)

Answer

1. She has \({15 \choose 6}\) ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \({15 \choose 6}6\) choices.
2. She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \({14 \choose 5}\) ways. Thus she has \(15 {14 \choose 5}\) choices.
3. We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity and the second way gives the right-hand side of the identity. Therefore the identity holds.

5

Give a combinatorial proof of the identity \({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)

Answer

Proof

Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \(k\) of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?

Answer 1: First select 2 of the \(n\) balls to put in the jar. Then select \(k-2\) of the remaining \(n-2\) balls to put in the box. The first task can be completed in \({n \choose 2}\) different ways, the second task in \({n-2 \choose k-2}\) ways. Thus there are \({n \choose 2}{n-2 \choose k-2}\) ways to select the balls.

Answer 2: First select \(k\) balls from the \(n\) in the container. Then pick 2 of the \(k\) balls you picked to put in the jar, placing the remaining \(k-2\) in the box. The first task can be completed in \({n \choose k}\) ways, the second task in \({k \choose 2}\) ways. Thus there are \({n \choose k}{k \choose 2}\) ways to select the balls.

Since both answers count the same thing, they must be equal and the identity is established.

\(\square\)

6

Consider the bit strings in \(\B^6_2\) (bit strings of length 6 and weight 2).

1. How many of those bit strings start with 1?
2. How many of those bit strings start with 01?
3. How many of those bit strings start with 001?
4. Are there any other strings we have not counted yet? Which ones, and how many are there?
5. How many bit strings are there total in \(\B^6_2\text{?}\)
6. What binomial identity have you just given a combinatorial proof for?

Answer

1. After the 1, we need to find a 5-bit string with one 1. There are \({5 \choose 1}\) ways to do this.
2. \({4 \choose 1}\) strings (we need to pick 1 of the remaining 4 slots to be the second 1).
3. \({3 \choose 1}\) strings.
4. Yes. We still need strings starting with 0001 (there are \({2 \choose 1}\) of these) and strings starting 00001 (there is only \({1 \choose 1} = 1\) of these).
5. \({6 \choose 2}\) strings
6. An example of the Hockey Stick Theorem: \begin{equation*} {1 \choose 1} + {2 \choose 1} + {3 \choose 1} + {4 \choose 1} + {5 \choose 1} = {6 \choose 2} \end{equation*}

7

Let's count ternary digit strings, that is, strings in which each digit can be 0, 1, or 2.

1. How many ternary digit strings contain exactly \(n\) digits?
2. How many ternary digit strings contain exactly \(n\) digits and \(n\) 2's.
3. How many ternary digit strings contain exactly \(n\) digits and \(n-1\) 2's. (Hint: where can you put the non-2 digit, and then what could it be?)
4. How many ternary digit strings contain exactly \(n\) digits and \(n-2\) 2's. (Hint: see previous hint)
5. How many ternary digit strings contain exactly \(n\) digits and \(n-k\) 2's.
6. How many ternary digit strings contain exactly \(n\) digits and no 2's. (Hint: what kind of a string is this?)
7. Use the above parts to give a combinatorial proof for the identity \begin{equation*} {n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \end{equation*}

Answer

1. \(3^n\) strings, since there are 3 choices for each of the \(n\) digits.
2. \(1\) string, since all the digits need to be 2's. However, we might write this as \({n \choose 0}\) strings.
3. There are \({n \choose 1}\) places to put the non-2 digit. That digit can be either a 0 or a 1, so there are \(2{n \choose 1}\) such strings.
4. We must choose two slots to fill with 0's or 1's. There are \({n \choose 2}\) ways to do that. Once the slots are picked, we have two choices for the first slot (0 or 1) and two choices for the second slot (0 or 1). So there are a total of \(2^2{n \choose 2}\) such strings.
5. There are \({n \choose k}\) ways to pick which slots don't have the 2's. Then those slots can be filled in \(2^k\) ways (0 or 1 for each slot). So there are \(2^k{n \choose k}\) such strings.
6. These strings contain just 0's and 1's, so they are bit strings. There are \(2^n\) bit strings. But keeping with the pattern above, we might write this as \(2^n {n \choose n}\) strings.
7. We answer the question of how many length \(n\) ternary digit strings there are in two ways. First, each digit can be one of three choices, so the total number of strings is \(3^n\text{.}\) On the other hand, we could break the question down into cases by how many of the digits are 2's. If they are all 2's, then there are \({n \choose 0}\) strings. If all but one is a 2, then there are \(2{n \choose 1}\) strings. If all but 2 of the digits are 2's, then there are \(2^2{n \choose 2}\) strings. We choose 2 of the \(n\) digits to be non-2, and then there are 2 choices for each of those digits. And so on for every possible number of 2's in the string. Therefore \({n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \)

8

How many ways are there to rearrange the letters in the word “rearrange”? Answer this question in at least two different ways to establish a binomial identity.

Answer

The word contains 9 letters: 3 “r”s, 2 “a”s and 2 “e”s, along with an “n” and a “g”. We could first select the positions for the “r”s in \({9 \choose 3}\) ways, then the “a”s in \({6 \choose 2}\) ways, the “e”s in \({4 \choose 2}\) ways and then select one of the remaining two spots to put the “n” (placing the “g” in the last spot). This gives the answer

\begin{equation*} {9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1}. \end{equation*}

Alternatively, we could select the positions of the letters in the opposite order, which would give an answer

\begin{equation*} {9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}. \end{equation*}

(where the 3 “r”s go in the remaining 3 spots). These two expressions are equal:

9

Give a combinatorial proof for the identity \(P(n,k) = {n \choose k}k!\)

Answer

Proof

Question: How many \(k\)-letter words can you make using \(n\) different letters without repeating any letter?

Answer 1: There are \(n\) choices for the first letter, \(n-1\) choices for the second letter, \(n-2\) choices for the third letter, and so on until \(n - (k-1)\) choices for the \(k\)th letter (since \(k-1\) letters have already been assigned at that point). The product of these numbers can be written \(\frac{n!}{(n-k)!}\) which is \(P(n,k)\text{.}\) Therefore there are \(P(n,k)\) words.

Answer 2: First pick \(k\) letters to be in the word from the \(n\) choices. This can be done in \({n \choose k}\) ways. Now arrange those letters into a word. There are \(k\) choices for the first letter, \(k-1\) choices for the second, and so on, for a total of \(k!\) arrangements of the \(k\) letters. Thus the total number of words is \({n \choose k}k!\text{.}\)

Since the two answers are correct answers to the same question, we have established that \(P(n,k) = {n \choose k}k!\text{.}\)

\(\square\)

10

Establish the identity below using a combinatorial proof.

\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation*}

Answer

Proof

Question: How many 5-element subsets are there of the set \(\{1,2,\ldots, n+3\}\text{.}\)

Answer 1: We choose 5 out of the \(n+3\) elements, so \({n+3 \choose 5}\) subsets.

Answer 2: Break this up into cases by what the “middle” (third smallest) element of the 5 element subset is. The smallest this could be is a 3. In that case, we have \({2 \choose 2}\) choices for the numbers below it, and \({n \choose 2}\) choices for the numbers above it. Alternatively, the middle number could be a 4. In this case there are \({3 \choose 2}\) choices for the bottom two numbers and \({n-1 \choose 2}\) choices for the top two numbers. If the middle number is 5, then there are \({4 \choose 2}\) choices for the bottom two numbers and \({n-2 \choose 2}\) choices for the top two numbers. An so on, all the way up to the largest the middle number could be, which is \(n+1\text{.}\) In that case there are \({n \choose 2}\) choices for the bottom two numbers and \({2 \choose 2}\) choices for the top number. Thus the number of 5 element subsets is

\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2}. \end{equation*}

Since the two answers correctly answer the same question, we have \begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation*}

1.5: Stars and Bars

1

A multiset is a collection of objects, just like a set, but can contain an object more than once (the order of the elements still doesn't matter). For example, \(\{1,1, 2, 5, 5, 7\}\) is a multiset of size 6.

1. How many sets of size 5 can be made using the 10 numeric digits 0 through 9?
2. How many multisets of size 5 can be made using the 10 numeric digits 0 through 9?

Answer

1. \({10\choose 5}\) sets. We must select 5 of the 10 digits to put in the set.
2. Use stars and bars: each star represents one of the 5 elements of the set, each bar represents a switch between digits. So there are 5 stars and 9 bars, giving us \({14 \choose 9}\) sets.

2

Each of the counting problems below can be solved with stars and bars. For each, say what outcome the diagram

\begin{equation*} ***|*||**| \end{equation*}

represents, if there are the correct number of stars and bars for the problem. Otherwise, say why the diagram does not represent any outcome, and what a correct diagram would look like.

1. How many ways are there to select a handful of 6 jellybeans from a jar that contains 5 different flavors?
2. How many ways can you distribute 5 identical lollipops to 6 kids?
3. How many 6-letter words can you make using the 5 vowels?
4. How many solutions are there to the equation \(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)

Answer

1. You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry and 0 bubblegum.
2. This is backwards. We don't want the stars to represent the kids because the kids are not identical, but the stars are. Instead we should use 5 stars (for the lollipops) and use 5 bars to switch between the 6 kids. For example, \begin{equation*} **||***||| \end{equation*} would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none.
3. This is the word AAAEOO.
4. This doesn't represent a solution. Each star should represent one of the 6 units that add up to 6, and the bars should switch between the different variables. We have one too many bars. An example of a correct diagram would be \begin{equation*} *|**||***, \end{equation*} representing that \(x_1 = 1\text{,}\) \(x_2 = 2\text{,}\) \(x_3 = 0\text{,}\) and \(x_4 = 3\text{.}\)

3

After gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins.

1. How many ways can you do this if there are no restrictions?
2. How many ways can you do this if each bin must contain at least one dodgeball?

Answer

1. \({18 \choose 4}\) ways. Each outcome can be represented by a sequence of 14 stars and 4 bars.
2. \({13 \choose 4}\) ways. First put one ball in each bin. This leaves 9 stars and 4 bars.

4

How many integer solutions are there to the equation \(x + y + z = 8\) for which

1. \(x\text{,}\) \(y\text{,}\) and \(z\) are all positive?
2. \(x\text{,}\) \(y\text{,}\) and \(z\) are all non-negative?
3. \(x\text{,}\) \(y\text{,}\) and \(z\) are all greater than \(-3\text{.}\)

Answer

1. \({7 \choose 2}\) solutions. After each variable gets 1 star for free, we are left with 5 stars and 2 bars.
2. \({10 \choose 2}\) solutions. We have 8 stars and 2 bars.
3. \({19 \choose 2}\) solutions. This problem is equivalent to finding the number of solutions to \(x' + y' + z' = 17\) where \(x'\text{,}\) \(y'\) and \(z'\) are non-negative. (In fact, we really just do a substitution. Let \(x = x'- 3\text{,}\) \(y = y' - 3\) and \(z = z' - 3\)).

5

Using the digits 2 through 8, find the number of different 5-digit numbers such that:

1. Digits cannot be repeated and must be written in increasing order. For example, 23678 is okay, but 32678 is not.
2. Digits can be repeated and must be written in non-decreasing order. For example, 24448 is okay, but 24484 is not.

Answer

1. There are \({7 \choose 5}\) numbers. We simply choose five of the seven digits and once chosen put them in increasing order.
2. This requires stars and bars. Use a star to represent each of the 5 digits in the number, and use their position relative to the bars to say what numeral fills that spot. So we will have 5 stars and 6 bars, giving \({11 \choose 6}\) numbers.

6

When playing Yahtzee, you roll five regular 6-sided dice. How many different outcomes are possible from a single roll? The order of the dice does not matter.

7

Your friend tells you she has 7 coins in her hand (just pennies, nickels, dimes and quarters). If you guess how many of each kind of coin she has, she will give them to you. If you guess randomly, what is the probability that you will be correct?

8

How many integer solutions to \(x_1 + x_2 + x_3 + x_4 = 25\) are there for which \(x_1 \ge 1\text{,}\) \(x_2 \ge 2\text{,}\) \(x_3 \ge 3\) and \(x_4 \ge 4\text{?}\)

9

Solve the three counting problems below. Then say why it makes sense that they all have the same answer. That is, say how you can interpret them as each other.

1. How many ways are there to distribute 8 cookies to 3 kids?
2. How many solutions in non-negative integers are there to \(x+y+z = 8\text{?}\)
3. How many different packs of 8 crayons can you make using crayons that come in red, blue and yellow?

10

Consider functions \(f:\{1,2,3,4,5\} \to \{0,1,2,\ldots,9\}\text{.}\)

1. How many of these functions are strictly increasing? Explain. (A function is strictly increasing provided if \(a \lt b\text{,}\) then \(f(a) \lt f(b)\text{.}\))
2. How many of the functions are non-decreasing? Explain. (A function is non-decreasing provided if \(a \lt b\text{,}\) then \(f(a) \le f(b)\text{.}\))

11

Conic, your favorite math themed fast food drive-in offers 20 flavors which can be added to your soda. You have enough money to buy a large soda with 4 added flavors. How many different soda concoctions can you order if:

1. You refuse to use any of the flavors more than once?
2. You refuse repeats but care about the order the flavors are added?
3. You allow yourself multiple shots of the same flavor?
4. You allow yourself multiple shots, and care about the order the flavors are added?

Answer

1. \({20 \choose 4}\) sodas (order does not matter and repeats are not allowed).
2. \(P(20, 4) = 20\cdot 19\cdot 18 \cdot 17\) sodas (order matters and repeats are not allowed).
3. \({23 \choose 19}\) sodas (order does not matter and repeats are allowed; 4 stars and 19 bars).
4. \(20^4\) sodas (order matters and repeats are allowed; 20 choices 4 times).

1.6: Advanced Counting Using PIE

1

The dollar menu at your favorite tax-free fast food restaurant has 7 items. You have $10 to spend. How many different meals can you buy if you spend all your money and:

1. Purchase at least one of each item.
2. Possibly skip some items.
3. Don't get more than 2 of any particular item.

Answer a

\(9 \choose 6\) meals.

Answer b

\(16 \choose 6\) meals.

Answer c

\({16 \choose 6} - \left[{7 \choose 1}{13 \choose 6} - {7 \choose 2}{10 \choose 6} + {7 \choose 3}{7 \choose 6}\right]\) me als. Use PIE to subtract all the meals in which you get 3 or more of a particular item.

2

After a late night of math studying, you and your friends decide to go to your favorite tax-free fast food Mexican restaurant, Burrito Chime. You decide to order off of the dollar menu, which has 7 items. Your group has $16 to spend (and will spend all of it).

1. How many different orders are possible? Explain. (The order in which the order is placed does not matter - just which and how many of each item that is ordered.)
2. How many different orders are possible if you want to get at least one of each item? Explain.
3. How many different orders are possible if you don't get more than 4 of any one item? Explain.

3

After another gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins. This time, no bin can hold more than 6 balls. How many ways can you clean up?

Solution

\({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\) Subtract all the distributions for which one or more bins contain 7 or more balls.

4

Consider the equation \(x_1 + x_2 + x_3 + x_4 = 15\text{.}\) How many solutions are there with \(2 \le x_i \le 5\) for all \(i \in \{1,2,3,4\}\text{?}\)

Solution

The easiest way to solve this is to instead count the solutions to \(y_1 + y_2 + y_3 + y_4 = 7\) with \(0 \le y_i \le 3\text{.}\) By taking \(x_i = y_i+2\text{,}\) each solution to this new equation corresponds to exactly one solution to the original equation.

Now all the ways to distribute the 7 units to the four \(y_i\) variables can be found using stars and bars, specifically 7 stars and 3 bars, so \({10 \choose 3}\) ways. But this includes the ways that one or more \(y_i\) variables can be assigned more than 3 units. So subtract, using PIE. We get

\begin{equation*} {10 \choose 3} - {4\choose 1} {6 \choose 3}. \end{equation*}

The \({4 \choose 1}\) counts the number of ways to pick one variable to be over-assigned, the \({6 \choose 3}\) is the number of ways to assign the remaining 3 units to the 4 variables. Note that this is the final answer because it is not possible to have two variables both get 4 units.

5

Suppose you planned on giving 7 gold stars to some of the 13 star students in your class. Each student can receive at most one star. How many ways can you do this? Use PIE, and also an easier method, and compare your results.

6

Based on the previous question, give a combinatorial proof for the identity:

\begin{equation*} {n \choose k} = {n+k-1 \choose k} - \sum_{j=1}^n (-1)^{j+1}{n \choose j}{n+k-(2j+1) \choose k}. \end{equation*}

7

Illustrate how the counting of derangements works by writing all permutations of \(\{1,2,3,4\}\) and the crossing out those which are not derangements. Keep track of the permutations you cross out more than once, using PIE.

Solution

The 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

8

How many permutations of \(\{1,2,3,4,5\}\) leave exactly 1 element fixed?

Solution

First pick one of the five elements to be fixed. For each such choice, derange the remaining four, using the standard advanced PIE formula. We get \({5 \choose 1}\left( 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right] \right)\) permutations.

9

Ten ladies of a certain age drop off their red hats at the hat check of a museum. As they are leaving, the hat check attendant gives the hats back randomly. In how many ways can exactly six of the ladies receive their own hat (and the other four not)? Explain.

10

The Grinch sneaks into a room with 6 Christmas presents to 6 different people. He proceeds to switch the name-labels on the presents. How many ways could he do this if:

1. No present is allowed to end up with its original label? Explain what each term in your answer represents.
2. Exactly 2 presents keep their original labels? Explain.
3. Exactly 5 presents keep their original labels? Explain.

11

Consider functions \(f: \{1,2,3,4\} \to \{a,b,c,d,e,f\}\text{.}\) How many functions have the property that \(f(1) \ne a\) or \(f(2) \ne b\text{,}\) or both?

Solution

There are \(5 \cdot 6^3\) functions for which \(f(1) \ne a\) and another \(5 \cdot 6^3\) functions for which \(f(2) \ne b\text{.}\) There are \(5^2 \cdot 6^2\) functions for which both \(f(1) \ne a\) and \(f(2) \ne b\text{.}\) So the total number of functions for which \(f(1) \ne a\) or \(f(2) \ne b\) or both is

\begin{equation*} 5 \cdot 6^3 + 5 \cdot 6^3 - 5^2 \cdot 6^2 = 1260. \end{equation*}

12

Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 5\text{.}\) How many functions \(f: A \to B\) are surjective?

Solution

\(5^{10} - \left[{5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right]\) functions. The \(5^{10}\) is all the functions from \(A\) to \(B\text{.}\) We subtract those that aren't surjective. Pick one of the five elements in \(B\) to not have in the range (in \({5 \choose 1}\) ways) and count all those functions (\(4^{10}\)). But this overcounts the functions where two elements from \(B\) are excluded from the range, so subtract those. And so on, using PIE.

13

Let \(A = \{1,2,3,4,5\}\text{.}\) How many injective functions \(f:A \to A\) have the property that for each \(x \in A\text{,}\) \(f(x) \ne x\text{?}\)

14

Let \(d_n\) be the number of derangements of \(n\) objects. For example, using the techniques of this section, we find

\begin{equation*} d_3 = 3!-\left({3 \choose 1}2! - {3 \choose 2}1! + {3 \choose 3}0! \right) \end{equation*}

We can use the formula for \({n \choose k}\) to write this all in terms of factorials. After simplifying, for \(d_3\) we would get

\begin{equation*} d_3 = 3!\left(1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} \right) \end{equation*}

Generalize this to find a nicer formula for \(d_n\text{.}\) Bonus: For large \(n\text{,}\) approximately what fraction of all permutations are derangements? Use your knowledge of Taylor series from calculus.