Permutation & Combination
This page provides an introduction to Permutation and Combination.
Overview
Permutations and combinations are fundamental concepts in combinatorics, a branch of mathematics that deals with counting and arranging objects. These concepts are used to solve problems related to arranging, selecting, or counting items in various ways.
There are two basic principles of counting
Multiplication Principle
It is used to determine the total number of possible outcomes when two or more independent events or choices are considered together. If there are ways to do one thing and ways to do another thing independently, then there are ways to do both things together.
Example 1
Total number of ways of attempting a question paper containting True/False type questions(Every question should be answered).
Solution
Each question can be answered either True/False. That means there are two ways to answer each question, so total ways is
Example 2
Total number of ways of posting letters in letter boxes.
Solution
Every letter can be placed into one of the available letter boxes. That means each letter has distinct choices for its destination, resulting in a total of possible ways.
Example 3
Total number of ways in which person can occupy chairs.
Solution
Number of ways of arranging different items in a line . As each chair is occupied, the number of available options decreases starting from the initial count of people.
So answer is: .
Example 4
If you have locks and corresponding keys, then find maximum number of attempts required to open all the locks.
Solution
For each lock we can do maximum of attempts, So maximum number attempts will be .
Example 5
Given digits count all possible digit numbers when Repetition of digits is allowed and when Repetition of digits is not allowed.
Solution
When repetition of digits is allowed, You have choices for each of the positions in the -digit number, so answer will be
When repetition of digits is not allowed, You have choices for the first position. After you've chosen one digit for the first position, you have choices left for the second position, then choices for the third position, choices for the fourth position, and choice for the fifth position, so answer will be .
Example 6
Given digits count all possible digit numbers when Repetition of digits is allowed and when Repetition of digits is not allowed.
Solution
When repetition of digits is allowed, For each of the four positions in the -digit number, you can select from a set of choices . However, for the first position, you have choices .
So answer will be .
When repetition of digits is not allowed, You have choices for the first position. After you've chosen one digit for the first position, you have choices left for the second position, then choices for the third position, choices for the fourth position, and choice for the fifth position.
So answer will be .
Example 7
Given digits count all possible digit odd numbers when repetition of digit is NOT allowed.
Solution
In order for the number to be odd, the last digit must be either or . Therefore, the fifth position has different choices.
The first position has different choices, which can be either or . After selecting the first and fifth positions, you have choices left for the second position, different choices left for the third position, and only choice for the fourth position.
So answer will be .
Addition Principle
It is used to determine the total number of possible outcomes when you have mutually exclusive or disjoint events. If there are ways to do one thing and ways to do another thing, and these events are mutually exclusive (meaning they cannot happen at the same time), then the total number of ways to do either one of them is .
Example 1
In a hall, there are a total of individuals gathered for an event. What is the total number of possible handshakes among them?
Solution
- The first person shakes hands with others.
- The second person shakes hands with others (skipping the first person).
- The third person shakes hands with others (skipping the first and second persons)
This pattern continues until the tenth person shakes hands with other person, So to calculate the total number of handshakes, you can sum up the individual handshakes for each person.
So answer is:
Permutation
Permutation involves first selection and then arrangement. Number of ways to arrange a permutation of items from set of different items is denoted by .
Arrangement of Non-Unique Items
- Number of arrangements of (taken all at a time)
- Number of arrangements of (taken all at a time)
- Number of arrangements of (taken all at a time)
Restricted Arrangement
Arrangement with some condition.
Example 1
If all the letters of the word are to be arranged then find number of words(s):
- Starting with
- Start and end with vowel
- Relative order of vowel remains the same
- Vowels occupy even places
Solution
Let's first count total number of each letters,
, , , , , ,
Starting with
If is fixed at position, there will be remaining positions. Remaining letters can be arranged on differnt position in ways.
Since word has duplicate letter, arragment of all such letter should be removed.
So total number of words starting with will be
Start and End with Vowel
There are total () vowels in world , so there are cases possible as below.
Case I: Starts with and ends with .
Case II: Starts with and ends with .
Case III: Starts with and ends with .
Case IV: Starts with and ends with .
Case V: Starts with and ends with .
Case VI: Starts with and ends with .
Case VII: Starts with and ends with .
So total number of words that starts and ends with vowel is addition of all of the above cases.
Relative Order of Vowel Remains the Same
Relative order means, position , , should still be occupied by vowels as they are occupied by vowels in given word .
Let's first write down vowels and consonants list. Vowels are , , and consonants are , , , .
vowels can be arragned on position in ways out of which vowels are repeating so there are ways.
Similarly, consonants can be arranged amoung themself in ways.
So total number of words where relative order of vowel remains the same will be:
Vowels Occupy Even Places
There are total even position in word and total vowels, so any position can selected in ways. Also, vowels can be arranged among themself in ways of which are same so vowels can be arranged in ways.
So total number of ways to arrange vowels in even position is .
Now, all the remaining position will be occupied by consonants, so total number of ways consonants will be placed in remaining position with arragement among themself is .
So total number of words where vowels occupy even places will be:
Rank of Word
Find the rank of a word if the letters of the word are permuted and are arranged in an alphabetical order as in an English dictionary.
In the dictionary, the words appearing first will begin with , then , then , then , then and at last .
Let us fix the first position as , remaining places above can be filled with letters in ways.
Similarly, fixing the first letter as , the remaining places can be filled with letters in ways.
Now, there are letters() come before in the alphabet, so there must be words with a lower alphabetical rank.
Based on that let's calculate table below:
Alphbet | Rank of Alphabet | Rank less than itself to right of it | Factorial in decending order |
---|---|---|---|
S | 6 | 5 | 5! |
A | 1 | 0 | 4! |
C | 2 | 0 | 3! |
H | 3 | 0 | 2! |
I | 4 | 0 | 1! |
N | 5 | 0 | 0 |
So, rank of word is multiplication of last two columns .
GAP Method
Gap method is used when some objects or things are to be kept seperated.
Example 1
Number of arragements of all letters of words such that no two consonants appears together.
Solution
There are consonents and vowels .
To ensure that the consonants are separated, we'll start by arranging the vowels, which creates empty spaces between them. From these spaces, we can then select locations in different ways.
Additionally, vowels can be arranged among themselves in ways and consonents can be arranged among themseleve in ways.
So total number of arragements will be: .
Tie Method
Tie method is used when some objects or things are to be kept together.
Example 1
Number of arragements of all the letters of words such that all vowels should apprear together.
Solution
There are consonents and vowels .
To keep the vowels together we first arrange the consonents which will create empty places for vowels to choose from, which can be done in ways. In addition to that consonents and vowels can arrange among themself in and different ways.
So total number of words such that all vowels appears together will be: .
Circular Permutation
Number of ways in which different things can be arranged on circle is .
Number of ways in which different things can be arranged on circle when clockwise and anticlockwise arrangement are considered as same is .
Combination
Combination involves only selection. Number of ways of selecting items from set of different items is denoted by .
Example 1
There are two urns. Urn has distinct red balls and urn has distinct blue balls. From each urn balls are taken out at random. Count the number of ways in which this can be done.
Solution
- balls can be drawn from Urn in ways.
- balls can be drawn from Urn in ways.
So total number of ways = *
Example 2
A Committee of members is to be formed from males and females. calculate number of ways the committee is formed with at least males.
Solution
Here question is asking for at least males, that means committee can have , or all males.
- Ways for selecting of males ∗ Ways for selecting of females +
- Ways for selecting of males ∗ Ways for selecting of females +
- Ways for selecting of males ∗ Ways for selecting of females.
So total number of ways
Example 3
Total points are there, out of which are collinear, then find total number of different straight lines that can be formed by joinning these points.
Solution
To determine the count of straight lines, we need to choose two points from the following possible cases.
Case I: Selecting both points from half circle.
Case II: One point from half circle and one point from line.
Case III: Both points from line.
So total number of ways .
Example 4
There are straight lines, circles and parabola are present, then find maximum number of intersection possible.
Solution
Here question is asking for maximum number of intersections possible, so we should think of all the possible intersection.
Line to Line intersection: lines can give us maximum of intersection point.
Line to Circle intersection: line and circle can give us maximum of intersection points.
Line to Parabola intersection: line and parabola can give us maximum of intersection points.
Circle to Circle intersection: circles can give us maximum of intersection points.
Circle to Parabola intersection: circle and parabola can give us maximum of intersection points
Parabola to Parabola intersection: parabola can give us maximum of intersection point.
So total number of intersections will be addition of all of the above cases.
Example 5
Count total possible squares and rectangles in a given arragment.
Solution
To count all rectagles, we select any vertical lines from given vertical lines and select any horizontal lines from given horizontal lines. So total number of rectangles .
To count all squares, we need to consider following cases:
- Total squares of unit
- Total squares of unit
- Total squares of unit
- Total squares of unit
- Total squares of unit
- Total squares of unit
So total number of squares
Restricted Selection
Selection with some condition.
Example 1
boys are selected out of boys such that two particular boys will NOT server together.
Solution
Let's say two particular boys are boy and boy , following cases are possible if two particular boys will NOT server together.
Case I : Boy will be selected and Boy will not be selected.
Case II : Boy will not be selected and Boy will be selected.
Case III: Boy will not be and selected Boy will not be selected
So total number of ways will be
Example 2
boys are selected out of boys such that two particular boys will always server together.
Solution
Let's say two specific boys are boy and boy , following cases are possible if two particular boys will always server together.
Case I: Boy will be selected and Boy will be selected
Case II: Boy will not be selected and Boy will not be selected
So total number of ways will be: .
Selections of Unique & Non-Unique Items
N Non-Unique things | N Unique things |
---|---|
Number of ways of selecting zero things | Number of ways of selecting zero things |
Number of ways of selecting one things | Number of ways of selecting one things |
Number of ways of selecting two things | Number of ways of selecting two things |
... | |
Number of ways of selecting all things | Number of ways of selecting all things |
Total possible selection | Total possible selection = |
Example 1
Assuming the balls to be identical except for different in colors, calculate the number of ways in which one or more balls can be selected from white, green and black balls.
Solution
Total number of ways to select one or more balls from white, green and black balls will be:
(select or more balls from white balls) (select or more balls from green balls) (select or more balls from black balls) .
By applying the formula to choose things from identical items we get ways for white ball, ways for green ball and ways for black ball.
We subtract to exclude the scenario where we choose zero balls from the white, green, and black sets, as we require at least one ball.
So total number of ways will be .
Divisor
If number can be divided into prime factor as then total number of divisor will be:
Proof
Imagine you have a bag containing identical objects, and you want to determine all possible selections of objects. Applying the formula for all possible selections on identical objects you get . Similarly for , , and .
Hence proved that, total number of divisor will be:
To get total number of proper divisor, you subtract from above equation, as proper divisors are those that do not include and the number itself.
Example 1
Calculate total number of unique ways to express as product of two factors.
Solution
There are divisors for and those are and , now if we choose those divisor as a first factor we get:
Here, the combinations of the last two products are identical to those of the first two products, so there are only unique ways.
You can calculate unique ways to express as product of two factors, when is a perfect square using formula below:
So number of unique ways to express as product of two factors will be .
Example 2
Calculate total number of unique ways to express as product of two factors.
Solution
There are divisors for and those are and , now if we choose those divisor as a first factor we get:
Here, the combinations of the last three products are identical to those of the first three products, so there are only unique ways.
You can also calculate unique ways to express as product of two factors, when is NOT a perfect square using formula below:
So number of unique ways to express as product of two factors will be .
Division into Group
Below is an example of dividing different items into group when group size are different.
Example 1
Divide different things into group size of , and .
Solution
For the group of size , you have choices for the first item and choices for the second item. However, since the order within the group doesn't matter (i.e., choosing and then is the same as choosing and then ), you need to divide by (the number of ways to arrange items within a group).
So for the first group, we have:
For the group of size , you have choices for the first item, choices for the second item, and choices for the third item. Again, you need to divide by (the number of ways to arrange items within a group).
So for the second group, we have:
Similarly, for the group of size , you have choices for the first item, choices for the second item, choices for the third item, and choice for the fourth item. Once more, you need to divide by (the number of ways to arrange items within a group).
So for the third group, we have:
Total number of ways to divide different things into group size of , and will be:
Below is an example of dividing items into group when group size are same.
Example 2
Divide different things into group size of , , , .
Solution
For the group of size , you have choices because each item can be its own group.
For the first group of size , you have choices for the first item and choices for the second item. However, since the order within the group doesn't matter, you need to divide by (the number of ways to arrange items within a group).
So for the first group of size , we have:
For the second group of size , you have choices for the first item and choices for the second item. Again, you need to divide by (the number of ways to arrange items within a group).
So for the second group of size 2, we have:
Similarly, for the third group of size , you have choices for the first item and choice for the second item. Once more, you need to divide by (the number of ways to arrange items within a group).
So for the third group of size , we have:
Additionally, because we have three groups, each with a size of , we also divide by . So total number of ways to divide different things into group size of , , , will be:
Distribution of Different Object
Below are some of the examples of dividing different items into group when group size is not provided.
Example 1
Distribute different things across different children such that every child get at least one.
Solution
First let's divide different things into groups of .
Case I: Number of ways to divide different things into a group of will be:
Case II: Number of ways to divide different things into a group of will be:
Case III: Number of ways to divide different things into a group of will be:
In addition to that total number of ways to distribute these group amoung three children is .
So total number of ways to distribute different things across different children such that every child get at least one will be:
Distribute of Identical Object
Below are some of the examples of dividing identical items into group when group size is not provided.
Example 1
Total number of ways of distributing identical objects among persons, when zero distribution is allowed.
Solution
To distribute identical objects into person we will need sticks.
O O O O O | |
Now, we can arrange all 7 objects among each other in 7! ways. However, since there are 5 identical things, we need to divide by 5! to account for the repeated arrangements. Additionally, there are 2 identical sticks, so we must also divide by 2!.
So total number of ways will be:
Example 2
Total number of ways of distributing identical objects among persons, such that each gets at least .
Solution
identical objects will create total of empty spaces around them as represented by underscore(_) below:
O _ O _ O _ O _ O
Here we are not putting underscore(_) at the begining and at the end of the identical objects, because as per the problem we want each person to get at least object.
Since we want to distribute objects among people, we need to choose spaces from the empty spaces(_), so total number of ways are .
Integral Solution of Equation
Below are some of the examples of solving Integral equation.
Example 1
Given equation , calculate number of solutions if i.e. .
Solution
Think of it as dividing identical objects into different children when zero distribution is not allowed. Let's say and distribution will look like below:
O _ O _ O _ O _ O
Formula for calculating number of ways to distribute identical objects into different people is below:
Example 2
Given equation , calculate number of solutions if i.e. .
Solution
Think of it as dividing identical objects into different people when zero distribution is allowed. Let's say and distribution will look like below:
O O O O O | |
Formula for calculating number of ways to distribute identical objects into different children is below:
Example 3
, calculate number of solutions.
Solution
Think of this problem as distributing identical objects into groups, such that each group has zero or more objects.
O O O O O O O O O O O O O O O | | |
So total number of solutions for equations will be:
Example 4
, calculate number of solutions.
Solution
- Substract from right hand side to satisfy the condition for .
- Substract from right hand side to satisfy the condition for .
- Substract from right hand side to satisfy the condition for .
New equation after satisfying condition for and will be:
Now, think of this problem as distributing identical objects into groups, such that each group has zero or more objects.
O O O O O O O O O O | | |
So total number of solutions for equations will be:
Example 5
, calculate number of solutions.
Solution
To satisfy condition replacing with below values:
New equation after satisfying condition for and will be:
Now, think of this problem as distributing identical objects into groups, such that each group has zero or more objects.
O O O O O O | | |
So total number of solutions for equations will be:
Example 6
In how many ways boys and girls can sit together in a row such that between every boys there are at least girls.
Solution
Let's say we have arragement as below:
Now, we want at least girls between boys, so we can rewrite the equations as below:
Substract from right hand side to satisfy the condition for and , new equation after satisfying condition for and will be:
O O O O O O O O O O O | | |
In addition to that, girls and boys can be arranged among themself among in and ways.
So total number of solutions for equations will be:
Principle of Inclusion and Exclusion
Principle of Inclusion and Exclusion is a counting technique used to find the size of the union of several sets, especially when those sets may overlap.
Example
Number of arrangements of (taken all) such that neither nor pattern appears.
Solution
Total number of arragements of will be .
Now, to ensure that stays together, we apply the tie method, treating as a single unit. This reduces the total number of elements to as and . So total number of arragements of with pattern will be .
Similarly, total number of arragements of with pattern will be .
To get our answer, we can subtract the arrangements with the patterns and from the total arrangements. However, this approach would lead to removing arrangements that contain both patterns and twice, which is incorrect.
We need to account for this overlap to ensure an accurate result, so let's calculate the arrangements that contain both patterns and together. By applying the tie method again, we reduce the total number of elements to just and the combined pattern . This gives us a total of arrangements that simultaneously contain both patterns.
So total number of arragement which contains neither or will be:
Total arrangements - Arrangements with pattern - Arrangements with pattern + Arrangements with pattern and together.