How many ways 5 letters can be selected using the letters of the word Mississippi?

This section covers permutations and combinations.

Arranging Objects

The number of ways of arranging n unlike objects in a line is n! (pronounced ‘n factorial’). n! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1

Example

How many different ways can the letters P, Q, R, S be arranged?

The answer is 4! = 24.

This is because there are four spaces to be filled: _, _, _, _

The first space can be filled by any one of the four letters. The second space can be filled by any of the remaining 3 letters. The third space can be filled by any of the 2 remaining letters and the final space must be filled by the one remaining letter. The total number of possible arrangements is therefore 4 × 3 × 2 × 1 = 4!

• The number of ways of arranging n objects, of which p of one type are alike, q of a second type are alike, r of a third type are alike, etc is:

n!        .
p! q! r! …

Example

In how many ways can the letters in the word: STATISTICS be arranged?

There are 3 S’s, 2 I’s and 3 T’s in this word, therefore, the number of ways of arranging the letters are:

10!=50 400
3! 2! 3!

Rings and Roundabouts

• The number of ways of arranging n unlike objects in a ring when clockwise and anticlockwise arrangements are different is (n – 1)!

When clockwise and anti-clockwise arrangements are the same, the number of ways is ½ (n – 1)!

Example

Ten people go to a party. How many different ways can they be seated?

Anti-clockwise and clockwise arrangements are the same. Therefore, the total number of ways is ½ (10-1)! = 181 440

Combinations

The number of ways of selecting r objects from n unlike objects is:

Example

There are 10 balls in a bag numbered from 1 to 10. Three balls are selected at random. How many different ways are there of selecting the three balls?

10C3 =10!=10 × 9 × 8= 120
             3! (10 – 3)!3 × 2 × 1

Permutations

A permutation is an ordered arrangement.

• The number of ordered arrangements of r objects taken from n unlike objects is:

nPr =       n!       .
          (n – r)!

Example

In the Match of the Day’s goal of the month competition, you had to pick the top 3 goals out of 10. Since the order is important, it is the permutation formula which we use.

10P3 =10!
            7!

= 720

There are therefore 720 different ways of picking the top three goals.

Probability

The above facts can be used to help solve problems in probability.

Example

In the National Lottery, 6 numbers are chosen from 49. You win if the 6 balls you pick match the six balls selected by the machine. What is the probability of winning the National Lottery?

The number of ways of choosing 6 numbers from 49 is 49C6 = 13 983 816 .

Therefore the probability of winning the lottery is 1/13983816 = 0.000 000 071 5 (3sf), which is about a 1 in 14 million chance.

Intro to Combinatorics

The Multinomial Theorem Explained

Today I’m continuing to talk about the fundamentals of combinatorics with the Multinomial Theorem, andwhat better way to do this than to tackle some classic combinatorics problems 😉

Have you got the chops to solve these problems?

The Mississippi Counting Problems

Problem 1

How many total arrangements of the letters in MISSISSIPPI are there?

Problem 2

How many arrangements of the letters in MISSISSIPPI exist such that the 2 P’s are separated?

Problem 3

How many arrangements of the letters in MISSISSIPPI have at least 2 adjacent S’s?

Note:

If you need a review of the basics, check out this intro to combinatorics post:

Solution #1: Permutations of MISSISSIPPI

Getting Started

In the last post we discovered that we can find the number of unique permutations by using the Fundamental Theorem of Counting.

Since MISSISSIPPI has 11 letters, draw eleven lines and fill each in with the number of available letter choices, e.g. 11 options for the first, 10 for the second, and so on…

This is equal to 11! or 39,916,800 permutations.

But is this correct for the unique permutations of the letters in MISSISSIPPI?

Consider this…

What happens if I switch the 3rd and 4th letters in MISSISSIPPI and leave all else the same? Are those different permutations?

Nope.

The 3rd and 4th letters are both S’s so switching them changes nothing. The above calculation is an over count because of these repeat letters.

So how do we adjust for these extra repeated arrangements?

Adjusting for Repeats

To adjust our calculation we need to divide out the duplicate permutations. Finding them isn’t too difficult.

First determine what causes repeated arrangements. This comes from letters that occur more than once. For MISSISSIPPI that includes 2 P’s, 4 I’s, and 4 S’s.

Let’s start with the P’s. For every permutation, we can make an identical permutation with the P’s in opposite positions. So to adjust for these duplications, we must divide by 2! (the number of ways we can arrange the 2 P’s).

To adjust for the repeated I’s, divide by the number of ways we can arrange 4 I’s, which is 4!.

Lastly to account for the 4 S’s divide by another 4!.

There we go! There are 34,650 permutations of the word MISSISSIPPI.

The Multinomial Theorem

This process of dividing out repeated permutations is exactly what the Multinomial Theorem is!

The Multinomial Theorem says in order to count the number of distinct ways a set of elements with duplicate items can be ordered all you need to do is divide the total number of permutations by the factorial of the quantity of each duplicate (turns out doing the math is easier than writing that sentence 😳 ).

So since MISSISSIPPI has 11 total letters with 2 P’s, 4 I’s, and 4 S’s our calculation is: 11!/(2!4!4!).

Solution #2: No Adjacent P’s

To solve this problem we have to get a little creative. We need to count the ways we can make permutations so that no P’s are adjacent. Let’s start simple and remove the P’s altogether.

Start by removing the P’s & calculating the permutations

This of course is just one arrangement of MISSISSII, how many ways could we rearrange those letters? Using the Multinomial Theorem there are 9!/(4!4!) or 630 permutations.

Okay, now let’s deal with the P’s. I’m going to draw in blanks before and after every letter of MISSISSII. These will represent the possible places we can insert P’s, and because each space is separated by some non-P letter, we know these are all safe possibilities.

We have 10 blanks and we can choose any 2 blanks to insert P’s at, so we need to calculate 10 choose 2 = 45 ways (click here for recap on the “choose” combinations formula).

Alright, last step.

We calculated that there are 630 ways of rearranging the non-P letters and 45 ways of inserting P’s, so to find the total number of desired permutations use the basic principle of counting, i.e. multiply the values together.

Number of permutations of MISSISSIPPI without adjacent P’s

So there are 28,350 permutations of MISSISSIPPI where the P’s are not adjacent.

Solution #3: At Least 2 Adjacent S’s

Where to begin? You know, we could come at this problem from the opposite angle. Instead of counting how many permutations have 2 or more adjacent S’s, we could find how many permutations have no adjacent S’s and then subtract that number from the total permutations of MISSISSIPPI.

Shall we try that?

Okay, this is similar to our last problem then. Start by removing the S’s and finding the permutations of the remaining letters using the Multinomial Theorem.

Remove the S’s

We have 7 letters with 4 I’s and 2 P’s, so that’s a total of 105 permutations.

Using the Multinomial Theorem

Next add blanks before and after each letter to represent places we can insert S’s.

There are 8 blanks and we have 4 S’s that can be inserted into any of those blanks. So let’s calculate 8 choose 4:

And then multiply the results together.

Number of permutations of MISSISSIPPI without adjacent S’s

That gives us the number of permutations of MISSISSIPPI without adjacent S’s. Remember we want to find the opposite. We want to know how many permutations have at least 2 adjacent S’s.

We know from problem #1 there are 34,650 permutations of MISSISSIPPI and we now know that 7,350 arrangements have no adjacent S’s, so to find the permutations with at least 2 adjacent S’s simply take the difference.

Number of permutations of MISSISSIPPI with at least 2 adjacent S’s

So there are 27,300 permutations with 2 or more adjacent S’s.

Thanks so much for reading!

Click the ❤ to let me know you learned something new!

More Interesting Math Stuff →

How many ways can the letters in the word Mississippi be arranged?

How many combinations can be made for the word Mississippi?

How many permutations can be formed using the letters of Mississippi?

How many ways can a 5 letter word be rearranged?