The central goal of Combinatorics is to count things. Usually, there is a set of stuff that you would want to count. It could be number of permutations, number of seating arrangements, number of primes from 1 to 1 million and so on.

Counting number of elements in a set can be a tricky business. One strategy to count is: compare the set you want to count with another set that you know how to count.

The Strategy


  • Particularly, suppose you want to count the number of elements in set A. 
  • Find a set that you know how to count.
  • You should be able to compare the set A with set B.

The hard part is to come up with such a set B. Usually the problem itself does not contain any information about this new artificially created set B. 

However, when you are able to find such a set B, the effect can be magical. Usually, the set B is much easier to count and has a natural relationship with set A (one that you wish to count).

Comparing sets

Example 1: 

Suppose you wish to count the number of people who attended a theatre show. It is hard to go to every seat in the auditorium and physically count every person (after all, when you are counting, someone may visit the washroom, some may have entered late or left early and so on).

Instead of counting the Set of People count the Set of tickets sold. In today’s world, it does not sound to be an incredibly novel idea. However for the first men and women who thought about this, really created a groundbreaking discovery. They artificially created a set which is indirectly related to the set of people entering the auditorium.

Example 2: 

A more clever example could be counting the number of matches played in a knock out football tournament. Assume that no match ends in a draw. If a team loses a match, it is out of the tournament.

If n teams participate in such a knockout tournament, how many matches are played? (Try this first before reading on).

The answer is n-1. The reason is as follows: for every match played there is a unique losing team corresponding to that match. Hence, our task becomes much simpler: count the number of losing teams. But that is easy! There is one winner of the entire tournament (the one who gets the trophy). Hence n-1 teams must have lost. Therefore exactly n-1 matches were played.

Here we compared set of matches played with the set of defeated teams. Logically they must have the same number of elements. It happens so that the set of defeated teams is much easier to count.

Injection


Injection is a function or map between two sets with some special properties.

Suppose we have two sets A and B. is a function that takes input from set A and gives output in set B. (A function is, after all, an input-output machine! It must take some input, do the processing and spit out some output).

Input Output machine

Let \(a_1, a_2 \) be any two distinct elements of the set A. If \( f(a_1) , f(a_2) \) are also distinct in set B, then we say the function is injective. That is f takes different elements in set A to distinct elements in set B. 

Hence for every element in set A, we find a corresponding element in set B. Therefore the set B has, at least as many elements, as there are in the set A. But it may have more (there could be elements in set B, to which no element in set A comes).

Injection Function

Therefore if you can find an injection function from set A to set B, you can be sure that the number of elements in set B, is at least equal to (if not more) than the number of elements in set A.

Showcase Problem


With this background try to solve the following problem:

A = {1, 2, 3, …. , 20} . Consider the set of all permutations (rearrangement) of the elements of set A. A permutation is called good, if it has at least one pair of consecutive elements whose difference is exactly 10. All other permutations are called bad. Are there more of good permutations or bad permutations? 

Send solutions to [email protected]. 
In the next installment of this discussion, 
we will show, how to use injection 
principle to solve this problem.