## Introduction to the Theory of CountingCombinatorics is full of beautiful tricks and most problems we encounter do depend on tricks in one way or another. However, when faced with a new problem, hunting for tricks should not be the first approach to take. If the problem is asking about counting some objects, the question to start with should be ``How would I solve this problem if I had an infinite amount of time?’’ Answering this question would force us to design a labeling of all combinatorial configurations. The key to solving difficult problems is a systematic labeling. We need to develop a very precise language even to understand what ``counting’’ means. ## Bad combinatoricsBefore we start, let us point out what is a bad language in combinatorics, and let us see how we can avoid it when necessary.
It is easy to see that the previous solution is bad. The above presentation of the solution was made more ugly than necessary, but nevertheless, you can’t improve it by minor cosmetic tune-ups. The word ``overcounting’’ is bad on many levels. It even won’t pass spell-check. Here is another source of disaster: ``We can choose the first student in 5 ways.’’ Who is the ``first student?’’ Problem didn’t mention that guy, and our solution didn’t define him (nor her). We can try defining this concept but we will end up in an endless hunt for undefined things that are just going to appear one after another. Despite the fact that many have used similar arguments in the past and got away with it, we will now solve the previous problem using precise and rigorous mathematical propositions. We will start with stating with the fundamental rule of combinatorics: Elements of sets are the only objects that we are allowed to count. ## Good combinatoricsEvery problem in the theory of counting needs to be formulated as ``How many elements does the set \( S \) have?’’ Our task is to define set \( S \) and count its elements. Here is the correct presentation of the solution to the problem above.
Even though you are not required to go to this many details when writing mathematics, it is good to know what rigorous and complete proof is and how to write it if you absolutely must. This skill will be of use in solving more complicated problems. |

2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |