Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Chapter2Counting

In this Chapter we will consider counting problems. These will be problems, where we need to count the number of possibilities of something happening. Let us warm up to this first by solving some easy exercises.

At the “Freshmen's party” several people meet. Five friends (Arnold, Bill, Carl, David, Edmund) greet each other at this party by shaking hands. How many handshakes does this mean? It is not too hard to count all possibilities: Arnold shakes hand with Bill, Carl, David, Edmund, Bill shakes hand with Carl, David, Edmund (we have already counted the Arnold-Bill handshake), Carl shakes hand with David and Edmund (we have already counted the Arnold-Carl and Bill-Carl handshake), David shakes hand with Edmund (we have already counted all other handshakes with David), and all handshakes with Edmund is already accounted for. That is, there are \(4 + 3 + 2 + 1 = 10\) handshakes altogether.

Now, this was easy, but this party is very big, and a lot of people attend it. Say, there are 200 College freshmen greeting each other by shaking hands. How many handshakes are there? We can try to generalize our former argument. Let us count the number of handshakes by ordering the people in some way (say, by date of birth). That is, first we count the handshakes by the oldest person, then the handshakes by the second oldest person, etc. The oldest person shakes hand with 199 other people, this is 199 handshakes. The second oldest person shakes hand with 199 people, as well, but we have already counted 1 handshake with the oldest person. That is, we count 198 more handshakes. For the third oldest person, out of 199 handshakes we have already counted 2: one with the oldest person and one with the second oldest person. That is, we count 197 more handshakes, etc. Continuing this argument, we count one less handshakes with each person. For the second youngest people we count only one new handshake: the handshake with the youngest person. And finally, for the youngest person we have already counted all handshakes. That is, the number of handshakes is

\begin{equation*} 199 + 198 + 197 + \dots + 1\text{.} \end{equation*}

How much is this number? Is there an easier way to calculate it, rather than adding all these numbers together? Those who are familiar with arithmetic progressions can calculate easily that the answer is \(\frac{199 \cdot 200}{2} = 19~900\text{.}\) But even without that knowledge, we can calculate this sum by observing that the sum of the first and last number is 200. Then the sum of the second and one but last number is 200, again. We can continue this argument, and reach \(99+101=200\text{,}\) and the number 100 is left alone. That is,

\begin{align*} \amp 1 + 2 + \dots + 198 + 199 = (1 + 199) + (2 + 198) + \dots + (99 + 101) + 100\\ \amp = 99\cdot 200 + 100 = (99 \cdot 2 + 1 ) \cdot 100 = 19~900\text{.} \end{align*}

This summation argument works in general, as well:

Prove Proposition 2.0.1 by using the argument described above. Make two cases depending on whether \(n\) is even or odd.

We show another proof here, which is usually attributed to Carl Friedrich Gauss. 1 German mathematician and physicist, 1777–1855. Let \(S\) be the sum of the integers from 1 to \(n\text{,}\) and write the same sum in reverse order below:

\begin{align*} S \amp = 1 + 2 + \dots + (n-1) + n,\\ S \amp = n + (n-1) + \dots + 2 + 1.\\ \end{align*}

Adding the two equations together, we obtain

\begin{align*} 2S \amp = (1+n) + (2 + n-1) + \dots + (n-1 + 2) + (n+1),\\ 2S \amp = (n+1) + (n+1) + \dots + (n+1) + (n+1),\\ 2S \amp = n \cdot (n+1),\\ S \amp = \frac{n\cdot (n+1)}{2}\text{.} \end{align*}

Now, we are able to tell the number of handshakes between \(n\) people. Using the same line of thought, the first person shakes hand with \((n-1)\) other people, the next one with \((n-2)\) other people (we already counted the handshake with the first person), etc. That is, the number of handshakes between \(n\) people is

\begin{equation*} (n-1) + (n-2) + \dots + 1\text{,} \end{equation*}

which is \(\frac{(n-1)\cdot n}{2}\) by Proposition 2.0.1 (writing \((n-1)\) instead of \(n\)). Thus, we have proved

Even though we have already proved the statement above, we give here an alternative proof. The reason for this is that this proof method will be useful later on.

Every person shakes hand with \((n-1)\) other people. Altogether there are \(n\) people, this would mean \((n-1) \cdot n\) handshakes. But this way every handshake is calculated twice: a handshake between \(A\) and \(B\) is calculated once for \(A\) and once for \(B\text{.}\) Thus, in reality, \((n-1) \cdot n\) is twice the number of handshakes. That is, the number of handshakes is \(\frac{(n-1) \cdot n}{2}\text{.}\)

Five friends meet at this party. Some of them shake hands. Is it possible that everyone shook hands exactly three times? What is the answer if a person can shake hands with another more than once? What are the answers if seven people meet?

Four girls (Alice, Beth, Carrie, Diane) and four boys (Ed, Frank, George, Hugo) meet at this party. As a greeting any two boys shake hands with each other, but with the girls the two parties kiss each other on the cheek.

How many handshakes and kisses are there?

After greeting each other, they want to dance. In fact, every boy wants to dance with every girl, and they are interested in how many rounds they need to achieve this.

First, let us count the number of ways they can form dancing couples (one boy and one girl). There are four boys, and four girls, every boy wants to dance with every girl, that is, there are altogether \(4 \cdot 4 = 16\) possible couples. We can even list these 16 possibilities:

Alice — Ed Beth — Ed Carrie — Ed Diane — Ed
Alice — Frank Beth — Frank Carrie — Frank Diane — Frank
Alice — George Beth — George Carrie — George Diane — George
Alice — Hugo Beth — Hugo Carrie — Hugo Diane — Hugo

In one round four couples can dance. How many ways can they form four dancing couples for one round? Assume that each girl chooses a partner in a certain order. First Alice chooses a partner, then Beth, then Carrie, and finally Diane dances with whoever is left. Alice has four choices, because she can choose any of the boys. Beth will only have three choices, because Alice will have already chosen someone. Carrie will have only two choices, because Alice and Beth will have already chosen someone. Finally, Diane has only one choice. Altogether, they have \(4 \cdot 3 \cdot 2 \cdot 1 = 24\) possibilities to form four dancing couples at the same time.

Now, in one round at most four couples can dance. Therefore they will need at least \(\frac{16}{4} = 4\) rounds for everyone dancing with everyone else. But be careful! We only proved that they need 4 rounds, we have not proved that they can actually do it in 4 rounds. The easiest is to just give a “schedule” for the 16 couples in each rounds, e.g. see Table 2.0.6

1st round 2nd round 3rd round 4th round
Alice — Ed Beth — Ed Carrie — Ed Diane — Ed
Beth — Frank Alice — Frank Diane — Frank Carrie — Frank
Carrie — George Diane — George Alice — George Beth — George
Diane — Hugo Carrie — Hugo Beth — Hugo Alice — Hugo
Table2.0.6Four couples dancing in four rounds

Is it possible

  1. to distribute 100 rabbits into five packs such that each pack contains an odd number of rabbits?

  2. that both the sum and the product of some integer numbers are 9?

  3. that both the sum and the product of 9 integer numbers are 9?

  4. that the sum of 9 integer numbers is 0 and the product of these numbers is 9?

  1. What is the sum of the first 24 positive integers, i.e. \(1 + 2 + 3 + \dots + 23 + 24 =\text{?}\)

  2. Compute \(\frac{1 + 2 + 3 + 4 + \dots + 23 + 24}{1 - 2 + 3 - 4 + \dots + 23 - 24}\text{.}\)