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 n_1 ways, and for each of these alternatives, the second step can be done in n_2 ways, then the total number of ways the process can be made is n_1\cdot n_2.

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.

Motivation

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 n, the factorial of n, denoted by n!, is defined as the product of all strictly positive integers less than or equal to n. Mathematically, it is expressed as:

    \[n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1 \quad \text{for} \quad n \ge 1\]

  • The Zero Factorial Convention: By foundational mathematical definition, zero factorial is explicitly defined to equal exactly one:

        \[0! = 1\]

    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:

        \[n! = n \times (n-1)!\]

Let us see an example.

Example: Evaluate the exact value of 5! using the product definition of factorials. Then, use the recursive property to express 6! in terms of your answer.

Here is what the expression n! represents more clearly:

Claim (Combinatorial Meaning of n!): Let n be a positive integer. The factorial n! represents the total number of unique ways to arrange or permute a collection of n distinct objects into a linear sequence without repetition.

Here is a scenario where we use n! intuitively:

Example: How many unique five-letter words can be created using each of the letters A, B, C, D, and E exactly once?

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 4! 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: \frac{4!}{2!}=12. We divide by 2! 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 n total letters contain elements that are not all distinct. If there are n_1 identical letters of type 1, n_2 identical letters of type 2, \dots, and n_k identical letters of type k, such that n_1 + n_2 + \dots + n_k = n, then the total number of unique linear arrangements (words) that can be created is given by:

    \[\text{Total Unique Permutations} = \frac{n!}{n_1! \times n_2! \times \dots \times n_k!}\]

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.

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 26^8 in total. Explained generally:

Claim (Permutations with Repetition / Arrangements with Replacement): Let a set contain n distinct objects. The total number of unique sequences (words) of length k that can be formed by selecting objects from this set, where any object can be repeated any number of times, is exactly equal to:

    \[\text{Total Permutations with Repetition} = n^k\]

Example: A standard mobile banking security system requires users to create a 4-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.

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?

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 5 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 3-letter code. If each character slot can be filled by any letter from the standard 26-letter alphabet and letters can be repeated without restriction, how many unique labels are possible?
3.
A security system generates a temporary 5-character computer password. Each character can be chosen from a pool of 36 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:

    \[\frac{95!}{94! + 93!}\]

2.
Simplify the numerical expression:

    \[\frac{10! - 9!}{8!}\]

3.
Simplify the general algebraic variable expression for n \ge 2:

    \[\frac{n! + (n-1)!}{(n-2)!}\]

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?
error: Content is protected!