Counting Using Bijections

We will only count elements of sets. Whenever we are faced with a combinatorial problem, we will put it in the form How many elements does the set S have?’’

One of the most widely used facts in combinatorics is that two sets have the same number of elements if and only if there is a bijection between them. Let us see how we can use this fact in solving problems.

Example 1.

In how many ways can we distribute 15 identical apples to 4 distinct students. Not all students have to get an apple.

Example 2

Determine the number of subsets of {1, 2, 3, 4, ..., 50} whose sum of elements is larger than or equal to 638.

2005-2013 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax