1. Tuples

Q: given a set of n symbols, how many different sequences of length k can we form out of these symbols?
A: these sequences are called tuples. There are n^k sequences.

This is actually easy to think. How many numbers are there from 0 – 9999? By common sense we know that there’re 10000 numbers. There’re 10 numbers from 0 – 9, 100 numbers from 0 – 99, 1000 numbers from 0 – 999. Thus 10000 numbers from 0 – 9999.

Instead of direct counting, we can think it another way. There’re 4 positions XXXX. Each position we can put in 0 – 9, altogether 10 numbers. As a result we have 10 x 10 x 10 x 10 ways to choice our number. That is 10000 ways.

2. Permutations

Tuples of length k without repetitions are called k-permutations.

Permutations are slightly different from tuples. The difference is “without repetitions”. In our previous example we can have numbers like 7777, with repetitions. If we don’t allow same number appears twice, then this is a question about permutations.

For the first position, we have 10 choices. The second position, 9 choices. Because we’ve already used one choice in the first position. The third position, 8 choices. The fourth position, 7 choices. Altogether we have 10 x 9 x 8 x 7 choices.

If we generalize the above procedure it becomes like this:

For a special case, 0! = 1.

3. Combinations

For a set S, its k-combination is a subset of S of size k. The number of k-combination of an n-element set is denoted by . Read “n choose k”.

Why is that? We can see some relations between permutation and combination. The formula of combination is in fact permutation divided by k!. We can try to think it this way. First we do k-permutation to get a number. K-combination must be smaller than this number. The question is smaller by what degree? Notice that each subset is counted k! times. Thus we divide the number by k! to get rid of redundancy.

Let’s look at a concrete example to enhance our understanding. We have 3 numbers {1,2,3}. Two-permutation will be 3 x 2 = 6. Let’s list them all together.

{1,2} {1,3} {2,3}
{2,1} {3,1} {3,2}

If we think of it as an rectangle, the width is “n choose k”, the height is k!, and the whole rectangle is k-permutation. To get “n choose k” we just need to divide k-permutation by k!.

4. Combination with repetition

The number of combinations of size k of n objects with repetition is equal to

This is trickier than previous ones. We have n types of objects. We can use n-1 delimiters to separate them into different groups. Thus the question becomes how to choose n-1 delimiters in k+(n-1) elements.

This shed light on the solution of combinatorics problems. The most important thing is to understand the problem and choose a proper angle. If the angle is right, you’ll solve the problem in no time.