Skip to main content
\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section 1.2 Basic Counting Principles

Problem 1

Five schools are going to send their baseball teams to a tournament, in which each team must play each other team exactly once. How many games are required?

Hint

Answer the questions in Problem 2 for the case of five schools.

Problem 2

Now some number \(n\) of schools are going to send their baseball teams to a tournament, and each team must play each other team exactly once. Let us think of the teams as numbered 1 through \(n\text{.}\)

(a)

How many games does team 1 have to play in?

(b)

How many games, other than the one with team 1, does team two have to play in?

(c)

How many games, other than those with the first \(i-1\) teams, does team \(i\) have to play in?

(d)

In terms of your answers to the previous parts of this problem, what is the total number of games that must be played?

Problem 3

One of the schools sending its team to the tournament has to send its players from some distance, and so it is making sandwiches for team members to eat along the way. There are three choices for the kind of bread and five choices for the kind of filling. How many different kinds of sandwiches are available?

Hint

For each kind of bread, how many sandwiches are possible?

Problem 4

An ordered pair \((a,b)\) consists of two things we call \(a\) and \(b\text{.}\) We say \(a\) is the first member of the pair and \(b\) is the second member of the pair. If \(M\) is an \(m\) element set and \(N\) is an \(n\)-element set, how many ordered pairs are there whose first member is in \(M\) and whose second member is in \(N\text{?}\) Does this problem have anything to do with any of the previous problems?

Problem 5

Since a sandwich by itself is pretty boring, students from the school in Problem 3 are offered a choice of a drink (from among five different kinds), a sandwich, and a fruit (from among four different kinds). In how many ways may a student make a choice of the three items now?

Problem 6

The coach of the team in Problem 3 knows of an ice cream parlor along the way where she plans to stop to buy each team member a triple decker cone. There are 12 different flavors of ice cream, and triple decker cones are made in homemade waffle cones. Having chocolate ice cream as the bottom scoop is different from having chocolate ice cream as the top scoop. How many possible ice cream cones are going to be available to the team members? How many cones with three different kinds of ice cream will be available?

Hint

Try to solve the problem first with a two-scoop cone. (Look for an earlier problem that is analogous.) Then, for each two scoop cone, in how many ways can you put on a top scoop?

Problem 7

The idea of a function is ubiquitous in mathematics. A function \(f\) from a set \(S\) to a set \(T\) is a relationship between the two sets that associates exactly one member \(f(x)\) of \(T\) with each element \(x\) in \(S\text{.}\) We will come back to the ideas of functions and relationships in more detail and from different points of view from time to time. However, the quick review above should probably let you answer these questions. If you have difficulty with them, it would be a good idea to go now to Appendix A and work through Section A.1 which covers this definition in more detail. You might also want to study Section A.1.3 to learn to visualize the properties of functions. We will take up the topic of this section later in this chapter as well, but in less detail than is in the appendix.

(a)

Using \(f\text{,}\) \(g\text{,}\) 
, to stand for the various functions, write down all the different functions you can from the set \(\{1,2\}\) to the set \(\{a,b\}\text{.}\) For example, you might start with \(f(1)=a\text{,}\) \(f(2)=b\text{.}\) How many functions are there from the set \(\{1,2\}\) to the set \(\{a,b\}\text{?}\)

Hint

Ask yourself “how many choices do we have for \(f(1)\text{?}\)” Then ask how many choices we have for \(f(2)\text{.}\)

(b)

How many functions are there from the three element set \(\{1,2,3\}\) to the two element set \(\{a,b\}\text{?}\)

Hint

It may not be practical to write down rules for all the functions for this problem. But you could ask yourself how many choices we have for \(f(1)\text{,}\) how many we have for \(f(2)\) and how many we have for \(f(3)\text{.}\)

(c)

How many functions are there from the two element set \(\{a,b\}\) to the three element set \(\{1,2,3\}\text{?}\)

Hint

If you are choosing a function \(f\text{,}\) how many choices do you have for \(f(a)\text{?}\) Then how many choices do you have for \(f(b)\text{?}\)

(d)

How many functions are there from a three element set to a 12 element set?

(e)

The function \(f\) is called one-to-one or an injection if whenever \(x\) is different from \(y\text{,}\) \(f(x)\) is different from \(f(y)\text{.}\) How many one-to-one functions are there from a three element set to a 12 element set?

(f)

Explain the relationship between this problem and Problem 6.

Problem 8

A group of hungry team members in Problem 6 notices it would be cheaper to buy three pints of ice cream for them to split than to buy a triple decker cone for each of them, and that way they would get more ice cream. They ask their coach if they can buy three pints of ice cream.

(a)

In how many ways can they choose three pints of different flavors out of the 12 flavors?

Hint

You know how to figure out in how many ways they could make a list of three flavors out of the twelve. But each set of three flavors can be listed in a number of different ways. Try to figure out in how many ways a set of three flavors can be listed, and then try to see how this helps you.

(b)

In how many ways may they choose three pints if the flavors don't have to be different?

Hint

Try to break the problem up into cases you can solve by previous methods; then figure out how to get the answer to the problem by using these answers for the cases.

Problem 9

Two sets are said to be disjoint if they have no elements in common. For example, \(\{1,3,12\}\) and \(\{6, 4, 8, 2\}\) are disjoint, but \(\{1,3,12\}\) and \(\{3,5,7\}\) are not. Three or more sets are said to be mutually disjoint if no two of them have any elements in common. What can you say about the size of the union of a finite number of finite (mutually) disjoint sets? Does this have anything to do with any of the previous problems?

Problem 10

Disjoint subsets are defined in Problem 9. What can you say about the size of the union of \(m\) (mutually) disjoint sets, each of size \(n\text{?}\) Does this have anything to do with any of the previous problems?

Subsection 1.2.1 The sum and product principles

These problems contain among them the kernels of many of the fundamental ideas of combinatorics. For example, with luck, you just stated the sum principle (illustrated in Figure 1.2.1), and product principle (illustrated in Figure 1.2.2) in Problems 9 and Problem 10. These two counting principles are the basis on which we will develop many other counting principles.

Figure 1.2.1 The union of these two disjoint sets has size 17.
Figure 1.2.2 The union of four disjoint sets of size five.

You may have noticed some standard mathematical words and phrases such as set, ordered pair, function and so on creeping into the problems. One of our goals in these notes is to show how most counting problems can be recognized as counting all or some of the elements of a set of standard mathematical objects. For example Problem 4 is meant to suggest that the question we asked in Problem 3 was really a problem of counting all the ordered pairs consisting of a bread choice and a filling choice. We use \(A\times B\) to stand for the set of all ordered pairs whose first element is in \(A\) and whose second element is in \(B\) and we call \(A\times B\) the Cartesian product of \(A\) and \(B\text{,}\) so you can think of Problem 4 as asking you for the size of the Cartesian product of \(M\) and \(N\text{,}\) that is, asking you to count the number of elements of this Cartesian product.

When a set \(S\) is a union of disjoint sets \(B_1, B_2, \ldots, B_m\) we say that the sets \(B_1, B_2, \ldots, B_m\) are a partition of the set \(S\text{.}\) Thus a partition of \(S\) is a (special kind of) set of sets. So that we don't find ourselves getting confused between the set \(S\) and the sets \(B_i\) into which we have divided it, we often call the sets \(B_1, B_2, \ldots, B_m\) the blocks of the partition. In this language, the sum principle says that

if we have a partition of a set \(S\text{,}\) then the size of \(S\) is the sum of the sizes of the blocks of the partition.

The product principle says that

if we have a partition of a set \(S\) into \(m\) blocks, each of size \(n\text{,}\) then \(S\) has size \(mn\text{.}\)

You'll notice that in our formal statement of the sum and product pinciple we talked about a partition of a finite set. We could modify our language a bit to cover infinite sizes, but whenever we talk about sizes of sets in what follows, we will be working with finite sets. So as to avoid possible complications in the future, let us agree that when we refer to the size of a set, we are implicitly assuming the set is finite. There is another version of the product principle that applies directly in problems like Problem 5 and Problem 6, where we were not just taking a union of \(m\) disjoint sets of size \(n\text{,}\) but rather \(m\) disjoint sets of size \(n\text{,}\) each of which was a union of \(m'\) disjoint sets of size \(n'\text{.}\) This is an inconvenient way to have to think about a counting problem, so we may rephrase the product principle in terms of a sequence of decisions:

Problem 11

If we make a sequence of \(m\) choices for which

  • there are \(k_1\) possible first choices, and
  • for each way of making the first \(i-1\) choices, there are \(k_i\) ways to make the \(i\)th choice,

then in how many ways may we make our sequence of choices? (You need not prove your answer correct at this time.)

The counting principle you gave in Problem 11 is called the general product principle. We will outline a proof of the general product pinciple from the original product principle in Problem 80. Until then, let us simply accept it as another counting principle. For now, notice how much easier it makes it to explain why we multiplied the things we did in Problem 5 and Problem 6.

Problem 12

A tennis club has \(2n\) members. We want to pair up the members by twos for singles matches.

(a)

In how many ways may we pair up all the members of the club? (Hint: consider the cases of 2, 4, and 6 members.)

Hint

Suppose you have a list in alphabetical order of names of the members of the club. In how many ways can you pair up the first person on the list? In how many ways can you pair up the next person who isn't already paired up?

(b)

Suppose that in addition to specifying who plays whom, for each pairing we say who serves first. Now in how many ways may we specify our pairs?

Problem 13

Let us now return to Problem 7 and justify—or perhaps finish—our answer to the question about the number of functions from a three-element set to a 12-element set.

(a)

How can you justify your answer in Problem 7 to the question “How many functions are there from a three element set (say \([3]=\{1,2,3\}\)) to a twelve element set (say [12])?”

(b)

Based on the examples you've seen so far, make a conjecture about how many functions there are from the set

\begin{equation*} [m] = \{1,2,3,\dots,m\} \end{equation*}

to \([n]=\{1,2,3,\dots,n\}\) and prove it.

(c)

A common notation for the set of all functions from a set \(M\) to a set \(N\) is \(N^M\text{.}\) Why is this a good notation?

Problem 14

Now suppose we are thinking about a set \(S\) of functions \(f\) from \([m]\) to some set \(X\text{.}\) (For example, in Problem 6 we were thinking of the set of functions from the three possible places for scoops in an ice-cream cone to \(12\) flavors of ice cream.) Suppose there are \(k_1\) choices for \(f(1)\text{.}\) (In Problem 6, \(k_1\) was \(12\text{,}\) because there were \(12\) ways to choose the first scoop.) Suppose that for each choice of \(f(1)\) there are \(k_2\) choices for \(f(2)\text{.}\) (For example, in Problem 6 \(k_2\) was \(12\) if the second flavor could be the same as the first, but \(k_2\) was \(11\) if the flavors had to be different.) In general, suppose that for each choice of \(f(1)\text{,}\) \(f(2)\text{,}\) 
 \(f(i-1)\text{,}\) there are \(k_i\) choices for \(f(i)\text{.}\) (For example, in Problem 6, if the flavors have to be different, then for each choice of \(f(1)\) and \(f(2)\text{,}\) there are \(10\) choices for \(f(3)\text{.}\))

What we have assumed so far about the functions in \(S\) may be summarized as

  • There are \(k_1\) choices for \(f(1)\text{.}\)
  • For each choice of \(f(1)\text{,}\) \(f(2)\text{,}\) 
, \(f(i-1)\text{,}\) there are \(k_i\) choices for \(f(i)\text{.}\)

How many functions are in the set \(S\text{?}\) Is there any practical difference between the result of this problem and the general product principle?

The point of Problem 14 is that the general product principle can be stated informally, as we did originally, or as a statement about counting sets of standard concrete mathematical objects, namely functions.

Problem 15

A roller coaster car has \(n\) rows of seats, each of which has room for two people. If \(n\) men and \(n\) women get into the car with a man and a woman in each row, in how many ways may they choose their seats?

Hint

In how many ways may you assign the men to their rows? The women? Once a woman and a man have a row to share, in how many ways may they choose their seats?

Problem 16

How does the general product principle apply to Problem 6?

Problem 17

In how many ways can we pass out \(k\) distinct pieces of fruit to \(n\) children (with no restriction on how many pieces of fruit a child may get)?

Problem 18

How many subsets does a set \(S\) with \(n\) elements have?

Hint

Try applying the product principle in the case \(n = 2\) and \(n = 3\text{.}\) How might you apply it in general?

Problem 19

Assuming \(k\le n\text{,}\) in how many ways can we pass out \(k\) distinct pieces of fruit to \(n\) children if each child may get at most one? What is the number if \(k>n\text{?}\) Assume for both questions that we pass out all the fruit.

Hint 1

Ask yourself if either the sum principle or product principle applies.

Hint 2

Remember that zero is a number.

Problem 20

Another name for a list, in a specific order, of \(k\) distinct things chosen from a set \(S\) is a \(k\)-element permutation of \(S\text{.}\) We can also think of a \(k\)-element permutation of \(S\) as a one-to-one function (or, in other words, injection) from \([k]=\{1,2,\ldots, k\}\) to \(S\text{.}\) How many \(k\)-element permutations does an \(n\)-element set have? (For this problem it is natural to assume \(k\le n\text{.}\) However the question makes sense even if \(k>n\text{.}\) What is the number of \(k\)-element permutations of an \(n\)-element set if \(k>n\text{?}\)

Hint

Do you see an analogy between this problem and any of the previous problems?

There are a number of different notations for the number of \(k\)-element permutations of an \(n\)-element set. The one we shall use was introduced by Don Knuth; namely \(n^{\underline{k}}\text{,}\) read “\(n\) to the \(k\) falling” or “\(n\) to the \(k\) down”. In Problem 20 you may have shown that

\begin{equation} n^{\underline{k}} =n(n-1)\cdots (n-k+1)= \prod_{i=1}^k( n-i+1).\label{productnotation}\tag{1.1} \end{equation}

It is standard to call \(n^{\underline{k}}\) the \(k\)-th falling factorial power of \(n\), which explains why we use exponential notation. Of course we call it a factorial power since \(n^{\underline{n}} = n(n-1)\cdots 1\) which we call \(n\)-factorial and denote by \(n!\text{.}\) If you are unfamiliar with the \(\Pi\) notation, or product notation we introduced for products in Equation (1.1), it works just like the \(\Sigma\) notation works for summations.

Problem 21

Express \(n^{\underline{k}}\) as a quotient of factorials.

Problem 22

How should we define \(n^{\underline{0}}\text{?}\)

Subsection 1.2.2 Functions and directed graphs

As another example how standard mathematical language relates to counting problems, Problem 7 explicitly asked you to relate the idea of counting functions to the question of Problem 6. You have probably learned in algebra or calculus how to draw graphs in the Cartesian plane of functions from a set of numbers to a set of numbers. You may recall how we can determine whether a graph is a graph of a function by examining whether each vertical straight line crosses the graph at most one time. You might also recall how we can determine whether such a function is one-to-one by examining whether each horizontal straight line crosses the graph at most one time. The functions we deal with will often involve objects which are not numbers, and will often be functions from one finite set to another. Thus graphs in the cartesian plane will often not be available to us for visualizing functions.

However, there is another kind of graph called a directed graph or digraph that is especially useful when dealing with functions between finite sets. We take up this topic in more detail in Appendix A, particularly Subsection A.1.2 and Subsection A.1.3. In Figure 1.2.3 we show several examples of digraphs of functions.

Figure 1.2.3 What is a digraph of a function?

If we have a function \(f\) from a set \(S\) to a set \(T\text{,}\) we draw a line of dots or circles, called vertices to represent the elements of \(S\) and another (usually parallel) line of circles or dots to represent the elements of \(T\text{.}\) We then draw an arrow from the circle for \(x\) to the circle for \(y\) if \(f(x) = y\text{.}\) Sometimes, as in part (e) of the figure, if we have a function from a set \(S\) to itself, we draw only one set of vertices representing the elements of \(S\text{,}\) in which case we can have arrows both entering and leaving a given vertex. As you see, the digraph can be more enlightening in this case if we experiment with the function to find a nice placement of the vertices rather than putting them in a row.

Notice that there is a simple test for whether a digraph whose vertices represent the elements of the sets \(S\) and \(T\) is the digraph of a function from \(S\) to \(T\text{.}\) There must be one and only one arrow leaving each vertex of the digraph representing an element of \(S\text{.}\) The fact that there is one arrow means that \(f(x)\) is defined for each \(x\) in \(S\text{.}\) The fact that there is only one arrow means that each \(x\) in \(S\) is related to exactly one element of \(T\text{.}\) (Note that these remarks hold as well if we have a function from \(S\) to \(S\) and draw only one set of vertices representing the elements of \(S\text{.}\)) For further discussion of functions and digraphs see Sections A.1.1 and Subsection A.1.2 of {Appendix A}.

Problem 23

Draw the digraph of the function from the set \(\{\)Alice, Bob, Dawn, Bill\(\}\) to the set \(\{\)A, B, C, D, E\(\}\) given by

\begin{equation*} f(X) = \text{ the first letter of the name }X . \end{equation*}
Problem 24

A function \(f:S\rightarrow T\) is called an onto function or surjection if each element of \(T\) is \(f(x)\) for some \(x\in S\text{.}\) Choose a set \(S\) and a set \(T\) so that you can draw the digraph of a function from \(S\) to \(T\) that is one-to-one but not onto, and draw the digraph of such a function.

Problem 25

Choose a set \(S\) and a set \(T\) so that you can draw the digraph of a function from \(S\) to \(T\) that is onto but not one-to-one, and draw the digraph of such a function.

Problem 26

Digraphs of functions help us visualize the ideas of one-to-one functions and onto functions.

(a)

What does the digraph of a one-to-one function (injection) from a finite set \(X\) to a finite set \(Y\) look like? (Look for a test somewhat similar to the one we described for when a digraph is the digraph of a function.)

Hint

For each part of this problem, think about how many arrows are allowed to enter a vertex representing a member of \(Y\text{.}\)

(b)

What does the digraph of an onto function look like?

(c)

What does the digraph of a one-to-one and onto function from a finite set \(S\) to a set \(T\) look like?

Problem 27

The word permutation is actually used in two different ways in mathematics. A permutation of a set \(S\) is one-to-one from \(S\) onto \(S\text{.}\) How many permutations does an \(n\)-element set have?

Notice that there is a great deal of consistency between the use of the word permutation in Problem 27 and the use in Problem 20. If we have some way \(a_1,a_2,\ldots,a_n\) of listing our set, then any other list \(b_1,b_2,\ldots,b_n\) gives us the permutation of \(S\) whose rule is \(f(a_i) =b_i\text{,}\) and any permutation of \(S\text{,}\) say the one given by \(g(a_i)=c_i\) gives us a list \(c_1,c_2,\ldots,c_n\) of \(S\text{.}\) Thus there is really very little difference between the idea of a permutation of \(S\) and an \(n\)-element permutation of \(S\) when \(n\) is the size of \(S\text{.}\)

Subsection 1.2.3 The bijection principle

Another name for a one-to-one and onto function is bijection. The digraphs marked (a), (b), and (e) in Figure 1.2.3 are digraphs of bijections. The description in Problem 26.c of the digraph of a bijection from \(X\) to \(Y\) illustrates one of the fundamental principles of combinatorial mathematics, the bijection principle:

Two sets have the same size if and only if there is a bijection between them.

It is surprising how this innocent sounding principle guides us into finding insight into some otherwise very complicated proofs.

Subsection 1.2.4 Counting subsets of a set

Problem 28

The binary representation of a number \(m\) is a list, or string, \(a_1a_2\ldots a_k\) of zeros and ones such that \(m=a_12^{k-1} + a_2 2^{k-2} +\cdots+ a_k 2^0.\) Describe a bijection between the binary representations of the integers between 0 and \(2^n-1\) and the subsets of an \(n\)-element set. What does this tell you about the number of subsets of an \(n\)-element set?

Hint

The problem is asking you to describe a one-to-one function from the set of binary representations of numbers between \(0\) and \(2^n-1\) onto the set of subsets of the set \([n]\text{.}\) Write down these two sets for \(n = 2\text{.}\) They should both have four elements. The set of binary representations should contain the string \(00\text{.}\) You could think of this as the instruction ``take no ones and take no twos.'' In that context, what could you think of the string \(11\) as standing for? This should help you describe a function. Of course now you have to figure out how to show it is one-to-one and onto.

Notice that the first question in Problem 8 asked you for the number of ways to choose a three element subset from a 12 element subset. You may have seen a notation like \(\binom{n}{k}\text{,}\) \(C(n,k)\text{,}\) or \(_nC_k\) which stands for the number of ways to choose a \(k\)-element subset from an \(n\)-element set. The number \(\binom{n}{k}\) is read as “\(n\) choose \(k\)” and is called a binomial coefficient for reasons we will see later on. Another frequently used way to read the binomial coefficient notation is ``the number of combinations of \(n\) things taken \(k\) at a time." You are going to be asked to construct two bijections that relate to these numbers and figure out what famous formula they prove. We are going to think about subsets of the \(n\)-element set \([n] = \{1,2,3,\ldots, n\}\text{.}\) As an example, the set of two-element subsets of \([4]\) is

\begin{equation*} \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}\}. \end{equation*}

This example tells us that \(\binom{4}{2} = 6\text{.}\)

Problem 29

Let \(C\) be the set of \(k\)-element subsets of \([n]\) that contain the number \(n\text{,}\) and let \(D\) be the set of \(k\)-element subsets of \([n]\) that don't contain \(n\text{.}\)

(a)

Let \(C'\) be the set of \((k-1)\)-element subsets of \([n-1]\text{.}\) Describe a bijection from \(C\) to \(C'\text{.}\) (A verbal description is fine.)

(b)

Let \(D'\) be the set of \(k\)-element subsets of \([n-1]=\{1,2,\ldots n-1\}\text{.}\) Describe a bijection from \(D\) to \(D'\text{.}\) (A verbal description is fine.)

(c)

Based on the two previous parts, express the sizes of \(C\) and \(D\) in terms of binomial coefficients involving \(n-1\) instead of \(n\text{.}\)

(d)

Apply the sum principle to \(C\) and \(D\) and obtain a formula that expresses \(\binom{n}{k}\) in terms of two binomial coefficients involving \(n-1\text{.}\) You have just derived the Pascal Equation that is the basis for the famous Pascal's Triangle.

Subsection 1.2.5 Pascal's Triangle

The Pascal Equation that you derived in Problem 29 gives us the triangle in Figure 1.2.4. This figure has the number of \(k\)-element subsets of an \(n\)-element set as the \(k\)th number over in the \(n\)th row (we call the top row the zeroth row and the beginning entry of a row the zeroth number over). You'll see that your formula doesn't say anything about \(\binom{n}{k}\) if \(k=0\) or \(k=n\text{,}\) but otherwise it says that each entry is the sum of the two that are above it and just to the left or right.

\begin{equation*} \begin{matrix}\amp \amp \amp \amp \amp \amp \amp 1\amp \amp \amp \amp \amp \amp \amp \\ \amp \amp \amp \amp \amp \amp 1\amp \amp 1\amp \amp \amp \amp \amp \amp \\ \amp \amp \amp \amp \amp 1\amp \amp 2\amp \amp 1\amp \amp \amp \amp \amp \\ \amp \amp \amp \amp 1\amp \amp 3\amp \amp 3\amp \amp 1\amp \amp \amp \amp \\ \amp \amp \amp 1\amp \amp 4\amp \amp 6\amp \amp 4\amp \amp 1\amp \amp \\ \amp \amp 1\amp \amp 5\amp \amp 10\amp \amp 10\amp \amp 5\amp \amp 1\amp \\ \amp 1\amp \amp 6\amp \amp 15\amp \amp 20\amp \amp 15\amp \amp 6\amp \amp 1\\ 1\amp \amp 7\amp \amp 21\amp \amp 35\amp \amp 35\amp \amp 21\amp \amp 7\amp \amp 1 \end{matrix} \end{equation*}
Figure 1.2.4 Pascal's Triangle

Problem 30

Just for practice, what is the next row of Pascal's triangle?

Problem 31

Without writing out the rows completely, write out enough of Pascal's triangle to get a numerical answer for the first question in Problem 8.

Hint

Starting with the row 1 8 28 56 70 56 28 8 1, put dots below it where the elements of row 9 should be. Then put dots below that where the elements of row 10 should be. Do the same for rows 11 and 12. Mark the dot where row 12 should appear. Now mark the dots you need in row 11 to compute the entry in column 3 of row 12. Now mark the dots you need in row 10 to compute the marked entries in row 11. Do the same for rows 9 and 8. Now you should be able to see what you need to do.

It is less common to see Pascal's triangle as a right triangle, but it actually makes your formula easier to interpret. In Pascal's Right Triangle, the element in row \(n\) and column \(k\) (with the convention that the first row is row zero and the first column is column zero) is \(\binom{n}{k}\text{.}\) In this case your formula says each entry in a row is the sum of the one above and the one above and to the left, except for the leftmost and rightmost entries of a row, for which that doesn't make sense. Since the leftmost entry is \(\binom{n}{0}\) and the rightmost entry is \(\binom{n}{n}\text{,}\) these entries are both one (to see why, ask yourself how many \(0\)-element subsets and how many \(n\)-element subsets an \(n\)-element set has), and your formula then tells how to fill in the rest of the table.

\(k=0\) 1 2 3 4 5 6 7
\(n=0\) 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
Table 1.2.5 Pascal's Right Triangle

Seeing this right triangle leads us to ask whether there is some natural way to extend the right triangle to a rectangle. If we did have a rectangular table of binomial coefficients, counting the first row as row zero (i.e., \(n=0\)) and the first column as column zero (i.e., \(k=0\)), the entries we don't yet have are values of \(\binom{n}{k}\) for \(k>n\text{.}\) But how many \(k\)-element subsets does an \(n\)-element set have if \(k>n\text{?}\) The answer, of course, is zero, so all the other entries we would fill in would be zero, giving us the rectangular array in Figure 1.2.6. It is straightforward to check that Pascal's equation now works for all the entries in the rectangle that have an entry above them and an entry above and to the left.

\(k=0\) 1 2 3 4 5 6 7
\(n=0\) 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
2 1 2 1 0 0 0 0 0
3 1 3 3 1 0 0 0 0
4 1 4 6 4 1 0 0 0
5 1 5 10 10 5 1 0 0
6 1 6 15 20 15 6 1 0
7 1 7 21 35 35 21 7 1
Table 1.2.6 Pascal's Rectangle
Problem 32

Because our definition told us that \(\binom{n}{k}\) is 0 when \(k>n\text{,}\) we got a rectangular table of numbers that satisfies the Pascal Equation.

(a)

Is there any other way to define \(\binom{n }{k}\) when \(k>n\) in order to get a rectangular table that agrees with Pascal's Right Triangle for \(k\le n\) and satisfies the Pascal Equation?

Hint

Begin by trying to figure out what the entries just above the diagonal of the rectangle are. After that, what other entries can you figure out?

(b)

Suppose we want to extend Pascal's Rectangle to the left and define \(\binom{n}{-k}\) for \(n\ge 0\) and \(k>0\) so that \(-k\lt 0\text{.}\) What should we put into row \(n\) and column \(-k\) of Pascal's Rectangle in order for the Pascal Equation to hold true?

Hint

See if you can figure out what the entries in column \(-1\) have to be.

(c)

What should we put into row \(-n\) and column \(k\) or column \(-k\) in order for the Pascal Equation to continue to hold? Do we have any freedom of choice?

Hint

What does the sum of two consecutive values in row \(-1\) have to be? Could this sum depend on which two consecutive values we take? Is there some value of row \(-1\) that we could choose arbitrarily? Now what about row \(-2\text{?}\) Can we make arbitrary choices there? If so, how many can we make, and is their position arbitrary?

Problem 33

There is yet another bijection that lets us prove that a set of size \(n\) has \(2^n\) subsets. Namely, for each subset \(S\) of \([n]=\{1,2,\ldots, n\}\text{,}\) define a function (traditionally denoted by \(\chi_S\)) as follows. 1 The symbol \(\chi\) is the Greek letter chi that is pronounced Ki, with the \(i\) sounding like “eye.”

\begin{equation*} \chi_S(i) = \begin{cases}1 \amp \text{ if } i\in S \\ 0 \amp \text{ if } i\not\in S \end{cases} \end{equation*}

The function \(\chi_S\) is called the characteristic function of \(S\text{.}\) Notice that the characteristic function is a function from \([n]\) to \(\{0,1\}\text{.}\)

(a)

For practice, consider the function \(\chi_{\{1,3\}}\) for the subset \(\{1,3\}\) of the set \(\{1,2,3,4\}\text{.}\) What are

(i)

\(\chi_{\{1,3\}}(1)\text{?}\)

(ii)

\(\chi_{\{1,3\}}(2)\text{?}\)

(iii)

\(\chi_{\{1,3\}}(3)\text{?}\)

(iv)

\(\chi_{\{1,3\}}(4)\text{?}\)

(b)

We define a function \(f\) from the set of subsets of \([n]=\{1,2,\ldots, n\}\) to the set of functions from \([n]\) to \(\{0,1\}\) by \(f(S)=\chi_S\text{.}\) Explain why \(f\) is a bijection.

(c)

Why does the fact that \(f\) is a bijection prove that \([n]\) has \(2^n\) subsets?

In Problems 18, Problem 28, and Problem 33 you gave three proofs of the following theorem.

The proofs in Problem 28 and Problem 33 use essentially the same bijection, but they interpret sequences of zeros and ones differently, and so end up being different proofs. We will give yet another proof, using bijections similar to those we used in proving the Pascal Equation, at the beginning of Chapter 2.

Subsection 1.2.6 The quotient principle

Problem 34

As we noted in Problem 29, the first question in Problem 8 asked us for the number of three-element subsets of a twelve-element set. We were able to use the Pascal Equation to get a numerical answer to that question. Had we had twenty or thirty flavors of ice cream to choose from, using the Pascal Equation to get our answer would have entailed a good bit more work. We have seen how the general product principle gives us an answer to Problem 6. Thus we might think that the number of ways to choose a three element set from 12 elements is the number of ways to choose the first element times the number of ways to choose the second element times the number of ways to choose the third element, which is \(12\cdot11\cdot10=1320\text{.}\) However, our result in Problem 29 shows that this is wrong.

(a)

What is it that is different between the number of ways to stack ice cream in a triple decker cone with three different flavors of ice cream and the number of ways to simply choose three different flavors of ice cream?

(b)

In particular, how many different triple decker cones use the same three flavors? (Of course any three distinct flavors could substitute for vanilla, chocolate and strawberry without changing the answer.)

(c)

Using your answer from part b, compute the number of ways to choose three different flavors of ice cream (out of twelve flavors) from the number of ways to choose a triple decker cone with three different flavors (out of twelve flavors).

Problem 35

Based on what you observed in Problem 34.c, how many \(k\)-element subsets does an \(n\)-element set have?

Problem 36

The formula you proved in Problem 35 is symmetric in \(k\) and \(n-k\text{;}\) that is, it gives the same number for \(\binom{n}{k}\) as it gives for \(\binom{n}{n-k}\text{.}\) Whenever two quantities are counted by the same formula it is good for our insight to find a bijection that demonstrates the two sets being counted have the same size. In fact this is a guiding principle of research in combinatorial mathematics. Find a bijection that proves that \(\binom{n}{k}\) equals \(\binom{n}{n-k}\text{.}\)

Hint

The first thing you need to decide is “What are the two sets whose elements we are counting?” Then it will be easier to think of a bijection between these two sets. It turns out that these two sets are sets of sets!

Problem 37

In how many ways can we pass out \(k\) (identical) ping-pong balls to \(n\) children if each child may get at most one?

Hint

Ask yourself “What is a problem like this doing in the middle of a bunch of problems about counting subsets of a set? Is it related, or is it supposed to gives us a break from sets?”

Problem 38

In how many ways may \(n\) people sit around a round table? (Assume that when people are sitting around a round table, all that really matters is who is to each person's right. For example, if we can get one arrangement of people around the table from another by having everyone get up and move to the right one place and sit back down, we get an equivalent arrangement of people. Notice that you can get a list from a seating arrangement by marking a place at the table, and then listing the people at the table, starting at that place and moving around to the right.) There are at least two different ways of doing this problem. Try to find them both.

Hint 1

The problem suggests that you think about how to get a list from a seating arrangement. Could every list of \(n\) distinct people come from a seating chart? How many lists of \(n\) distinct people are there? How many lists could we get from a given seating chart by taking different starting places?

Hint 2

For a different way of doing the problem, suppose that you have chosen one person, say the first one in a list of the people in alphabetical order by name. Now seat that person. Does it matter where they sit? In how many ways can you seat the remaining people? Does it matter where the second person in alphabetical order sits?

We are now going to analyze the result of Problem 35 in more detail in order to tease out another counting principle that we can use in a wide variety of situations.

\(abc\) \(acb\) \(bac\) \(bca\) \(cab\) \(cba\)
\(abd\) \(adb\) \(bad\) \(bda\) \(dab\) \(dba\)
\(abe\) \(aeb\) \(bae\) \(bea\) \(eab\) \(eba\)
\(acd\) \(adc\) \(cad\) \(cda\) \(dac\) \(dca\)
\(ace\) \(aec\) \(cae\) \(cea\) \(eac\) \(eca\)
\(ade\) \(aed\) \(dae\) \(dea\) \(ead\) \(eda\)
\(bcd\) \(bdc\) \(cbd\) \(cdb\) \(dbc\) \(dcb\)
\(bce\) \(bec\) \(cbe\) \(ceb\) \(ebc\) \(ecb\)
\(bde\) \(bed\) \(dbe\) \(deb\) \(ebd\) \(edb\)
\(cde\) \(ced\) \(dce\) \(dec\) \(ecd\) \(edc\)
Table 1.2.8 The \(3\)-element permutations of \(\{a,b,c,d,e\}\) organized by which \(3\)-element set they permute.

In Table 1.2.8 we list all three-element permutations from the \(5\)-element set \(\{a,b,c,d,e\}\text{.}\) Each row consists of all \(3\)-element permutations of some subset of \(\{a,b,c,d,e\}\text{.}\) Because a given \(k\)-element subset can be listed as a \(k\)-element permutation in \(k!\) ways, there are \(3!=6\) permutations in each row. Because each \(3\)-element permutation appears exactly once in the table, each row is a block of a partition of the set of \(3\)-element permutations of \(\{a,b,c,d,e\}\text{.}\) Each block has size six. Each block consists of all \(3\)-element permutations of some three-element subset of \(\{a,b,c,d,e\}\text{.}\) Since there are ten rows, we see that there are ten \(3\)-element subsets of \(\{a,b,c,d,e\}\text{.}\) An alternate way to see this is to observe that we partitioned the set of all \(60\) three-element permutations of \(\{a,b,c,d,e\}\) into some number \(q\) of blocks, each of size six. Thus by the product principle, \(q\cdot 6=60\text{,}\) so \(q=10\text{.}\)

Problem 39

Rather than restricting ourselves to \(n=5\) and \(k=3\text{,}\) we can partition the set of all \(k\)-element permutations of \(S\) up into blocks. We do so by letting \(B_K\) be the set (block) of all \(k\)-element permutations of \(K\) for each \(k\)-element subset \(K\) of \(S\text{.}\) Thus as in our preceding example, each block consists of all permutations of some subset \(K\) of our \(n\)-element set. For example, the permutations of \(\{a,b,c\}\) are listed in the first row of Table 1.2.8. In fact each row of that table is a block. The questions that follow are about the corresponding partition of the set of \(k\)-element permutations of \(S\text{,}\) where \(S\) and \(k\) are arbitrary.

(a)

How many permutations are there in a block?

Hint

A block consists of all permutations of some subset \(\{a_1 , a_2, \ldots, a_k \}\) of \(S\text{.}\) How many permutations are there of the set \(\{a_1 , a_2, \ldots, a_k \}\text{?}\)

(b)

Since \(S\) has \(n\) elements, what does problem 20 tell you about the total number of \(k\)-element permutations of \(S\text{?}\)

(c)

Describe a bijection between the set of blocks of the partition and the set of \(k\)-element subsets of \(S\text{.}\)

Hint

What sets are listed, and how many times is each one listed if you take one list from each row of Table 1.2.8? How does this choice of lists give you the bijection in this special case?

(d)

What formula does this give you for the number \(\binom{n}{k}\) of \(k\)-element subsets of an \(n\)-element set?

Hint

You can make good use of the product principle here.

Problem 40

A basketball team has 12 players. However, only five players play at any given time during a game.

(a)

In how may ways may the coach choose the five players?

(b)

To be more realistic, the five players playing a game normally consist of two guards, two forwards, and one center. If there are five guards, four forwards, and three centers on the team, in how many ways can the coach choose two guards, two forwards, and one center?

Hint

The coach is making a sequence of decisions. Can you figure out how many choices the coach has for each decision in the sequence?

(c)

What if one of the centers is equally skilled at playing forward?

Hint

As with any counting problem whose context does not suggest an approach, it is useful to ask yourself if you could decompose the problem into simpler parts by using either the sum or product principle.

Problem 41

In Problem 38, describe a way to partition the \(n\)-element permutations of the \(n\) people into blocks so that there is a bijection between the set of blocks of the partition and the set of arrangements of the \(n\) people around a round table. What method of solution for Problem 38 does this correspond to?

Problem 42

In Problems 39.d and 41, you have been using the product principle in a new way. One of the ways in which we previously stated the product principle was “If we partition a set into \(m\) blocks each of size \(n\text{,}\) then the set has size \(m\cdot n\text{.}\)” In Problems 39.d and 41 we knew the size \(p\) of a set \(P\) of permutations of a set, and we knew we had partitioned \(P\) into some unknown number of blocks, each of a certain known size \(r\text{.}\) If we let \(q\) stand for the number of blocks, what does the product principle tell us about \(p\text{,}\) \(q\text{,}\) and \(r\text{?}\) What do we get when we solve for \(q\text{?}\)

The formula you found in the Problem 42 is so useful that we are going to single it out as another principle. The quotient principle says:

If we partition a set \(P\) into \(q\) blocks, each of size \(r\text{,}\) then \(q=p/r.\)

The quotient principle is really just a restatement of the product principle, but thinking about it as a principle in its own right often leads us to find solutions to problems. Notice that it does not always give us a formula for the number of blocks of a partition; it only works when all the blocks have the same size. In Chapter 6, we develop a way to solve problems with different block sizes in cases where there is a good deal of symmetry in the problem. (The roundness of the table was a symmetry in the problem of people at a table; the fact that we can order the sets in any order is the symmetry in the problem of counting \(k\)-element subsets.)

In Section A.2 of Appendix A we introduce the idea of an equivalence relation, see what equivalence relations have to do with partitions, and discuss the quotient principle from that point of view. While that appendix is not required for what we are doing here, if you want a more thorough discussion of the quotient principle, this would be a good time to work through that appendix.

Problem 43

In how many ways may we string \(n\) distinct beads on a necklace without a clasp? (Perhaps we make the necklace by stringing the beads on a string, and then carefully gluing the two ends of the string together so that the joint can't be seen. Assume someone can pick up the necklace, move it around in space and put it back down, giving an apparently different way of stringing the beads that is equivalent to the first.)

Hint 1

How could we get a list of beads from a necklace?

Hint 2

When we cut the necklace and string it out on a table, there are 2n lists of beads we could get. Why is it \(2n\) rather than \(n\text{?}\)

Problem 44

We first gave this problem as Problem 12.a. Now we have several ways to approach the problem. A tennis club has \(2n\) members. We want to pair up the members by twos for singles matches.

(a)

In how many ways may we pair up all the members of the club? Give at least two solutions different from the one you gave in Problem 12.a. (You may not have done Problem 12.a. In that case, see if you can find three solutions.)

Hint

You might first choose the pairs of people. You might also choose to make a list of all the people and then take them by twos from the list.

(b)

Suppose that in addition to specifying who plays whom, for each pairing we say who serves first. Now in how many ways may we specify our pairs? Try to find as many solutions as you can.

Hint

You might first choose ordered pairs of people, and have the first person in each pair serve first. You might also choose to make a list of all the people and then take them by twos from the list in order.

Problem 45

(This becomes especially relevant in Chapter 6, though it makes an important point here.) In how many ways may we attach two identical red beads and two identical blue beads to the corners of a square (with one bead per corner) free to move around in (three-dimensional) space?

Hint

It might be helpful to just draw some pictures of the possible configurations. There aren't that many.

Problem 46

While the formula you proved in Problems 35 and 39.d is very useful, it doesn't give us a sense of how big the binomial coefficients are. We can get a very rough idea, for example, of the size of \(\binom{2n}{n}\) by recognizing that we can write \((2n)^{\underline{n}}/n!\) as \(\frac{2n}{n}\cdot \frac{2n-1}{n-1}\cdots \frac{n+1}{1}\text{,}\) and each quotient is at least \(2\text{,}\) so the product is at least \(2^n\text{.}\) If this were an accurate estimate, it would mean the fraction of \(n\)-element subsets of a \(2n\)-element set would be about \(2^n/2^{2n}=1/2^n\text{,}\) which becomes very small as \(n\) becomes large. However it is pretty clear the approximation will not be a very good one, because some of the terms in that product are much larger than 2. In fact, if \(\binom{2n}{k}\) were the same for every \(k\text{,}\) then each would be the fraction \(\frac{1}{2n+1}\) of \(2^{2n}\text{.}\) This is much larger than the fraction \(\frac{1}{2^n}\text{.}\) But our intuition suggets that \(\binom{2n}{n}\) is much larger than \(\binom{2n}{1}\) and is likely larger than \(\binom{2n}{n-1}\) so we can be sure our approximation is a bad one. For estimates like this, James Stirling developed a formula to approximate \(n!\) when \(n\) is large, namely \(n!\) is about \(\left(\sqrt{2\pi n}\right){n^n/ e^n}\text{.}\) In fact the ratio of \(n!\) to this expression approaches 1 as \(n\) becomes infinite. 2 Proving this takes more of a detour than is advisable here; however there is an elementary proof which you can work through in the problems of the end of Section 1 of Chapter 1 of Introductory Combinatorics by Kenneth P. Bogart, Harcourt Academic Press, (2000). We write this as

\begin{equation*} n!\sim \sqrt{2\pi n}\frac{n^n}{e^n}. \end{equation*}

We read this notation as \(n!\) is asymptotic to \(\sqrt{2\pi n}\frac{n^n}{e^n}\text{.}\) Use Stirling's formula to show that the fraction of subsets of size \(n\) in an \(2n\)-element set is approximately \(1/\sqrt{\pi n}\text{.}\) This is a much bigger fraction than \(\frac{1}{2^n}\text{!}\)