Introduction (cloned) | Combinatorics (cloned)

Combinatorics

Do you know enough combinatorics techniques and formulas to do well on the AMC? Before you answer, consider that the AMC not only requires you to know these things, but it also requires you to know when to use the various techniques and formulas in solving both counting problems and probability problems.

Let’s bone up on all these topics so that you can not only get to AIME, but also do well once you’re there.

The basics

Combinatorics is mostly about the technical language used to describe certain complicated situations. (By contrast, probability is mostly about how to think about such situations.)

The tricky bit here is that the technical language doesn’t connect to the ideas in an obvious way. That makes learning combinatorics extra difficult: it often isn’t clear why you’re learning what you’re learning.

The best bridge from the conceptual to the technical that I know rests on the following definition:

Definitions

The first rule of probability: The chance of getting what you want can be calculated by counting the number of ways you can get what you want, and dividing by the total number of things you could possibly get.

Or, in the language of math: $P (good outcome) = \frac{number of good outcomes}{number of all outcomes}$

Crucially, this means, that we need to be very good at thinking about different possible scenarios, and counting them accurately, even when the numbers get very large (as they often do on the AMC).

The main mathematical tools we rely on for this purpose are:

The choose operation
The permute operation
The factorial operation

Definitions

Choose: To choose is to calculate (with the help of a formula) the number of ways one can select a subgroup of distinguishable items from a larger group of distinguishable items.
Permute: To permute is to calculate (with the help of a formula) the number of ways one can select an ordering of a subgroup of distinguishable items from a larger group of distinguishable items.
Factorial: The factorial of an integer is defined as the product of that integer with all smaller positive integers. (This turns out to be an important part of the choose and permute formulas.)

Using these operations and their symbols

Let’s start by observing what these operations look like and sound like in context.

Let’s say there are four students in a classroom and you want to know how many different pairs of students could be selected to work on a project together.

We say that there are “4 choose 2” ways to pick pairs. We’d write it as $(2 4)$ , or less commonly as $_{4} C_{2}$ . Technically this is called a combination: there are $(2 4)$ different combinations of two people that can be made from an initial pool of four.

Now let’s examine a similar-but-different situation: there are four students in the class, and this time we’re interested in electing a president and a vice-president. Note that this is equivalent to asking the question “how many different pairs can I make out or four people, if I am keeping track of which one of the pair gets picked first (so that I can make that person president and the other vice-president)?” This is expressed as $_{4} P_{2}$ , and is called a permutation, which is where the $P$ comes from. Out loud, we often pronounce the expression $_{4} P_{2}$ as “ $4$ permute $2$ .”

To distinguish these two from each other, it’s common to say that “for combinations, order doesn’t matter; for permutations, order matters.” Some people find this helpful; others find it confusing. <shrug emoji plus smiley face>

We commonly use these symbols in discussion in lieu of the actual numbers they represent, especially when that makes it easier to follow the (often complicated) argument that builds to a solution, as in this example:

If there are $20$ juniors and $10$ seniors in a certain class, then how many ways are there to pick a group of two juniors and two seniors for a special committee?

(spoiler)

There are $(2 20)$ ways to choose the juniors and $(2 10)$ ways to choose the seniors. Any one of the junior groups could be combined with any one of the senior groups to form a unique committee, so the final answer is $(2 20)$ $(2 10) = 190 \cdot 45 = 8550.$

Note that the numbers don’t really help make the argument clear. Sticking with the symbols until the very end makes it easier to make sure that the argument is logically sound, which is often the most important part of such solutions.

Calculating their values (i.e. the formulas)

$(r n) = \frac{n !}{r ! ( n - r )!}$

$_{n} P_{r} = \frac{n !}{( n - r )!}$

Note the similarities of these two formulas (and their one key difference).

For given values of $n$ and $r$ , there will always be at least as many combinations as permutations (and in many cases far more!) because for any combination of things, there is one or more possible permutations (i.e. orderings) of those items.

What to do next

If everything above was old news to you, then this section should be difficult but doable. Click “complete” below, and we’ll add all the relevant quizzes to your deck. Then, during your short daily practice, we’ll occasionally quiz you on this knowledge in a way that etch it into your memory for good.
If some or all of this was new to you, then hold off for now. Instead, see below for some resources you should take advantage of.

Reading through Chapter 25 of AoPS Volume 1, and doing a few of the many problems there, is one of many good ways to reinforce the basic ideas you need in order to get full value out of this unit of the course. If you don’t have that book, I recommend buying it. (Note: I’m not related to AoPS in any way, and they don’t pay me anything to say this. I just think it’s a good book.) If you’d rather not, though, don’t worry; a search will lead you to many other great resources as well.

Chapter 15 of AoPS Volume 2 is also very helpful if you happen to already have it. Some of the more complicated quizzes from this unit are explained more fully in that chapter.

Note: We are on Version 3 of this course at the time I write this. By Version 4, most or all of the AoPS explanations I’m recommending above will be in the course itself, and as a registered user of this course you will (of course) have full access to that material. The reason I’m pointing you to the AoPS chapters above is that they do a great job of explaining this material, and you probably already have the book(s) anyhow. This allows me to focus on more fully developing other parts of the course whose information isn’t so readily available elsewhere.