Skip to main content

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 n\text{n} ways to do one thing and m\text{m} ways to do another thing independently, then there are n * m\text{n * m} ways to do both things together.

Example 1

Total number of ways of attempting a question paper containting 1010 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 2102^{10}

Example 2

Total number of ways of posting 33 letters in 44 letter boxes.

Solution

Every letter can be placed into one of the 44 available letter boxes. That means each letter has 44 distinct choices for its destination, resulting in a total of 434^3 possible ways.

Example 3

Total number of ways in which 66 person can occupy 44 chairs.

Solution

Number of ways of arranging rr different items in a line =r! = \text{r}!. As each chair is occupied, the number of available options decreases starting from the initial count of 66 people.

So answer is: 6543=3606 * 5 * 4 * 3 = 360.

Example 4

If you have 1010 locks and 1010 corresponding keys, then find maximum number of attempts required to open all the locks.

Solution

For each lock we can do maximum of 1010 attempts, So maximum number attempts will be 1010=10010 * 10 = 100.

Example 5

Given digits 1,2,3,4,51,2,3,4,5 count all possible 55 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 55 choices (1,2,3,4,5)(1, 2, 3, 4, 5) for each of the 55 positions in the 55-digit number, so answer will be 555^5

When repetition of digits is not allowed, You have 55 choices for the first position. After you've chosen one digit for the first position, you have 44 choices left for the second position, then 33 choices for the third position, 22 choices for the fourth position, and 11 choice for the fifth position, so answer will be 5!5!.

Example 6

Given digits 0,1,2,3,40,1,2,3,4 count all possible 55 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 55-digit number, you can select from a set of 55 choices (0,1,2,3,4)(0, 1, 2, 3, 4). However, for the first position, you have 44 choices (1,2,3,4)(1, 2, 3, 4).

So answer will be 4544 * 5^4.

When repetition of digits is not allowed, You have 44 choices(1,2,3,4)(1,2,3,4) for the first position. After you've chosen one digit for the first position, you have 44 choices left for the second position, then 33 choices for the third position, 22 choices for the fourth position, and 11 choice for the fifth position.

So answer will be 44321=964 * 4 * 3 * 2 * 1 = 96.

Example 7

Given digits 0,1,2,3,40,1,2,3,4 count all possible 55 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 11 or 33. Therefore, the fifth position has 22 different choices.

The first position has 33 different choices, which can be either (1,2,4)(1, 2, 4) or (2,3,4)(2, 3, 4). After selecting the first and fifth positions, you have 33 choices left for the second position, 22 different choices left for the third position, and only 11 choice for the fourth position.

So answer will be 23321=362 * 3 * 3 * 2 * 1 = 36.

Addition Principle

It is used to determine the total number of possible outcomes when you have mutually exclusive or disjoint events. If there are n\text{n} ways to do one thing and m\text{m} 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 n + m\text{n + m}.

Example 1

In a hall, there are a total of 1111 individuals gathered for an event. What is the total number of possible handshakes among them?

Solution

  • The first person shakes hands with 1010 others.
  • The second person shakes hands with 99 others (skipping the first person).
  • The third person shakes hands with 88 others (skipping the first and second persons)

This pattern continues until the tenth person shakes hands with 11 other person, So to calculate the total number of handshakes, you can sum up the individual handshakes for each person.

So answer is: 10+9+8+7+6+5+4+3+2+1=10    11210 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = \large \frac {10 \ \ * \ \ 11}{2} =55= 55

Permutation

Permutation involves first selection and then arrangement. Number of ways to arrange a permutation of r\text{r} items from set of n\text{n} different items is denoted by == nPr^\text{n}\text{P}_\text{r}.

nPr=n!(n - r)!^\text{n}\text{P}_\text{r} = \frac{\text{n}!}{\text{(n - r)}!}

Arrangement of Non-Unique Items

  • Number of arrangements of A, B, C, D, E\text{A, B, C, D, E} (taken all at a time) =5!= 5!
  • Number of arrangements of A, A, A, B, C\text{A, A, A, B, C} (taken all at a time) =5!3!= \large \frac{5!}{3!}
  • Number of arrangements of A, A, A, B, B, C, C\text{A, A, A, B, B, C, C} (taken all at a time) =7!(3!    2!    2!)= \large \frac{7!}{(3! \ \ * \ \ 2! \ \ * \ \ 2!)}

Restricted Arrangement

Arrangement with some condition.

Example 1

If all the letters of the word PATLIPUTRA\text{PATLIPUTRA} are to be arranged then find number of words(s):

  • Starting with A\text{A}
  • 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,

P=2\text{P} = 2, A=2\text{A} = 2, T=2\text{T} = 2, L=1\text{L} = 1, I=1\text{I} = 1, U=1\text{U} = 1, R=1.\text{R} = 1.

Starting with A\text{A}

If A\text{A} is fixed at 1st1^{\text{st}} position, there will be 99 remaining positions. Remaining 99 letters can be arranged on 99 differnt position in 99 ways.

Since word PATLIPUTRA\text{PATLIPUTRA} has duplicate letter, arragment of all such letter should be removed.

So total number of words starting with A\text{A} will be 9!2!    2!\large \frac{9!}{2! \ \ * \ \ 2!}

Start and End with Vowel

There are total 33(A, I, U\text{A, I, U}) vowels in world PATLIPUTRA\text{PATLIPUTRA}, so there are 77 cases possible as below.

Case I: Starts with A\text{A} and ends with A\text{A}.

8!2!    2!\frac{8!}{2! \ \ * \ \ 2!}

Case II: Starts with A\text{A} and ends with I\text{I}.

8!2!    2!\frac{8!}{2! \ \ * \ \ 2!}

Case III: Starts with I\text{I} and ends with A\text{A}.

8!2!    2!\frac{8!}{2! \ \ * \ \ 2!}

Case IV: Starts with A\text{A} and ends with U\text{U}.

8!2!    2!\frac{8!}{2! \ \ * \ \ 2!}

Case V: Starts with U\text{U} and ends with A\text{A}.

8!2!    2!\frac{8!}{2! \ \ * \ \ 2!}

Case VI: Starts with U\text{U} and ends with A\text{A}.

8!2!    2!    2!\frac{8!}{2! \ \ * \ \ 2! \ \ * \ \ 2!}

Case VII: Starts with U\text{U} and ends with A\text{A}.

8!2!    2!    2!\frac{8!}{2! \ \ * \ \ 2! \ \ * \ \ 2!}

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 2nd2^{\text{nd}}, 5th5^{\text{th}}, 7th7^{\text{th}} 10th10^{\text{th}} should still be occupied by vowels as they are occupied by vowels in given word PATLIPUTRA\text{PATLIPUTRA}.

Let's first write down vowels and consonants list. Vowels are A=2\text{A} = 2, I=1\text{I} = 1, U=1\text{U} = 1 and consonants are P=2\text{P} = 2, T=2\text{T} = 2, L=1\text{L} = 1, R=1\text{R} = 1.

44 vowels can be arragned on 44 position in 4!4! ways out of which 22 vowels are repeating so there are 4!2!\large \frac{4!}{2!} ways.

Similarly, consonants can be arranged amoung themself in 6!2!    2!\large \frac{6!}{2! \ \ * \ \ 2!} ways.

So total number of words where relative order of vowel remains the same will be:

4!2!6!2!    2!\frac{4!}{2!} * \frac{6!}{2! \ \ * \ \ 2!}

Vowels Occupy Even Places

There are total 55 even position in word PATLIPUTRA\text{PATLIPUTRA} and total 44 vowels, so any 44 position can selected in 5C4^5\text{C}_4 ways. Also, 44 vowels can be arranged among themself in 4!4! ways of which 22 are same so vowels can be arranged in 4!2!\large \frac{4!}{2!} ways.

So total number of ways to arrange vowels in even position is 5C44!2!^5\text{C}_4 * \large \frac{4!}{2!}.

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 6C66!2!    2!^6\text{C}_6 * \large \frac{6!}{2! \ \ * \ \ 2!}.

So total number of words where vowels occupy even places will be:

5C4    4!2!    6C6    6!2!    2!^5C_4 \ \ * \ \ \frac{4!}{2!} \ \ * \ \ ^6C_6 \ \ * \ \ \frac{6!}{2! \ \ * \ \ 2!}

Rank of Word

Find the rank of a word SACHIN\text{SACHIN} if the letters of the word SACHIN\text{SACHIN} are permuted and are arranged in an alphabetical order as in an English dictionary.

In the dictionary, the words appearing first will begin with A\text{A}, then C\text{C}, then H\text{H}, then I\text{I}, then N\text{N} and at last S\text{S}.

Let us fix the first position as A\text{A}, remaining 55 places above can be filled with letters C, H, I, N, S\text{C, H, I, N, S} in 5!5! ways.

Similarly, fixing the first letter as C\text{C}, the remaining 55 places can be filled with letters A, H, I, N, S\text{A, H, I, N, S} in 5!5! ways.

Now, SACHIN\text{SACHIN} there are 55 letters(A, C, H, I, N\text{A, C, H, I, N}) come before SS in the alphabet, so there must be 55!5 * 5! words with a lower alphabetical rank.

Based on that let's calculate table below:

AlphbetRank of AlphabetRank less than itself to right of itFactorial in decending order
S655!
A104!
C203!
H302!
I401!
N500

So, rank of word SACHIN\text{SACHIN} is multiplication of last two columns ++ 1 1.

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 EQUATION\text{EQUATION} such that no two consonants appears together.

Solution

There are 33 consonents QTN\text{QTN} and 55 vowels EUAIO\text{EUAIO}.

To ensure that the consonants are separated, we'll start by arranging the 55 vowels, which creates 66 empty spaces between them. From these 66 spaces, we can then select 33 locations in 6C3^6\text{C}_3 different ways.

Additionally, 55 vowels can be arranged among themselves in 5!5! ways and 33 consonents can be arranged among themseleve in 3!3! ways.

So total number of arragements will be: 6C33!5!^6\text{C}_3 * 3! * 5!.

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 EQUATION\text{EQUATION} such that all vowels should apprear together.

Solution

There are 33 consonents QTN\text{QTN} and 55 vowels EUAIO\text{EUAIO}.

To keep the vowels together we first arrange the consonents QTN\text{QTN} which will create 44 empty places for vowels to choose from, which can be done in 4C1^4\text{C}_1 ways. In addition to that 33 consonents and 55 vowels can arrange among themself in 3!3! and 5!5! different ways.

So total number of words such that all vowels appears together will be: 4C13!5!^4\text{C}_1 * 3! * 5!.

Circular Permutation

Number of ways in which n\text{n} different things can be arranged on circle is (n - 1)!\text{(n - 1)}!.

Number of ways in which n\text{n} different things can be arranged on circle when clockwise and anticlockwise arrangement are considered as same is (n    1)!2\large \frac{(\text{n} \ \ - \ \ 1)!}{2}.

Combination

Combination involves only selection. Number of ways of selecting r\text{r} items from set of n\text{n} different items is denoted by == nCr^\text{n}\text{C}_\text{r}.

nCr=n!r!(n - r)!^\text{n}\text{C}_\text{r} = \frac{\text{n}!}{\text{r}!\text{(n - r)}!}

Example 1

There are two urns. Urn A\text{A} has 33 distinct red balls and urn B\text{B} has 99 distinct blue balls. From each urn 22 balls are taken out at random. Count the number of ways in which this can be done.

Solution

  • 22 balls can be drawn from Urn A\text{A} in 3C2^3\text{C}_2 ways.
  • 22 balls can be drawn from Urn B\text{B} in 9C2^9\text{C}_2 ways.

So total number of ways = 3C2^3\text{C}_2 * 9C2^9\text{C}_2 =108 = 108

Example 2

A Committee of 1111 members is to be formed from 88 males and 55 females. calculate number of ways the committee is formed with at least 66 males.

Solution

Here question is asking for at least 66 males, that means committee can have 66, 77 or all 88 males.

  • Ways for selecting of 66 males ∗ Ways for selecting of 55 females +
  • Ways for selecting of 77 males ∗ Ways for selecting of 44 females +
  • Ways for selecting of 88 males ∗ Ways for selecting of 33 females.

So total number of ways =(8C65C5)+(8C75C4)+(8C85C3)=78= (^8\text{C}_6 ∗ ^5\text{C}_5) + (^8\text{C}_7 ∗ ^5\text{C}_4) + (^8\text{C}_8 ∗ ^5\text{C}_3) = 78

Example 3

Total 1010 points are there, out of which 44 are collinear, then find total number of different straight lines that can be formed by joinning these points.

permutations-and-combinations-1.svg

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.

6C2^6\text{C}_2

Case II: One point from half circle and one point from line.

6C14C1^6\text{C}_1 * ^4\text{C}_1

Case III: Both points from line.

11

So total number of ways 15+24+1=4015 + 24 + 1 = 40.

Example 4

There are 44 straight lines, 33 circles and 22 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: 22 lines can give us maximum of 11 intersection point.

4C21^4\text{C}_2 * 1

Line to Circle intersection: 11 line and 11 circle can give us maximum of 22 intersection points.

4C13C12^4\text{C}_1 * ^3\text{C}_1 * 2

Line to Parabola intersection: 11 line and 11 parabola can give us maximum of 22 intersection points.

4C12C12^4\text{C}_1 * ^2\text{C}_1 * 2

Circle to Circle intersection: 22 circles can give us maximum of 22 intersection points.

3C22^3\text{C}_2 * 2

Circle to Parabola intersection: 11 circle and 11 parabola can give us maximum of 44 intersection points

3C12C14^3\text{C}_1 * ^2\text{C}_1 * 4

Parabola to Parabola intersection: 22 parabola can give us maximum of 22 intersection point.

2C24^2\text{C}_2 *4

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.

permutations-and-combinations-2.svg

Solution

To count all rectagles, we select any 22 vertical lines from given 77 vertical lines and select any 22 horizontal lines from given 88 horizontal lines. So total number of rectangles 7C28C2=49^7\text{C}_2 * ^8\text{C}_2 = 49.

To count all squares, we need to consider following cases:

  • Total squares of unit 11=76=421 * 1 = 7 * 6 = 42
  • Total squares of unit 22=65=302 * 2 = 6 * 5 = 30
  • Total squares of unit 33=54=203 * 3 = 5 * 4 = 20
  • Total squares of unit 44=43=124 * 4 = 4 * 3 = 12
  • Total squares of unit 55=32=65 * 5 = 3 * 2 = 6
  • Total squares of unit 66=21=26 * 6 = 2 * 1 = 2

So total number of squares 42+30+20+12+6+2=11242 + 30 + 20 + 12 + 6 + 2 = 112

Restricted Selection

Selection with some condition.

Example 1

55 boys are selected out of 77 boys such that two particular boys will NOT server together.

Solution

Let's say two particular boys are boy A\text{A} and boy B\text{B}, following cases are possible if two particular boys will NOT server together.

Case I : Boy A\text{A} will be selected and Boy B\text{B} will not be selected.

5C4^5\text{C}_4

Case II : Boy A\text{A} will not be selected and Boy B\text{B} will be selected.

5C4^5\text{C}_4

Case III: Boy A\text{A} will not be and selected Boy B\text{B} will not be selected

5C5^5\text{C}_5

So total number of ways will be 5+5+1=115 + 5 + 1 = 11

Example 2

55 boys are selected out of 77 boys such that two particular boys will always server together.

Solution

Let's say two specific boys are boy A\text{A} and boy B\text{B}, following cases are possible if two particular boys will always server together.

Case I: Boy A\text{A} will be selected and Boy B\text{B} will be selected

5C3^5\text{C}_3

Case II: Boy A\text{A} will not be selected and Boy B\text{B} will not be selected

5C5^5\text{C}_5

So total number of ways will be: 10+1=1110 + 1 = 11.

Selections of Unique & Non-Unique Items

N Non-Unique thingsN Unique things
Number of ways of selecting zero things =1= 1Number of ways of selecting zero things =1 = 1
Number of ways of selecting one things =1= 1Number of ways of selecting one things == nC1^\text{n}\text{C}_1
Number of ways of selecting two things =1= 1Number of ways of selecting two things == nC2^\text{n}\text{C}_2
...
Number of ways of selecting all things =1= 1Number of ways of selecting all things == nCn^\text{n}\text{C}_n
Total possible selection =(n+1)= (\text{n} + 1)Total possible selection = 2n2^\text{n}

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 1010 white, 99 green and 77 black balls.

Solution

Total number of ways to select one or more balls from 1010 white, 99 green and 77 black balls will be:

(select 00 or more balls from 1010 white balls) * (select 00 or more balls from 99 green balls) * (select 00 or more balls from 77 black balls)   1 - \ \ 1.

By applying the formula =(n+1) = (\text{n} + 1) to choose x\text{x} things from n\text{n} identical items we get 1111 ways for white ball, 1010 ways for green ball and 88 ways for black ball.

info

We subtract 11 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 111081=87911 * 10 * 8 - 1 = 879.

Divisor

If number N\text{N} can be divided into prime factor as N=2α3β5γ7δ...\text{N} = 2^{\alpha} * 3^{\beta} * 5^{\gamma} * 7^{\delta} * ... then total number of divisor will be:

(α+1)(β+1)(γ+1)(δ+1) ....(\alpha + 1) * (\beta + 1) * (\gamma + 1) * (\delta + 1) \space * ....

Proof

Imagine you have a bag containing α\alpha identical objects, and you want to determine all possible selections of α\alpha objects. Applying the formula for all possible selections on α\alpha identical objects you get (α+1)(\alpha + 1). Similarly for β\beta, γ\gamma, and δ\delta.

Hence proved that, total number of divisor will be:

(α+1)(β+1)(γ+1)(δ+1) ....(\alpha + 1) * (\beta + 1) * (\gamma + 1) * (\delta + 1) \space * ....
info

To get total number of proper divisor, you subtract 22 from above equation, as proper divisors are those that do not include 11 and the number itself.

Example 1

Calculate total number of unique ways to express N=8\text{N} = 8 as product of two factors.

Solution

There are 44 divisors for N=8\text{N} = 8 and those are 1,2,41, 2, 4 and 88, now if we choose those divisor as a first factor we get:

  • 8=20238 = 2^0 * 2^3
  • 8=21228 = 2^1 * 2^2
  • 8=22218 = 2^2 * 2^1
  • 8=23208 = 2^3 * 2^0

Here, the combinations of the last two products are identical to those of the first two products, so there are only 22 unique ways.

You can calculate unique ways to express N\text{N} as product of two factors, when N\text{N} is a perfect square using formula below:

Total number of divisors2\frac{\text{Total number of divisors}}{2}

So number of unique ways to express N=8\text{N} = 8 as product of two factors will be 22.

Example 2

Calculate total number of unique ways to express N=16\text{N} = 16 as product of two factors.

Solution

There are 55 divisors for N=16\text{N} = 16 and those are 1,2,4,81, 2, 4, 8 and 1616, now if we choose those divisor as a first factor we get:

  • 16=202416 = 2^0 * 2^4
  • 16=212316 = 2^1 * 2^3
  • 16=222216 = 2^2 * 2^2
  • 16=232116 = 2^3 * 2^1
  • 16=242016 = 2^4 * 2^0

Here, the combinations of the last three products are identical to those of the first three products, so there are only 33 unique ways.

You can also calculate unique ways to express N\text{N} as product of two factors, when N\text{N} is NOT a perfect square using formula below:

Total number of divisors + 12\frac{\text{Total number of divisors + 1}}{2}

So number of unique ways to express N=16\text{N} = 16 as product of two factors will be 33.

Division into Group

Below is an example of dividing different items into group when group size are different.

Example 1

Divide 99 different things into group size of 22, 33 and 44.

Solution

For the group of size 22, you have 99 choices for the first item and 88 choices for the second item. However, since the order within the group doesn't matter (i.e., choosing A\text{A} and then B\text{B} is the same as choosing B\text{B} and then A\text{A}), you need to divide by 2!2! (the number of ways to arrange 22 items within a group).

So for the first group, we have:

9    82!\frac{9 \ \ * \ \ 8}{2!}

For the group of size 33, you have 77 choices for the first item, 66 choices for the second item, and 55 choices for the third item. Again, you need to divide by 3!3! (the number of ways to arrange 33 items within a group).

So for the second group, we have:

7    6    53!\frac{7 \ \ * \ \ 6 \ \ * \ \ 5}{3!}

Similarly, for the group of size 44, you have 44 choices for the first item, 33 choices for the second item, 22 choices for the third item, and 11 choice for the fourth item. Once more, you need to divide by 4!4! (the number of ways to arrange 44 items within a group).

So for the third group, we have:

4    3    2    14!\frac{4 \ \ * \ \ 3 \ \ * \ \ 2 \ \ * \ \ 1}{4!}

Total number of ways to divide 99 different things into group size of 22, 33 and 44 will be:

9!2!    3!    4!\frac{9!}{2! \ \ * \ \ 3! \ \ * \ \ 4!}

Below is an example of dividing items into group when group size are same.

Example 2

Divide 77 different things into group size of 11, 22, 22, 22.

Solution

For the group of size 11, you have 77 choices because each item can be its own group.

For the first group of size 22, you have 66 choices for the first item and 55 choices for the second item. However, since the order within the group doesn't matter, you need to divide by 2!2! (the number of ways to arrange 22 items within a group).

So for the first group of size 22, we have:

6    52!\frac{6 \ \ * \ \ 5}{2!}

For the second group of size 22, you have 44 choices for the first item and 33 choices for the second item. Again, you need to divide by 2!2! (the number of ways to arrange 22 items within a group).

So for the second group of size 2, we have:

4    32!\frac{4 \ \ * \ \ 3}{2!}

Similarly, for the third group of size 22, you have 22 choices for the first item and 11 choice for the second item. Once more, you need to divide by 2!2! (the number of ways to arrange 22 items within a group).

So for the third group of size 22, we have:

2    12!\frac{2 \ \ * \ \ 1}{2!}

Additionally, because we have three groups, each with a size of 22, we also divide by 3!3!. So total number of ways to divide 77 different things into group size of 11, 22, 22, 22 will be:

7!1!    2!    2!    2!    3!\frac{7!}{1! \ \ * \ \ 2! \ \ * \ \ 2! \ \ * \ \ 2! \ \ * \ \ 3! }

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 66 different things across 33 different children such that every child get at least one.

Solution

First let's divide 66 different things into groups of 33.

Case I: Number of ways to divide 66 different things into a group of 1,2,31, 2, 3 will be:

6!1!    2!    3!\frac{6!}{1! \ \ * \ \ 2! \ \ * \ \ 3!}

Case II: Number of ways to divide 66 different things into a group of 1,1,41, 1, 4 will be:

6!1!    4!    1!  2!\frac{6!}{1! \ \ * \ \ 4! \ \ * \ \ 1! * \ \ 2!}

Case III: Number of ways to divide 66 different things into a group of 2,2,22, 2, 2 will be:

6!2!    2!    2!  3!\frac{6!}{2! \ \ * \ \ 2! \ \ * \ \ 2! * \ \ 3!}

In addition to that total number of ways to distribute these 33 group amoung three children is 3!3!.

So total number of ways to distribute 66 different things across 33 different children such that every child get at least one will be:

3!    (6!1!    2!    3!+6!1!    1!    4!  2!+6!2!    2!    2!  3!)3! \ \ * \ \ \large( \normalsize \frac{6!}{1! \ \ * \ \ 2! \ \ * \ \ 3!} + \frac{6!}{1! \ \ * \ \ 1! \ \ * \ \ 4! * \ \ 2!} + \frac{6!}{2! \ \ * \ \ 2! \ \ * \ \ 2! * \ \ 3!} \large)

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 55 identical objects among 33 persons, when zero distribution is allowed.

Solution

To distribute 55 identical objects into 33 person we will need 22 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:

7!5!    2!\frac{7!}{5! \ \ * \ \ 2!}

Example 2

Total number of ways of distributing 55 identical objects among 33 persons, such that each gets at least 11.

Solution

55 identical objects will create total of 44 empty spaces around them as represented by underscore(_) below:

O _ O _ O _ O _ O

info

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 11 object.

Since we want to distribute 55 objects among 33 people, we need to choose 22 spaces from the 44 empty spaces(_), so total number of ways are 4C2^4\text{C}_2.

Integral Solution of Equation

Below are some of the examples of solving Integral equation.

Example 1

Given equation x1+x2+x3+...+xr=n\text{x}_1 + \text{x}_2 + \text{x}_3 + ... + \text{x}_\text{r} = \text{n}, calculate number of solutions if x1,x2,x3,....xrN\text{x}_1, \text{x}_2, \text{x}_3, .... \text{x}_\text{r} \in \text{N} i.e. x1,x2,x3,....x>0\text{x}_1, \text{x}_2, \text{x}_3, .... \text{x} > 0.

Solution

Think of it as dividing n\text{n} identical objects into r\text{r} different children when zero distribution is not allowed. Let's say n=5\text{n} = 5 and r=3\text{r} = 3 distribution will look like below:

O _ O _ O _ O _ O

Formula for calculating number of ways to distribute n\text{n} identical objects into r\text{r} different people is below:

(n1)C(r1)^{(\text{n} - 1)}\text{C}_{(\text{r} - 1)}

Example 2

Given equation x1+x2+x3+...+xr=n\text{x}_1 + \text{x}_2 + \text{x}_3 + ... + \text{x}_\text{r} = \text{n}, calculate number of solutions if x1,x2,x3,....xrW\text{x}_1, \text{x}_2, \text{x}_3, .... \text{x}_\text{r} \in \text{W} i.e. x1,x2,x3,....x>=0\text{x}_1, \text{x}_2, \text{x}_3, .... \text{x} >= 0.

Solution

Think of it as dividing n\text{n} identical objects into r\text{r} different people when zero distribution is allowed. Let's say n=5\text{n} = 5 and r=3\text{r} = 3 distribution will look like below:

O O O O O | |

Formula for calculating number of ways to distribute n\text{n} identical objects into r\text{r} different children is below:

(n + r1)C(r1)^{(\text{n + r} - 1)}\text{C}_{(\text{r} - 1)}

Example 3

x + y + z + t = 15,  (x, y, znon-negative integers)\text{x + y + z + t = 15}, \ \ (\text{x, y, z} \in \text{non-negative integers}), calculate number of solutions.

Solution

Think of this problem as distributing 1515 identical objects into 44 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:

18!3!    15!\frac{18!}{3! \ \ * \ \ 15!}

Example 4

x + y + z + t = 16,  (x >= 1, y >= 2, z >= 3, t >= 0)\text{x + y + z + t = 16}, \ \ (\text{x >= 1, y >= 2, z >= 3, t >= 0}), calculate number of solutions.

Solution

  • Substract 11 from right hand side to satisfy the condition for x\text{x}.
  • Substract 22 from right hand side to satisfy the condition for y\text{y}.
  • Substract 33 from right hand side to satisfy the condition for z\text{z}.

New equation after satisfying condition for x, y, \text{x, y, } and z\text{z} will be:

x’ + y’ + z’ + t = 10\text{x' + y' + z' + t = 10}

Now, think of this problem as distributing 1010 identical objects into 44 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:

13!3!    10!\frac{13!}{3! \ \ * \ \ 10!}

Example 5

x + y + z + t = 16,  (x, y, z, todd positive integers)\text{x + y + z + t = 16}, \ \ (\text{x, y, z, t} \in \text{odd positive integers}), calculate number of solutions.

Solution

To satisfy condition replacing x, y, z, t\text{x, y, z, t} with below values:

  • x = 2p + 1\text{x = 2p + 1}
  • y = 2q + 1\text{y = 2q + 1}
  • z = 2r + 1\text{z = 2r + 1}
  • t = 2s + 1\text{t = 2s + 1}

New equation after satisfying condition for x, y, z\text{x, y, z} and t\text{t} will be:

p + q + r + s = 6,  (p, q, r, sW)\text{p + q + r + s = 6}, \ \ (\text{p, q, r, s} \in \text{W})

Now, think of this problem as distributing 66 identical objects into 44 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:

9!6!    3!\frac{9!}{6! \ \ * \ \ 3!}

Example 6

In how many ways 33 boys and 1515 girls can sit together in a row such that between every 22 boys there are at least 22 girls.

Solution

Let's say we have arragement as below:

x girls  +  Boy 1+  y girls  +  Boy 2+  z girls  +  Boy 3+  t girls\text{x girls} \ \ + \ \ \text{Boy 1} + \ \ \text{y girls} \ \ + \ \ \text{Boy 2} + \ \ \text{z girls} \ \ + \ \ \text{Boy 3} + \ \ \text{t girls}

Now, we want at least 22 girls between 22 boys, so we can rewrite the equations as below:

x + y + z + t = 15,  (x >= 0, y >= 2, z >= 2 and t >= 0)\text{x + y + z + t = 15}, \ \ (\text{x >= 0, y >= 2, z >= 2 and t >= 0})

Substract 22 from right hand side to satisfy the condition for y\text{y} and z\text{z}, new equation after satisfying condition for y\text{y} and z\text{z} will be:

x + y’ + z’ + t = 11,  (x >= 0, y >= 0, z >= 0 and t >= 0)\text{x + y' + z' + t = 11}, \ \ (\text{x >= 0, y >= 0, z >= 0 and t >= 0})

O O O O O O O O O O O | | |

In addition to that, 1515 girls and 33 boys can be arranged among themself among in 15!15! and 3!3! ways.

So total number of solutions for equations will be:

14!11!    3!    15!    3!\frac{14!}{11! \ \ * \ \ 3!} \ \ * \ \ 15! \ \ * \ \ 3!

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 a, b, c, d, e, f, g\text{a, b, c, d, e, f, g} (taken all) such that neither beg\text{beg} nor cad\text{cad} pattern appears.

Solution

Total number of arragements of a, b, c, d, e, f, g\text{a, b, c, d, e, f, g} will be 7!7!.

Now, to ensure that beg\text{beg} stays together, we apply the tie method, treating beg\text{beg} as a single unit. This reduces the total number of elements to 55 as a, c, d, f,\text{a, c, d, f,} and beg\text{beg}. So total number of arragements of a, b, c, d, e, f, g\text{a, b, c, d, e, f, g} with pattern beg\text{beg} will be 5!5!.

Similarly, total number of arragements of a, b, c, d, e, f, g\text{a, b, c, d, e, f, g} with pattern cad\text{cad} will be 5!5!.

To get our answer, we can subtract the arrangements with the patterns cad\text{cad} and beg\text{beg} from the total arrangements. However, this approach would lead to removing arrangements that contain both patterns cad\text{cad} and beg\text{beg} 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 beg\text{beg} and cad\text{cad} together. By applying the tie method again, we reduce the total number of elements to just a, f\text{a, f} and the combined pattern begcad\text{begcad}. This gives us a total of 3!3! arrangements that simultaneously contain both patterns.

So total number of arragement which contains neither beg\text{beg} or cad\text{cad} will be:

Total arrangements - Arrangements with pattern cad\text{cad} - Arrangements with pattern beg\text{beg} + Arrangements with pattern cad\text{cad} and beg\text{beg} together.

permutations-and-combinations-1.svg
7!5!5!+3!7! - 5! - 5! + 3!