# How do you teach the correctness of bijections when dealing with counting in combinatorics?

Consider the problem of awarding prizes to people in a school.

Let $A$ be the set of awards and $|A| = m = 3$.

Let $P$ be the set of people in the school and $|P| = n$.

Then in how many ways can we award these 3 different awards to n students?

Let the pair/tuple $\langle a_i, p_k \rangle$ indicate that award $a_i$ was given to student $p_k$ (note that the same person may earn/win all the awards, someone can get all prizes!).

One example of awarding the 3 prizes (if n = 2):

$$(\langle a_1, p_1 \rangle, \langle a_2, p_2 \rangle, \langle a_3, p_1 \rangle)$$

Basically we do it this way:

“person x wins award a_1, y wins award a_2, and z wins award a_3”

so we get that we always have $|A|=m$ "spaces" where we need to select which person will get an award. This suggests that we have a bijection from the set of sequences $P^3 = P \times P \times P$ to the ways of awarding three prizes.

This yields that the way of awarding the $|A|=m=3$ awards/prizes is:

$$|P^3| = |P|^3$$

For me the solution makes sense. However, the problem I am having with it is not my understanding it but pedagogically, how to teach its the correct answer (maybe I don't understand it as much as I thought I did...) and how to convince someone else that this bijection is correct and that we are not "missing" anything in the way we are counting.

I had someone ask me, what if we arranged the "spaces", i.e. give the awards in different orders. Instead of doing $a_1, a_2, a_3$ we awarded the prizes in the order $a_2, a_3, a_1$. Wouldn't that be a bijection too? Then if it is, doesn't it mean that we are in fact, NOT counting all the ways to award the prices because we could have awarded them in different order.

I explained that the order does NOT matter and that we are double counting (if we included more counts), however, it was clear to me that the student was not satisfied. Does someone have a better more intuitive, or even maybe more rigorous way of clarifying this misconception? I am having the problem that maybe this is so "obvious" to me that its hard to know what I need to say or what I could do to help them understand better. Any ideas?

One problem is that you wrote

$$\big(\langle a_1,p_1\rangle,\langle a_2,p_2\rangle,\langle a_3,p_3\rangle\big)$$

$$\{\langle a_1,p_1\rangle,\langle a_2,p_2\rangle,\langle a_3,p_3\rangle\}\;.$$

That makes

$$\big(\langle a_2,p_2\rangle,\langle a_3,p_3\rangle,\langle a_1,p_1\rangle\big)$$

look like something different, since the parentheses make it look like an ordered triple. In fact it should be

$$\{\langle a_2,p_2\rangle,\langle a_3,p_3\rangle,\langle a_1,p_1\rangle\}\;,$$

the same function from $\{a_1,a_2,a_3\}$ to $P$ with its elements listed in a different order. But the order in which we name the elements of a set is irrelevant. The sets

\begin{align*} &\{\langle a_1,p_1\rangle,\langle a_2,p_2\rangle,\langle a_3,p_3\rangle\}\;,\\ &\{\langle a_1,p_1\rangle,\langle a_3,p_3\rangle,\langle a_2,p_2\rangle\}\;,\\ &\{\langle a_2,p_2\rangle,\langle a_1,p_1\rangle,\langle a_3,p_3\rangle\}\;,\\ &\{\langle a_2,p_2\rangle,\langle a_3,p_3\rangle,\langle a_1,p_1\rangle\}\;,\\ &\{\langle a_3,p_3\rangle,\langle a_1,p_1\rangle,\langle a_2,p_2\rangle\}\;,\text{ and}\\ &\{\langle a_3,p_3\rangle,\langle a_2,p_2\rangle,\langle a_1,p_1\rangle\} \end{align*}

are all the same set and hence the same function from $\{a_1,a_2,a_3\}$ to $P$. If you’ve emphasized that fact about sets sufficiently, it should at least help in making the point.

Less technically, all we’re saying is that the outcome — the actual identification of who gets each award — has nothing to do with the order in which the awards are actually presented. The function tells who gets what; it doesn’t say in what order the awards are actually distributed. They might even be distributed simultaneously be three different presenters.

• I realized that notation confusion after I wrote my question. It is so important. Thanks for pointing it out, I agree with you. Thanks :) – Pinocchio Nov 7 '14 at 18:50
• @Pinocchio: You’re welcome. By the way, it’s really my last paragraph that I’d probably use first in trying to sort out the student’s confusion. – Brian M. Scott Nov 7 '14 at 18:52