Combinatorics is the branch of mathematics concerned with counting and arranging things. The central question is often: “How many different ways can I do this?”
One of the basic probabilistic formulas you have learned in S4 is that, when outcomes are all equally likely, the probability of an event happening is all the favourable outcomes divided by the total number of outcomes. Therefore, we have an interest in understanding how many possible ways there are for different scenarios.
For this topic to make sense, we will have an underlying principle/assumption working in the background: If a process consists of two steps, the first of which can be done in ways, and for each of these alternatives, the second step can be done in ways, then the total number of ways the process can be made is .
For example: If we have three different shirts and four different trousers, there are 12 different outfits we could select.
For this section, we will purposefully avoid using the word “choose” and discuss arrangements or selections instead.
Suppose you have 3 books: A,B,C. How many ways can you arrange them on a shelf? There are a total of 6 arrangements: ABC, ACB, BAC, BCA, CAB, and CBA.
How do we generalise this and how can we apply a general logic to such a problem? That is the goal of this part of the unit. We will develop a bit of notation and new operations and put them into the different contexts.
In this spirit, we will be interested in understanding how many objects we have to select, out of how many, whether we are allowed to repeat object in our selection or not, and whether the order in which we choose them matters.
When the order matters (e.g.: selecting a password),we will call this a permutation. When the order does not matter (e.g.: selecting people for a team), we will call this a combination.
The example above, with the books, is a permutation of three distinct objects.
Permutation of n Objects Without Repetition
We start by defining an operation that will be heavily used in all our cases.
Definition (Factorial): For any non-negative integer , the factorial of , denoted by , is defined as the product of all strictly positive integers less than or equal to . Mathematically, it is expressed as:
The Zero Factorial Convention: By foundational mathematical definition, zero factorial is explicitly defined to equal exactly one:
This convention ensures that algebraic formula systems for permutations, combinations, and power series expansions remain perfectly consistent without breaking down.
Recursive Property: A factorial can be uniquely characterized by its standard recursive functional relationship:
Let us see an example.
Example: Evaluate the exact value of using the product definition of factorials. Then, use the recursive property to express in terms of your answer.
Step 1: Apply the product definition to calculate
According to the core definition, is the product of all positive integers descending from down to :
Step 2: Compute the arithmetic steps sequentially
Multiply the integers step by step:
Step 3: Apply the recursive property to find
The recursive rule states that . For , we can isolate the sub-factorial product block directly:
Substitute our evaluated product result of into the expression:
Conclusion:
The exact values derived from the factorial definitions are:
Value of :
Value of :
Here is what the expression represents more clearly:
Claim (Combinatorial Meaning of ): Let be a positive integer. The factorial represents the total number of unique ways to arrange or permute a collection of distinct objects into a linear sequence without repetition.
Proof using the Fundamental Counting Principle (Multiplication Rule):
Suppose we have a set containing distinct objects, and we want to fill sequential positions in a straight linear arrangement:
We evaluate the number of available independent choices for each position step by step:
Position 1: There are exactly available objects to choose from. Once an object is selected and placed, it cannot be reused because repetition is strictly forbidden.
Position 2: Since one distinct item is already fixed in the first spot, there are exactly remaining candidate items available for this position.
Position 3: With two distinct objects now removed from the pool, there are exactly remaining items available to fill this spot.
Position (The Last Position): This process scales down sequentially until we reach the final slot. At this stage, items have already been allocated, leaving exactly final remaining object to place.
According to the Fundamental Counting Principle, if a compound operation can be broken down into successive independent choices, the total number of overall configurations is found by multiplying the number of options at each individual stage together:
By inspecting our algebraic axioms, we recognize that this exact descending product of integers from down to matches the formal definition of the factorial function:
This logically concludes the proof and maps the combinatorial claim perfectly.
Here is a scenario where we use intuitively:
Example: How many unique five-letter words can be created using each of the letters A, B, C, D, and E exactly once?
Step 1: Identify the problem type
We need to arrange a set of distinct letters into a sequence of positions where each letter is used exactly once. This is a classic permutation problem of unique objects without repetition.
Step 2: Apply the permutation claim formula
According to the linear permutation principle, the total number of unique ways to arrange distinct objects is given by . Substituting letters into the formula yields:
Step 3: Expand and calculate the arithmetic value
Apply the product definition of the factorial function to multiply the integers sequentially:
Conclusion:
Exactly different words can be created using the letters A, B, C, D, and E.
Permutations With Repeated Objects
Imagine the same example as above, except we have a repeated letter, so: A, B, C, and A. How many 4-letter words can we create? The answer is not because the A is a repeated letter. Instead, every time we swap the A’s around, we effectively have not changed our word. Therefore, we are counting too many times. The real answer is: . We divide by because this is the number of ways the A letters can be rearranged, and every time they can be rearranged we have counted an extra word which is not really there.
In short, we have:
Claim (Permutations with Repeated Objects / Multiset Permutations): Let a collection of total letters contain elements that are not all distinct. If there are identical letters of type 1, identical letters of type 2, , and identical letters of type , such that , then the total number of unique linear arrangements (words) that can be created is given by:
Proof using the Overcounting Correction Method:
Let be the unknown number of truly unique linear arrangements that can be formed by these letters. We want to solve for .
Suppose for a moment that we artificially force all letters to be completely distinct by attaching unique labels or subscripts to them. For example, if we had two ‘A’s, we would treat them as distinct elements and . According to the distinct linear permutation principle, the total number of ways to arrange these newly labeled items is exactly .
Now, let’s analyze how this unconstrained total of relates to our unique count by tracking the effect of erasing our artificial labels:
For any single unique arrangement out of our options, there are exactly letters of type 1. If we re-apply unique labels to just these type 1 elements, they can be internally scrambled in exactly distinct ways without changing the look of the rest of the word.
Similarly, the identical letters of type 2 can be internally permuted in ways once labeled.
This logic applies independently across every group up to type , which can be internally arranged in ways.
By applying the Fundamental Counting Principle, each single unique arrangement blows up into exactly duplicate variations when we add labels. Therefore, the total number of distinct labeled arrangements is given by:
Since factorial products are strictly positive and non-zero, we isolate our unique target value by dividing both sides by the overcounting multiplier:
This completes the algebraic verification and establishes the formula for permutations with repeated elements.
This looks more difficult than what it actually is. We check an example to make sure we understand how to use this.
Example: Determine the total number of unique eleven-letter words that can be created by rearranging all the letters from the word MISSISSIPPI.
Step 1: Count the total number of letters ()
Count the total frequency of letters available in the word MISSISSIPPI:
Step 2: Find the frequency of each repeated letter
Break down the word into individual letter groups to identify repetitions:
Letter M appears: time
Letter I appears: times
Letter S appears: times
Letter P appears: times
Check:, which matches our total count perfectly.
Step 3: Apply the multiset permutation formula
Substitute the total count and the duplicate frequencies into the repeated object permutation formula:
Step 4: Simplify the factorials and calculate the final value
Expand the numerator to cancel out the largest factorial group () in the denominator:
Simplify the numbers to speed up multiplication. Notice that (canceling the 8 in the numerator) and (canceling the 6 in the numerator):
Conclusion:
Exactly different unique words can be created using all the letters from MISSISSIPPI.
Permutations of n Objects With Repetition
What happens if the objects are different but we are allowed to repeat our selection? Then we keep the same number of objects with every selection. If we need to select an 8-character password, there are 26 letters in the alphabet, and we can repeat, then we have 26 possible selections per character So in total. Explained generally:
Claim (Permutations with Repetition / Arrangements with Replacement): Let a set contain distinct objects. The total number of unique sequences (words) of length that can be formed by selecting objects from this set, where any object can be repeated any number of times, is exactly equal to:
Proof using the Fundamental Counting Principle (Multiplication Rule):
Suppose we want to build an ordered sequence of length . This task can be broken down into filling independent, sequential positions from left to right:
We evaluate the number of available choices for each position step by step under the condition that repetition is fully allowed (replacement occurs after each choice):
Position 1: There are exactly distinct objects available in the pool to choose from.
Position 2: Because repetition is allowed, the object selected for the first position is placed back into the pool. Therefore, there are still exactly distinct objects available for this position.
Position 3: Following the same rule, the pool remains completely full. There are exactly independent options available for this spot.
Position : This pattern continues identically all the way to the final slot. For the -th position, there are still exactly choices.
According to the Fundamental Counting Principle, if a compound sequence of choices is made, the total number of unique outcomes is found by multiplying the number of options at each individual stage together. Since there are positions to fill and each position has choices, we multiply the value by itself exactly times:
By the algebraic laws of exponents, a number multiplied by itself times is expressed as a power function:
This logically concludes the proof and maps the combinatorial rule perfectly.
Example: A standard mobile banking security system requires users to create a -digit PIN number. Each digit must be selected from the numbers 0 through 9, and digits can be repeated any number of times. Find the total number of unique PINs that can be generated.
Step 1: Identify the pool size () and sequence length ()
The available pool of choices consists of the single-digit numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Counting these options gives:
The length of the required PIN sequence is exactly characters long:
Step 2: Apply the permutation with repetition formula
Because digits can be repeated without restriction (for instance, “1111” or “1221” are completely valid), we apply the exponential rule :
Step 3: Calculate the numerical value
Multiply the base integer by itself times according to the laws of exponents:
Conclusion:
There are exactly unique unique -digit PIN numbers that can be created.
We could have also said that there are 10,000 numbers if we count 0000 and until 9999. This is to show that a problem can have more than one solution.
Restrictions
Our final application for this page is the same type of examples we have been seen, except we start introducing restrictions and other rules. For example, creating a password without using the digit 1 or the character A.
To solve this problem, we go from most restrictive condition to least restrictive.
Example: How many unique five-letter words can be created using each of the letters A, B, C, D, and E exactly once such that the letter A is always in the second position, and the letter B is never in the last position?
Step 1: Analyze the strict positional constraints first
To solve constrained arrangement problems efficiently, always fill the most restricted positions first:
Second Position (Slot 2): Must always be the letter A. This leaves exactly choice.
Last Position (Slot 5): Cannot be the letter B. Since the letter A is already fixed in Slot 2, the last position can only be filled by the remaining unrestricted letters: C, D, or E. This leaves exactly choices.
Step 2: Fill the remaining unrestricted slots
Two letters have now been placed (A in Slot 2, and one of C, D, or E in Slot 5), leaving exactly letters unplaced from our initial five-letter set (which includes B and the two remaining letters from C, D, and E):
First Position (Slot 1): Can be filled by any of the remaining letters.
Third Position (Slot 3): Can be filled by any of the remaining letters.
Fourth Position (Slot 4): Can be filled by the final remaining letter.
Step 3: Apply the Fundamental Counting Principle
Multiply the number of independent choice possibilities across all 5 positions together to calculate the final value:
Diagram Visualisation:
Conclusion:
Exactly unique words can be formed under these placement constraints.
The diagram in the end can sometimes be an easier way to manage all these rules simultaneously.
Exercises
For each of the following three combinatorial scenarios, calculate the exact number of unique straight linear arrangements that can be formed.
1.
A security system passcode requires you to arrange the numbers 2, 4, 7, and 9 into a sequential code. If each number must be used exactly once, how many unique passcodes can be created?
2.
Six top-tier runners qualify for the finals of a short sprint. In how many unique ways can these six athletes finish in a ranking from first place to sixth place?
3.
An art gallery manager wants to hang seven completely unique paintings side-by-side on a central wall. How many unique horizontal arrangements can the manager choose from?
For each of the following three words, calculate the exact number of unique anagrams (words) that can be created by rearranging all of its letters. Apply the multiset permutation formula to account for repeated letters and simplify your final answer to an integer value.
1.
How many unique words can be created using all the letters from the word BANANA?
2.
How many unique words can be created using all the letters from the word COCONUT?
3.
How many unique words can be created using all the letters from the word BOOKKEEPER?
For each of the following three security and coding scenarios, calculate the total number of unique sequences that can be created.
1.
A high-security heavy padlock uses a rolling wheel code mechanism with dials. If each individual dial can only be turned to the numbers 1, 2, or 3, how many unique total padlock combinations can be configured?
2.
An automated system generates inventory labels consisting of a -letter code. If each character slot can be filled by any letter from the standard -letter alphabet and letters can be repeated without restriction, how many unique labels are possible?
3.
A security system generates a temporary -character computer password. Each character can be chosen from a pool of available alphanumeric options (the 10 single-digit numbers 0–9 along with the 26 lowercase letters a–z). If full character repetition is allowed, how many unique temporary passwords can be built?
For each of the following three rational expressions involving factorials, perform algebraic simplification by factoring out the lowest common factorial group. Evaluate your final answers down to an exact integer or a completely simplified fraction without using a calculator.
1.
Simplify the numerical expression:
2.
Simplify the numerical expression:
3.
Simplify the general algebraic variable expression for :
For each of the following three arrangement problems, calculate the number of arrangements, assuming each element can be used exactly once.
1.
How many unique five-letter words can be created using each of the letters P, Q, R, S, and T exactly once such that the letter P is always in the first position, and the letter Q is never in the third position?
2.
A four-digit passcode is created by arranging the numbers 1, 3, 5, and 7 without repetition. How many unique codes can be formed if the code must end with an odd number less than 4 (the number 1), and the number 7 cannot be placed in the first position?
3.
How many unique six-letter words can be constructed using each of the letters U, V, W, X, Y, and Z exactly once under the condition that the letter U must fill the last slot, and neither V nor W can be placed in the first slot?