Basic Combinatorics

Introduction to Combinatorics

Multiplication Principle

If there are m ways for event A to happen and n ways for event B to happen, then there are m*n ways for events A and B to happen.

Factorials

n! = n*(n-1)*(n-2)*...*3*2*1

Permutations

A permutation of a set of objects is a way of arranging the objects in a line. To count the number of permutations, we use the multiplication principle

Overcounting

• Sometimes it helps to overcount and then subtract or divide out the extras.

• For example, if I have a pile of ropes and I can't tell which rope is which, but I want to know how many, how could I do it?

• Count the ends. If there are 12 rope ends, how many ropes are there?

• 12/2 = 6

Combinations

• Combinations are used when we want to select a number of objects but we don't care about the order in which they are selected.

• For example, if I am choosing members of a committee or students for a class or winners of a raffle, I don't care what order in which the group is chosen in. I only care about who the members of the final group are.

• To calculate the number of ways we can choose these groups, we use combinations, which are an excellent example of overcounting.

Combinations

• Suppose I want to choose a group of 4 students from a class of 10. How could I do it?

• First choose 4 students our of the group of 10, where order DOES matter. How many ways can I do this?

• 10*9*8*7=5040

• Then divide by the number of orders that each group of 4 can be chosen. So what is our final answer?

•  $\frac{5040}{4\cdot3\cdot2\cdot1}=210$  

Combinations

• The general formula for how to choose r objects from a group of n objects where order doesn't matter is  $\ _nC_r=\frac{n!}{\left(n-r\right)!r!}$  

• We say this aloud as "n choose r"

• In our last example, we had 10 students and we chose 4, so  $\ _{10}C_4=\frac{10!}{6!4!}=\frac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1}=10\cdot3\cdot7=210$  

Challenge Questions