Combinations and Permutations

A simple example with five balls and clear graphics to explain the formulas for combinations and permutations, with and without repetition.

1. How many ways can you arrange 5 balls? (Full Permutations)

1. Red ball: You can place it in any of the 5 available spots.
   
   
   
   
   
2. Green ball: For each position of the red ball, there are 4 remaining spots where you can place the green ball.
   
   
   
   
   
   But why only 4? If you tried to put the green ball in the first position and the red ball in the second, that specific arrangement has already been accounted for in the previous step.
   For example, the following arrangement:
   
   was already covered when we calculated all the possibilities for the red ball in the second position (Section 1):
   
   
3. Blue ball: Since the red and green balls are already set, you have 3 remaining spots to choose from.
4. Yellow ball: With three spots taken, you only have 2 spots left.
5. Grey ball: By the time you reach the final ball, there is only 1 spot remaining.

The Final Calculation

To find the total number of possible arrangements, we multiply the number of choices for each step together:

5 × 4 × 3 × 2 × 1 = 120

In mathematics, this shorthand is called a factorial, and it is written with an exclamation mark: 5!

Now, let’s change the goal. Instead of arranging all five balls, what if we only want to choose 3 of them to put on a shelf?

2. How many ways can you pick 3 balls from 5 balls when order is matters? (Partial Permutations)

1. First Choice: You start with 5 balls available, so you have 5 options for the first spot.
2. Second Choice: Since one ball is already picked, you have 4 balls left to choose from.
3. Third Choice: Now you have 3 balls remaining to fill the final spot.

The Formula

To calculate this, we multiply the choices for the spots we want to fill:

5 × 4 × 3 = 60

In mathematics, this shorthand is written using factorials to "cancel out" the spots we didn't use (the 2 balls left over, which can be arranged in 2! ways):

Permutations =	5!	=	5!	= 60
	(5-3)!		2!

Another way to explain the formula is this: When we count the 120 (5!) total permutations of five balls, we are including the order of the remaining two balls (yellow and grey). However, if we only care about the first 3 balls (red, green, and blue), then the following 2! permutations:


Both 'collapse' into one permutation:

This formula, uses 2! to remove the 2 × 1 that we don't need, leaving us with just 5 × 4 × 3.
Please notice that this is a specific case because 2 is equal to 2!.
To see the difference more clearly: if we choose 3 balls from a set of 7, we would divide the 7! permutations by 4! (1 × 2 × 3 × 4), which equals 24. This removes the unnecessary arrangements and leaves us with just 7 × 6 × 5.
$\frac{7!}{4!}=\frac{7\times 6\times 5\times \cancel{4\times 3\times 2\times 1}}{\cancel{4\times 3\times 2\times 1}}=7\times 6\times 5$

Now, let’s imagine a different scenario. What if we are just picking 3 balls to put in a bag? In this case, picking Red-Green-Blue is the exact same thing as picking Blue-Red-Green.

3. How many ways can you pick 3 balls from 5 when the order doesn't matter? (Combinations)

1. Start with our previous total: From the last step, we know there are 60 ways to pick and arrange 3 balls.
2. Identify the duplicates: For any 3 balls you pick, there are 3! (3 × 2 × 1 = 6) different ways to arrange them.
3. Remove the order: Since we don't care about the arrangement, we divide our total by those 6 duplicates.

60 ÷ 6 = 10

For example, the following 6 permutations 'collapse' into one combination:

The Final Formula

In mathematics, this is the true definition of a Combination. We take our previous formula and add one more "cancel out" step for the arrangements of the picked balls (3!):

Combinations =	5!	= 10
	(5-3)! × 3!

This formula cancels out the 2! balls we didn't use, AND the 3! ways the chosen balls could have been ordered.

Finally, let’s look at what happens if we can pick the same ball more than once. Imagine picking a ball, writing down its color, and then putting it back in the bag before picking the next one.

4. How many ways can you pick 3 balls from 5 when order matters and repetition is allowed? (Permutations with Repetition)

1. First Choice: You have 5 balls to choose from.
2. Second Choice: Since you put the first ball back, you still have 5 balls to choose from.
3. Third Choice: Again, you still have all 5 balls available.

The Calculation

Because the number of choices stays the same for every spot, the math becomes a simple power:

5 × 5 × 5 = 125

In mathematics, this shorthand is written as an exponent: 5³.

With repetition allowed, there are 125 possible ways to pick the balls, which is much higher than when we were removing them from the bag!

5. How many ways can you pick 3 balls from 5 when order doesn't matter and repetition is allowed? (Combinations with Repetition)

This time, we use a different method called Stars and Bars.

• The Stars (*): These represent the 3 balls you pick.
• The Bars (|): These represent the "walls" that separate the 5 different balls. Since there are 5 balls, we need 5 - 1 = 4 bars to separate them.

When you see two bars next to each other, it means no balls of that specific color were chosen.
For example, the selection Red-Red-Green is represented as:

** | * | | |

This means: 2 balls in the first section (Red), 1 ball in the second section (Green), and 0 balls in the others.

Total spots = 7: (3 balls + 4 bars). The problem now becomes: "How many ways can we choose 3 spots out of 7 to place our stars?"
Once the stars are placed, the bars must go in the remaining 4 spots.

Since the order of the stars doesn't matter, this is exactly like a Combination without Repetition problem. You simply need to choose 3 spots (our r) out of a new total of 7 spots (n' = 3 + 5 - 1 = 7).

$C_3=C_3=\frac{7\times 6\times 5}{3\times 2\times 1}=35$

Formulas

To get the formulas, replace 5 with n and 3 with r:

Name	Order Matters?	Repeats Allowed?	Formula
Permutation	Yes	No	$$P(n,r)=\frac{n!}{(n-r)!}$$
Combination	No	No	$$C(n,r)=\frac{n!}{r!(n-r)!}$$
Permutation (with Repetition)	Yes	Yes	$$n^r$$
Combination (with Repetition)	No	Yes	$$C(n+r-1,r)=\frac{(n+r-1)!}{r!(n-1)!}$$