Bijections (cloned) | Combinatorics (cloned)

Bijections

Introduction

Fair warning: we are now in territory that more AIME prep than AMC prep: it’s helpful, but it isn’t your top priority unless you’ve already qualified for AIME.

This section is about using the formulas and techniques elsewhere in this chapter for the purpose of solving problems that seems like they ought to have nothing at all to do with those ideas and formulas. It’s a kind of “legal cheating” if you will.

To novices, this is going to sound a little crazy. But to experts, it’s often the obviously best way to tackle certain hard problems.

Definitions

bijection: A connection between the individual members of two different sets so that each object in Set A corresponds to one particular object in Set B.
bijection, as we are using the term in this unit: The observation that certain very difficult-seeming problems correspond to certain different but much more straightforward problems. This correspondence is so perfect that techniques and formulas for solving the straightforward problems can be applied equally well to the difficult ones, provided you know which difficult problems correspond to which straightforward ones. (Some memorization is required here.)

Stars and bars (partitioning)

Definitions

partition (verb): to apportion all the elements of a given set into distinguishable categories (or “buckets”). In other words, to divvy up.
partitioning (noun): a partitioning of a set is one particular division of the elements of that group into particular buckets.

The stars and bars technique is a great method for partitioning. It shows that you can distribute $n$ identical items among $k$ different groups in $(n n + k - 1)$ ways.

The idea is that you think of this as an arrangement not only of the items themselves, but also of the dividers between groups.

You can search the internet if you’d like more examples, perhaps starting with its Wikipedia entry. The pictures under the proof of Theorem Two on the Wikipedia page (linked above) may help you develop a visual intuition about this. AoPS’s explanation of the technique is also good.

Counting routes through a graph

The number of ways to move from the bottom left corner to the top right corner of an $m \times n$ grid by going only up or right is $(m m + n) = (n m + n)$ .

Why? Because we must move right $m$ times and up $n$ times, so our total is the same as the number of ways we can order the moves. (Expect variations on this theme as well.)

Recursion

There’s one other bijection I want to include here even though it doesn’t use combinatoric techniques. (That way there doesn’t have to be a whole new chapter for one example, which I think would be a little silly.)

Definitions

Recursion: The act of defining the next element of a list in terms of a previous element of the list.; Also: the act of defining an entire sequence in terms of a recursive act (as described above).

Recursion is useful to regular people in cases where it’s hard to calculate the $n t h$ element of a list directly.

Recursion is useful in a different way to the authors of contests like the AMC: it allows them to disguise easy questions as difficult ones.

Let’s look at an example. Do you know the eleventh Fibonacci number offhand? Yeah, me neither. But we both probably know the definition of the sequence:

$F_{0} = F_{1} = 1$ ; $F_{n} = F_{(} n - 1) + F_{(} n - 2)$ .

From this definition we can “recurse” our way to the eleventh term, $F (10)$ :

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89$ ; so $F_{10} = 89$ .

But there’s a lot more to recursion than Fibonacci.

For example, recursion shows up in diagrams: a repeating pattern is evidence of recursion. In this case, it can of course be useful to look carefully at the difference between each figure and the next.

There’s a well-known problem in which Josie is meant to climb ten stairs, and with each step she can cover one or two stairs. The question is: how many ways are there to get to the top? This turns out to be a sticky problem in lots of ways. But applying recursion helps a lot: Let’s say $F (n)$ is the number of ways to get to Step # $n$ . Then $F (0) = F (1) = 1$ . We know that to get to Step # $2$ , we needed to have come from either Step # $1$ or Step # $0$ (i.e. directly from the floor).

Think about that for a moment. It means that $F (2) = F (1) + F (0)$ . What’s more, that’s true for every step after the second, too. That means $F (n) = F (n - 1) + F (n - 2)$ . After all, any way that gets you to Step # $(n - 1)$ could then take you to Step # $n$ with a one-stair step, and any way that gets you to Step # $(n - 2)$ could then take you to Step #n with a two-stair step.

$F (n)$ is not just recursive; it’s the Fibonacci sequence, perhaps the best-known of the sequences often described recursively. So, since $F (n)$ is Fibonacci, we know that there are $89$ ways to get to Step # $10$ .

Other bijections

These are the biggies, but there are lots of little ones too. If you find any others that you think should be included here, please email me.

What to do

If you’re already scoring within 20 points of AIME qualification and the above explanations make enough sense that you’d be able to use the formulas once you had them memorized, then click “complete” below, and we’ll add all the relevant quizzes to your deck.