World of Combinatorics: Counting, Permutations, and Combinations
In the world of Combinatorics, an important aspect of the probability theory is being able to determine the total number of possible outcomes when multiple events are performed.
Combinatorics is a branch of mathematics that focuses on counting. It has many applications in other areas of mathematics, including graph theory, coding and cryptography, and probability. Combinatorics has applications in optimization, computer science, and statistical physics.
The Counting Principle
The Fundamental Counting Principle also known as the multiplication rule of counting, states that, if one event has m possible outcome and event 2 has n possible outcomes, then there m.n total possible outcomes for the two events together.
If there are m ways to do one thing and n ways to do another, then there are m*n ways of doing both, together.
The counting principle is said to involve outcomes with different categories similar to that of a tree diagram.
A tree diagram gives you a visual representation of the solution.
When calculating few outcomes, the use of tables, lists, and tree diagrams, may be feasible. When you have a large number of outcomes or data sets to determine, it no longer becomes practical to use the above methods to unearth the different possibilities. It becomes imperative to adopt the fundamental counting principle.
To put all this into perspective, let us assume, we can perform a task in m1 ways, and for each of these a second task can be performed in m2 ways, and for each of the latter a third task can be performed in m3 ways, β¦, and for each of the latter we can conclude based on the pattern that an nth task can be performed in mn ways. The entire sequence of n tasks can be therefore be performed in m1 β’ m2β’ m3β’ β¦ β’ mn ways.
How to solve a counting problem through permutations and combinations.
The use of permutations and combinations to solve a counting problem can at first be daunting and confusing. But before we jump into all that, let us first understand the factorial algorithm.
What is a factorial?
Factorial is a mathematical function just like square roots, addition, multiplication, represented by a ! symbol. It multiplies a number by every number below it. The numbers all positive integers, including 0.
In terms of application, the function used to find the number of ways βnβ objects can be arranged. n being the set or population.
In mathematics, the Factorial of n is indicated as n!. This means that there are n! ways to arrange n objects in sequence. n! gives the number of ways in which n objects can be permuted.
Therefore, 5 factorial (5!) is 5*4*3*2*1 = 120
We needed to know about factorial because they are used in permutation and combinations. So letβs now get to the fun bit.
Permutations vs Combinations
Letβs start with Permutations. What a fancy word, heh! Anyway, on a serious note. A permutation is defined as an arrangement of items in which the order matters. It represents the number of ways you can choose r objects from n possibilities where the order of selection matters.
Permutations asks, what are all possible ways of doing something?
For example; given the letters ABC. The Permutations will be as follows:
Permutations can be carried out in two ways:
β Permutations with Repetition
β Permutations without Repetition
Letβs look at the different scenarios:
Permutations where repetion is allowed:
We already know that in the permutations, the order of items is important. Permutations with repetition mean we can select one item twice and the order still matters.
Where n is the number of things to choose from, and you choose r of them. Notation for this concept is:
This means you can re-use the same element within the order, such as in your phoneβs password lock your code could be β7777β or β5488β.
Example 1: A lock has a 5 digit code. Each digit is chosen from 0β9, and a digit can be repeated. How many different codes can you have?
Example 2: How many 3 letter words can be formed using the letters ABC allowing for repetition of the letters?
Solution:
For this problem, 3 locations are needed:
_____ β’ _____ β’ _____
3 letters can be used to fill the first location. Because repetition is allowed, the same 3 letters can be used to fill the second location and also the last location.
__3___ β’ __3___ β’ __3___ = 27 arrangements
Permutations without repetition
In this scenario, each element can only appear once in order. For example, on password locks in some premises, each number can only be used once. Similarly, when youβre electing an official, each slot needs to be given to a different person i.e President, Vice President, Secretary, etc.
Where n is the number of things to choose from, and you choose r of them. Notation for this concept is:
In permutations without repetition, our choices get reduced each time.
Example: How many ways can you order 3 out of 16 different billiard balls?
We are not choosing all of them, just 3 of them. Therefore:
A permutation is, therefore, an ordered selection of r items from a set of n items where repetition may be allowed or not.
A combination is the selection of items in which order does not matter. Combinations represent the number of ways you can choose r objects from n possibilities where the order of section does not matter.
Like permutation, the combination is of two type
β Combinations with Repetition
β Combinations without Repetition
Example: In a fruit salad made up of 3 fruits, melons, mangoes, and bananas, when cut up and mixed, the fruit salad will look and taste the same regardless of the order in which the 3 fruits are selected, cut, and mixed. In this case when the order does NOT matter it is a combination.
Combinations with repetition
When repetition is allowed: C is a combination of n elements in a set A, taking r elements at a time from this set (order is not important) with repetition. Each element can be selected multiple times.
We define C as:
Where n is the number of things to choose from, and you choose r of them.
For example, if there are 5 flavors of ice cream and you can have 3 scoops of ice cream (vanilla, chocolate, strawberry). How many combinations/variations can you have? You can repeat flavors.
Example selections would be:
- {c, c, c} (3 scoops of chocolate)
- {v, c, s} (one each of vanilla, chocolate, and strawberry)
- {v, s, s} (one of vanilla, two of strawberry)
Based on the example, our answer would be:
Combinations without repetition
When repetition is not allowed: C is a combination of n distinct things taking r at a time (order is not important).
We define C as:
Where n is the number of things to choose from, and you choose r of them
Example: The state lottery chooses 6 different numbers between 1 and 50 to determine the winning numbers. How many combinations are possible?
The relation between Permutation and Combination
The difference between a Permutations and Combinations
Read more:
Resources:
Phew, I know right! That seems to be a lot to take in. The best way to go about all this is to reason through the problem before solving it, using the formula.
Alright, there you go! A quick recap in the world of combinatorics. I hope this has been helpful and informative. If you like the article, please do give it a clap. Feel free to connect with me on LinkedIn.
