Basic Combinatorics, Part One

Note: This is part one of a two-part article. This topic was suggested by a former student of mine, who shall remain anonymous

© 2014 - CC0 Creative Commons - from University of Birmingham College of Engineering and Physical Sciences

Having coached math teams both in the United States and in Asia, I find that one topic which can sometimes elude for first-timers, particularly younger students, is that of combinatorics. These are often coupled with probability, and require that we count the number of ways an event can occur, or the number of possible ways of "choosing" from a set or multiple sets of items. What follows is a very brief introduction to some basic ideas in combinatorics.

For this, we study the topics of permutations and combinations.

The Essentials

We will begin by introducing a few essential concepts:

1. The Product Rule: Given p ways to choose one element from one set, and q ways to choose one element from another, there are pq ways to choose the two different elements (one from each set)
2. The Sum Rule: Given p ways to choose one element from one set, and q ways to choose one element from another, there are p+q ways to choose a single element from either set.

We'll illustrate these by an example:

Suppose a certain restaurant offers three choices for an appetizer, three for a main course, and two courses for dessert. How many possible meals can one order?

In this example the number of meals, following the product rule, is simply the product of the number of choices in each category, or 18.

Another important concept in combinatorics is the factorial. The factorial, written as , essentially states the number of ways we can order a set of n distinct objects. For example, we can order the letters XYZ in six, or 3!, distinct ways: XYZ, XZY, YZX, YXZ, ZYX, ZXY.

Combinations and Permutations

The factorial is key to understanding another key concept in such questions, the permutation. We can think of the permutation as the number of possible ways in which we can select k distinct objects from a set of n objects. To illustrate by means of an example:

Given a group of ten people, how many possible ways are there to select a chairperson and vice-chairperson, given that nobody may hold both positions?

Clearly, there are ten possible choices for a chairperson. However, once this person is chose, he's not eligible to be vice-chair. There are nine remaining people for the position of vice-chairperson, so this gives us 90 possible choices.

In general, the number of possible permutations, i.e. choosing k distinct objects from a set of n objects is given by:

The last concept in our initial survey of combinatorics shall be the "combination". The combination differs from the permutation in that order does not matter. For example, if 9 people wish to select five from among themselves to form a five-a-side football team, the number of possible teams, according to the equation above would be:

This answer accounts for every possible combination, taking into account the positions that each person plays. If our goal is to merely decide who will be on the team, and not consider the positions of the players, then the number of possible teams is smaller. Recalling that there are n! possible ways to place n players, we would have:

Therefore, the number of possible teams one can have, when position is not considered, is 15120/120, or 126 possible teams, a much more manageable number.