Permutations and combinations

##### Example on Permutation

A class in probability theory consists of 6 men and 4 women. An examination is given, and the students are ranked according to their performance. Assume that no two students obtain the same score.

(a) How many different rankings are possible?

(b) If the men are ranked just among themselves and the women just among themselves, how many different rankings are possible?

(a) Because each ranking corresponds to a particular ordered arrangement of the 10 people, the answer to this part is 10! = 3,628,800.

(b) Since there are 6! possible rankings of the men among themselves and 4! possible rankings of the women among themselves, it follows from the basic principle that there are (6!)(4!) = (720)(24) = 17,280 possible rankings in this case.

##### 0Comment

##### Example 3d (Sheldon Ross) on Arrangement of Letters

How many different letter arrangements can be formed from the letters PEPPER?

We first note that

There are 6! permutations of the letters P_{1}E_{1}P_{2}P_{3}E_{2}R when the 3P’s and the 2E’s are distinguished from each other.

However, consider any one of these permutations—for instance, P_{1}P_{2}E_{1}P_{3}E_{2}R. If we now permute the P’s among themselves and the E’s among themselves, then the resultant arrangement would still be of the form PPEPER. That is, all 3! 2! permutations

P_{1}P_{2}E_{1}P_{3}E_{2}R P_{1}P_{2}E_{2}P_{3}E_{1}R

P_{1}P_{3}E_{1}P_{2}E_{2}R P_{1}P_{3}E_{2}P_{2}E_{1}R

P_{2}P_{1}E_{1}P_{3}E_{2}R P_{2}P_{1}E_{2}P_{3}E_{1}R

P_{2}P_{3}E_{1}P_{1}E_{2}R P_{2}P_{3}E_{2}P_{1}E_{1}R

P_{3}P_{1}E_{1}P_{2}E_{2}R P_{3}P_{1}E_{2}P_{2}E_{1}R

P_{3}P_{2}E_{1}P_{1}E_{2}R P_{3}P_{2}E_{2}P_{1}E_{1}R

are of the form PPEPER. Hence, there are \({6! \over (3! 2!)} = 60\) possible letter arrangements of the letters PEPPER.

##### 0Comment

##### Permutations

**THEOREM 1** If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are

P (n, r) = n(n − 1)(n − 2)···(n − r + 1)

r-permutations of a set with n distinct elements.

**Note: **If n and r are integers with 0 ≤ r ≤ n, then** P (n, r) = n!/ (n − r)! .**

**EXAMPLE** How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest?

**Solution: **Because it matters which person wins which prize, So for first prize we have 100 people now for second prize we havee 99 person left and third placed can be occupied by 98 people

Consequently, the answer is P (100, 3) = 100 · 99 · 98 = 970,200.

**EXAMPLE** Suppose that there are eight runners in a race. The winner receives a gold medal, the secondplace finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award these medals, if all possible outcomes of the race can occur and there are no ties?

**Solution: **The number of different ways to award the medals is the number of 3-permutations of a set with eight elements. Hence, there are P (8, 3) = 8 · 7 · 6 = 336 possible ways to award the medals.

OR

We can say that we need to choose 3 person out of 8 ,after choosing we can arrange themi.e

C(8,3)*3! = (8!/5!*3!)*3! = P(8,3)

**EXAMPLE** Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities?

**Solution:**the first city is determined, So we have to find permutation for rest 7 cities but the remaining seven can be ordered arbitrarily. Consequently, there are 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman to choose her tour.

**EXAMPLE** How many permutations of the letters ABCDEFGH contain the string ABC ?

**Solution:** Because the letters **ABC** must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block ABC and the individual letters D, E, F, G, and H. Because these six objects can occur in any order, there are 6! = 720 permutations of the letters **ABC**DEFGH in which **ABC** occurs as a block.

##### 0Comment

##### Combinations

**THEOREM ** The number of r-combinations of a set with n elements, where n is a non-negative integer and r is an integer with 0 ≤ r ≤ n, equals

C(n, r) = n!\r!(n − r)!

Here note that we are only counting unordered selections of objects..i.e ordered not matter

**Example :**Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S. (Note that {4, 1, 3} is the same 3-combination as {1, 3, 4}, because the order in which the elements of a set are listed does not matter.)

An **r-combination **of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.

**EXAMPLE : **How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also, how many ways are there to select 47 cards from a standard deck of 52 cards?

**Solution:** Because the order in which the five cards are dealt from a deck of 52 cards does not matter, there are C(52, 5) = 52! /5!47!

To select 47 cards from 52 cards we can write as,

C(52, 47) = 52! /47!5!

**Note: **Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).

**EXAMPLE ** How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?

**Solution:**

the number of 5-combinations of a set with 10 elements. By Theorem , the number of such combinations is C(10, 5) = 10! /5! 5! = 252.

**EXAMPLE** A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many ways are there to select a crew of six people to go on this mission (assuming that all crew members have the same job)?

**Solution:**

The number of ways to select a crew of six from the pool of 30 people is the number of 6-combinations of a set with 30 elements

C(30, 6) = 30!/ 6! 24! = 30 · 29 · 28 · 27 · 26 · 25 /6 · 5 · 4 · 3 · 2 · 1 = 593,775.

**EXAMPLE** How many bit strings of length n contain exactly r 1s?

**Solution:**

The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of length n that contain exactly r 1s.

**EXAMPLE :**

Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?

**Solution: **By the product rule, the answer is the product of the number of 3-combinations of a set with nine elements and the number of 4-combinations of a set with 11 elements. The number of ways to select the committee is

C(9, 3) · C(11, 4) = 9! /3!6! · 11! /4!7!

= 84 · 330

= 27,720.

##### 0Comment

##### Example 4c Sheldon Ross

Consider a set of n antennas of which m are defective and n − m are functional and assume that all of the defectives and all of the functionals are considered indistinguishable. How many linear orderings are there in which no two defectives are consecutive?

Imagine that the n − m functional antennas are lined up among themselves.

Now, if no two defectives are to be consecutive, then the spaces between the functional antennas must each contain at most one defective antenna That is, in the n − m + 1 possible positions—represented in Figure 1.1 by carets—between the n − m functional antennas, we must select m of these in which to put the defective antennas. Hence, there are \({n - m + 1 \choose m}\) possible orderings in which there is at least one functional antenna between any two defective ones.

##### 0Comment

##### Example 6a Sheldon Ross

How many distinct nonnegative integer-valued solutions of x1 + x2 = 3 are possible?

**Things you need to know **

Proposition 6.1 & 6.2 Sheldon Ross (8th edition)

Now,

There are \({3 + 2 - 1 \choose 2 - 1} = 4\) such solutions : (0, 3), (1, 2), (2, 1), (3, 0).

##### 0Comment

##### Example 5a Sheldon Ross on Combinatorics

A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 officers into the 3 groups are possible?

There are \(10 ! \over 5! 2! 3 ! \) possible divisions.

##### 0Comment

##### Number of games to play

For a game in which 2 partners oppose 2 other partners, seven men are available. If every possible pair must play against every other pair, then the number of games to be played is

- 90
- 120
- 140
- 105

Let us consider 7 men as a, b, c, d, e, f ,g

Then no. of ways to pick 2 out of 7 men = ^{7}C_{2} = 21

Then no. of ways to pick 2 out of remaining 5 men = ^{5}C_{2} =10

thus , total possible way of game =21*10/2 =210/2 = 105

//we have divided it by 2 as playing pair a with pair b , is same as playing pair b with pair a

Ans is 105

##### 1Comment

##### The Pigeonhole Principle

**Theorem: **If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

The abstract formulation of the principle: Let X and Y be finite sets and let

F : XY be a function then,

1) If X has more elements than Y, then f is not one-to-one.

2)If X and Y have the same number of elements and f is onto, then f is one-to-one.

3)If X and Y have the same number of elements and f is one-to-one, then f is onto.

Pigeonhole principle is one of the simplest but most useful ideas in mathematics. We will see more applications that proof of this theorem.

**Example –:** A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

**Solution**: Apply pigeonhole principle.

No. of colors (pigeonholes) n = 3

No. of marbles (pigeons) K+1 = 4

Therefore the minimum no. of marbles required = Kn+1

By simplifying we get Kn+1 = 10.

Verification: ceil[Average] is [Kn+1/n] = 4

[Kn+1/3] = 4

Kn+1 = 10

i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

Pigeonhole principle another form –

**Theorem: **Let a1, a2, . . . , an be positive integers.

If a1+ a2+ . . . + an – n + 1 objects are put into n boxes, then either the 1st box contains at least a1 objects, or the 2nd box contains at least a2 objects, . . ., the nth box contains at least an objects.

Application of this theorem is more important, so let us see how we apply this theorem in problem solving.

**Example **– 1: In a computer science department, a student club can be formed with either 9 members from first year or 7 members from second year or 6 from third year or 3 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed?

Solution: we can directly apply from the above formula where,

a1 =9, a2 =7, a3 =6, a4 =3 and n=4

Therefore the minimum number of students required to ensure department club to be formed is

9 + 7+ 6 + 3 – 4 + 1 = 22

##### 0Comment

##### Distributing Objects into Boxes

**Case1: **__DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES__

**EXAMPLE**

How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?

sol:

The first player can be choose 5 cards in C(52, 5) ways. The second player can be choose 5 cards in C(47, 5) ways, because only 47 cards are left. The third player can be choose 5 cards in C(42, 5) ways. Finally, the fourth player can be choose 5 cards in C(37, 5) ways. Hence, the total number of ways to deal four players 5 cards each is

here we use product rule,

C(52, 5)C(47, 5)C(42, 5)C(37, 5) = 52! /47! 5! · 47!/ 42! 5! · 42! /37! 5! · 37! /32! 5!

= 52!/ 5! 5! 5! 5! 32!

**THEOREM** The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i, i = 1, 2,... , k, equals **n! /n1! n2!··· nk!**

**Case2:** __INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES__

Counting the number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to be the same as counting the number of n-combinations for a set with k elements when repetitions are allowed.

**EXAMPLE **

How many ways are there to place 10 indistinguishable balls into eight distinguishable bins?

**Solution:** The number of ways to place 10 indistinguishable balls into eight bins equals the number of 10-combinations from a set with eight elements when repetition is allowed.

C(8 + 10 − 1, 10) = C(17, 10) = 17! /10!7!

= 19,448.

This means that there are C(n + r − 1, n − 1) ways to place r indistinguishable objects into n distinguishable boxes

**Case3:** __DISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES__

**EXAMPLE**

How many ways are there to put four different employees into three indistinguishable offices, when each office can contain any number of employees?

**Solution:**

First, we note that we can distribute employees so that all four are put into one office, three are put into one office and a fourth is put into a second office, two employees are put into one office and two put into a second office, and finally, two are put into one office, and one each put into the other two offices. Each way to distribute these employees to these offices can be represented by a way to partition the elements A, B, C, and D into disjoint subsets.

we find that there are 14 ways to put four different employees into three indistinguishable offices.

**Case4:** __INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES__

**EXAMPLE **

How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?

**Solution:**

here we will write all the ways we can pack books in the boxes

we will list the number of books in the box with the largest number of books, followed by the numbers of books in each box containing at least one book, in order of decreasing number of books in a box.

6

5, 1

4, 2

4, 1, 1

3, 3

3, 2, 1

3, 1, 1, 1

2, 2, 2

2, 2, 1, 1.