Combinatorics and countingProduct ruleGeneral product ruleCounting subsetsCounting functionsNumber of functionsInclusion-exclusion principleGeneralized pigeonhole principleTheoremProofSolutionPermutations-permutationsCombinationsBinomial theorem-combinations with repetitionSummaryUseful example questions

Combinatorics and counting

Product rule

If and are finite sets, then .

Proof: Obvious, but prove with induction on .

General product rule

If are finite sets, then

Proof: Induction on , using the basic product rule.

Counting subsets

A finite set, , has distinct subsets.

Proof: Suppose . There is a one-to-one correspondence (bijection), between subsets of and bit strings of length . The bit string of length we associate with a subset has a in position if , and in position if , for all .

By the product rule, there are such bit strings.

Counting functions

Number of functions

For all finite sets and , the number of distinct functions, , mapping to is:

Proof: Suppose . There is a one-to-one correspondence between functions and strings (sequences) of length over an alphabet of size .

By the product rule, there are such strings of length .

Inclusion-exclusion principle

For any finite sets and (not necesarily disjoint):

Generalized pigeonhole principle

Theorem

If objects are placed in boxes, then at least one box contains at least objects.

Proof

Suppose no box has more than objects. Sum up the number of objects in the boxes. It is at most

Thus, there must be fewer than . Contradiction.

E.g. "At least students in this course were born in the same month"

Suppose the number of students registered for the course is .

What is the maximum number for which it is certain that the statement is true?

Solution

Since we are assuming there are registered students, , so by GPP we know that the statement is true for .

Permutations

A permutation of a set is an ordered arrangement of the elements of . i.e. A sequence containing every element of exactly once.

-permutations

A -permutation of a set is an ordered arrangement of distinct elements of .

If we have a set of size , the number of -permutations of the -set are the different ordered arrangements of a -element subset of the set with elements. This is given by:

E.g. how many ways can first and second place be awarded to 10 people?

Here, we have and .

Order does matter in this case, because someone coming first and another person coming second is not the same, the other way round.

Therefore, we have to find the -permutations of elements.

Combinations

A -element combination of the set with elements is a -element subset, in which the elements are not ordered. The number of -element combinations of the set with elements is given by:

E.g. How many different 5-card poker hands can be dealt from a deck of cards?

E.g. How many different 47-card poker hands can be dealt from a deck of cards?

Binomial theorem

-combinations with repetition

To choose elements with repetition allowed from a set of size , we can do this in the following number of ways:

E.g. How many different solutions in non-negative integers , and does the following equation have?

Solution: We have to place pebbles into three different bins , and .

This is the equivalent to choosing an -combination (with repetition) from a set of size , so the answer is:

Summary

TypeRepetition allowed?Formula
-permutationsNo
-combinationsNo
-permutationsYes
-combinationsYes

Useful example questions

Question: How many solutions are there to the equation  where () is a non-negative integer, such that for .

Answer: Let for . Then, we obtain

Where is now a non-negative number for . The number of solutions to this equation can now be reduced to solving a typical stars and bars problem:


Question: How many solutions are there to the equation  where () is a non-negative integer, such that .

Answer: If is fixed, then the number of solutions for the other variables is:

Since the solutions are in one-to-one correspondence with the reorderings of stars and bars.

The possible values for are and hence, the answer is:


Give a formula for the coefficient of in the expansion of , where is an integer.

Answer: We know that:

Coefficient of in the expansion of is .

Formula for the coefficient of in the expansion of is .


Give a formula for the coefficient of in the expansion of where is an integer.

Answer: A general term in this expression is of form:

For all integers such that . Rearranging for gives: .

The coefficient is   .