Combinatorics (Table of contents)

Counting with 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.