COMBINATORICS

Combinatorics is a branch of mathematics concerned with counting, arranging, and organizing objects or elements according to specified rules or constraints. It deals with the study of finite or discrete structures and explores various methods for counting and analyzing combinations and permutations of objects.

When order matters, it means the ordering of objects is significant. For example, a password such as 1234 is different from 4321.

If order does not matter, then the ordering of objects is insignificant. For example, choosing students A, B, and C, for a team, is the same as choosing them in any other order ( BCA, or CAB...etc)

Example 1: ordered and no repetition - You are creating a password for your new computer account. The password must consist of 4 characters, each chosen from the 10 digits (0 through 9). However, you cannot repeat any digit within the password. How many different passwords can you create?

Answer: Following the ordered and no repetition formula: n!/(n-k)!. 10!/6! = 5040

Explanation: n! = 10! = the number of ways to arrange the 10 digits.

(n-k)! = 6! = the number of ways to arrange the last 6 digits.

We divide 10!/6! because we have 10 choices for the first pick, 9 choices for the second pick, 8 choices for the 3rd pick, and 7 choices for the 4th pick.

Example 2: ordered and repetition - You are creating a 3-digit lock combination for your suitcase. Each digit in the combination can be any number from 0 to 9, and repetition of digits is allowed. How many different lock combinations can you create?

Answer: Following the ordered and repetition formula: n^k. 10^3 = 1000

Explanation: There are 10 different choices for your first, second, and third picks since repetition is allowed.

Example 3: Unordered and no repetition - You are choosing 3 colors from 7 to form a pattern . How many ways can you do this if the order of the colors chosen do not matter and there is no repetition allowed?

Answer: Follow the ordered and repetition formula: nCk. 7C3 = 7!/(3!(7-3)!) = 35

Explanation: Notice that this format n!/(k!(n-k!)) is similar to the permutation equation, except for its division by k!. Similarly, n! = the number of ways to arrange n objects. By diving by (n-k)!, we limit the equation to only arrange k objects. Next, dividing by k! is done to eliminate combinations that share the same elements, For example, choosing red, blue, and green is the same as choosing blue, red, and green. k! = the number of ways to arrange k objects.

Example 4: Unordered and repetition allowed - You're planning a party and want to bake a cake for your guests. You have five different add-ins: strawberries, nutella, honey, blueberries and bananas. Each layer can have any combination of add-ins, and add-ins can be repeated. However, the order in which the toppings are added to the pizza does not matter. How many different cakes can you make, if you only use 3 add-ins?

Answer: Following the unordered and repetition formula: (n+k-1)Ck. (3 + 5 - 1)C3 = 35

Explanation: Since we allow repetition of add-ins, we use n+k-1 instead of just n. We now use (n+k-1)Ck the combinations equation to find the number of ways to choose k objects from n+k-1.

Practice Questions