## Functions, Bijections, and Combinatorics ☆

| January 23, 2014

At times, studying general definitions of functions and particular classifications of functions (e.g., bijective, surjective) can seem tedious. As a secondary teacher, the functions we consider nearly always map real numbers to real numbers, which can make it difficult to be motivated to push past this into the abstract. While bijections have implications for infinite cardinalities, and while there are many examples of functions in real life that map different types of objects, such as mapping students to desks, vending machine buttons to sodas, or published works to ISBNs, the implications for studying functions can feel somewhat irrelevant. However, I have come to appreciate these ideas – in particular, as they arise in common counting problems or combinatorics.

Counting problems, while often simple to state, can span the spectrum of difficulty – from ridiculously easy to insanely complex. Often, however, one of the tools of the trade in counting problems is counting an “analogous” problem. This process, however, requires functions, and in particular, bijections: if there is a bijective function between two sets, then the two sets have the same cardinality (or size). A few thoughts about how understanding more abstract sets and classifications for functions can be important are discussed below.

1.The handshake problem. In a group of 10 people, if everyone shakes hands with everyone else, how many total handshakes are given?

This is a familiar problem. Having done this with high school students, one of the common ways of approaching this problem is to physically model the handshakes. Done in a systematic way, this often results in the series, 9+8+7+…+3+2+1 = 45. This is a nice way to solve the problem, and which can be a nice way of introducing arithmetic series. However, in the context of combinatorics, one very powerful way is to model this problem differently. In particular, it is to create a bijective function, mapping every “physical” handshake to an ordered pair. If we assume the first 10 letters of the alphabet represent the 10 people in the room, then every handshake involves two people, and we can list the handshake between A and F as (A,F). (In particular, since we only want “one” handshake, we only want, say, ordered pairs in alphabetical order, so that (A,F) is counted, but not (F,A).) We can verify that this is a bijective function by clarifying that “every handshake” will map to an ordered alphabetical pair, and every ordered alphabetical pair will be mapped to from some handshake. Indeed, this is the case. The power in doing so is that we no longer have to think about the physical activity of shaking hands. By counting a different problem, which began by mapping the objects we wanted to count to a set of more countable objects – how many ordered alphabetical pairs are there with the first ten letters of the alphabet – we can make a conclusion about the total number of handshakes. Since there are 10C2 such ordered pairs, then there must be 10C2 (or 10*9/2! = 45) handshakes.

2. How do we know that 7C2 is the same as 7C5 (without relying on the formulas)? Or, more generally, why is nCk = nC(n-k)?

Based on the formula for a combination, it is easy to conclude that these two quantities are the same size. However, it may be less obvious why there are the same number of ways to form a “pair” as a “group of 5” from a room with seven people. There are analogies that can help explain, but the analogies often make use of bijective functions. The set of “pairs” of people look like: {(A,B), (A,C), (A,D), …(F,G)}. The set of “group of 5” look like: {(A,B,C,D,E), (A,B,C,D,F), … (C,D,E,F,G)}. How do we know there are the same number of elements in each set? The easiest way is to find a bijective function between these two “sets” of objects. Indeed, while there are many, perhaps the easiest to justify is to map (A,B) -> (C,D,E,F,G), (A,C) -> (B,D,E,F,G), etc., effectively mapping the “pair” to the “remaining people left”. Indeed, every pair formed has exactly 5 people not chosen, which means every “pair” will map to some element in the “group of 5 set”; similarly, every “group of 5” formed will be mapped from, because every “group of 5” has exactly 2 people not chosen, which will be the “pair” that maps to it. Thus, this mapping between these sets of objects can be used to verify that sets of 7C2 and 7C5 have the same cardinality. (The analogy being that for every group of 2 selected, there are 5 not selected – thus they must be the same size sets.) The more general argument concluding nCk=nC(n-k) follows naturally.

3. How many different subsets can be formed from a set of n elements?

One way of answering this problem is to say that each element can either be “in” or “out” of the subset, thereby creating 2^n subsets. Another argument, an inductive one, is to show that if there are 2^n subsets with n elements, there will be 2^n+1 subsets with n+1 elements. Again, this involves a bijective mapping. Say we have all the subsets with “n” elements listed – what does adding the element “n+1” do? Well, all of the subsets with “n” elements are also subsets of this new set. Additionally, there are subsets with the element “n+1” that we need to count. Considering this set, there is a bijective function between the subsets with the element “n+1” and the (2^n) subsets with “n” elements. Each subset with “n+1”, for example: (1, 3, 5, 7, n+1) can be mapped to the subset without the “n+1” element, in this case, to (1, 3, 5, 7). In this way, (n+1) gets mapped to the empty set (from the subsets with “n” elements), and, indeed, since every other subset with “n+1” has some elements from the “n” elements, there is a bijection. The conclusion, of course, is that the cardinalities of these two sets (subsets with “n” elements, and subsets including the element “n+1”) are the same: namely, they are both 2^n. Thus, there are 2^n+2^n = 2^(n+1) subsets with “n+1” elements, which completes the inductive step of the proof.

4. How many numbers between 0 and 10,000 have digits that sum to 9?

This is a relatively difficult problem, and the easiest way to solve it is approaching it as a multi-choose (e.g., stars and bars) problem. But even this can be hard to follow and conceptualize. In fact, what is happening in this process is a bijection. The solution actually consists of the numbers: {0009, 0090, …, 3105, …}. But how many are there? The stars and bars method in this case is actually “mapping” each of these numbers to a 9-letter object. In particular, if we let Th=Thousands, H=hundreds, T=tens, and O=ones, then each of the solution elements can be created by a 9-string using these four letters (again, we will consider these written as “alphabetical” based on digits): ThThHHTTTOO maps to 2,232. And because each of these strings has 9 letters, we can verify that the sum of the digits will be equal to 9 in every case; and since every number between 0 and 10,000 will have a certain number (between 0 and 9) of Ths, Hs, Ts, and Os, then there is a bijection between these two sets. Therefore, we can instead count the number of 9-strings, from four “letters” (where letters can repeat and order does not matter – aka, we only consider “one” of these strings – namely, the “alphabetical” based on digits one), which amounts to 12C3 ways. But the key to answering the original question lies in transforming it, modeling it, mapping it, to a collection of objects that is easier to count.

5. Random variables in statistics

Lastly, another common application of functions comes from statistics. In fact, random variables are functions. In particular, they are functions that map the outcome set to the set of real numbers. For example, the outcome set for flipping a coin three times consists of the following elements – effectively the “data” from the experiement: {HHH, HHT, HTH, HTT, THH, THT, TTH ,TTT}. Yet often what is of interest is a random variable, something like, say, X=the number of heads. Accordingly, this function, X, then maps each of the elements in the set to a number: 0, 1, 2, or 3 (i.e.,  HHH -> 3, whereas HTT -> 1). Indeed, understanding this relationship is critical to properly conceptualizing aspects of probability. In the original outcome set each of the eight outcomes are equally-likely, whereas because of the functional mapping process the random variable outcomes (0, 1, 2, 3) are not equally-likely. Notably, this mapping is not a bijection, since 1, for example, is mapped to from three different elements (HTT, THT, TTH) – which is in fact the reason that getting 1 head is three times as likely as getting 0 heads.

These examples are by no means the only ones. However, they do perhaps provide some real applications and uses for understanding sets and functions more generally (particularly bijective functions), and they can provide a relatively natural contexts – counting problems – for becoming increasingly familiar with these concepts. Much of the time when we “solve a related” counting problem, we end up applying a bijective function – whether we are aware of it or not – as the means to help verify that we have counted correctly. 