Mississississippi

How many of the permutations of the letters in the word "MISSISSIPPI" are palindromes?

Details and assumptions

A permutation of the letters of a word contains all of the letters in the word in some order.


The answer is 30.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Trevor B.
Dec 16, 2013

The first thing we should do is define a palindrome. This is where the letters of a word (or number, but that's not relevant here) read the same forwards and backwards. For example, "Word row" is a palindrome.

Next, take an inventory of the letters in the word "Mississippi." There are 4 4 I's, 4 4 S's, 2 2 P's, and 1 1 M, for a total of 11 11 letters. The first 5 5 letters of the word are the same as the reverse of the last 5 5 letters of the word, and the middle 6 6 th letter can be anything. A palindrome with an odd number of letters has exactly one letter that appears an odd number of times, so the 6 6 th letter of a palindromic permutation of the letters in "MISSISSIPPI" is always "M." This leaves us with 4 4 I's, 4 4 S's, and 2 2 P's.

There are 5 5 letters that occur before the "M." Each different permutation of the first 5 5 letters has a unique permutation of the last 5 5 letters. Because the arrangement of letters is symmetric about the "M," there are 2 2 I's, 2 2 S's, and 1 1 P in the first 5 5 letters. The number of ways to arrange these letters is equal to 5 ! 2 ! × 2 ! × 1 ! = 120 4 = 30 \dfrac{5!}{2!\times2!\times1!}=\dfrac{120}{4}=\boxed{30}

Some generalizations about the problem include the following.

In a palindrome with n n letters where n n is odd, the first n 1 2 \dfrac{n-1}{2} letters are the same as the reverse of the last n 1 2 \dfrac{n-1}{2} letters, and the n + 1 2 \dfrac{n+1}{2} th letter has no restrictions. Similarly, in a palindrome with k k letters where k k is even, the first k 2 \dfrac{k}{2} letters are the same as the reverse of the last k 2 \dfrac{k}{2} letters. There is not a letter that has no restrictions because the k 2 \dfrac{k}{2} th letter is the same as the 1 + k 2 1+\dfrac{k}{2} th letter.

In a palindrome with an odd number of letters, there is exactly one letter that appears an odd number of times. In a palindrome with an even number of letters, no letters occur an odd number of times.

The number of ways to arrange n n letters where the letters { a 1 , a 2 , } \{a_1, a_2, \ldots\} appear { b 1 , b 2 , } \{b_1, b_2, \ldots\} times is equal to n ! b 1 ! b 2 ! \dfrac{n!}{b_1!b_2!\ldots}

wao brillient

Maria Kanwal Maria Kanwal - 7 years, 5 months ago

nice generalization ^^

Jean Lille - 7 years, 3 months ago
Oliver Welsh
Dec 16, 2013

First we count the number of times each letter appears. There is 1 1 M, 2 2 I's, 4 4 S's and 4 4 P's. Therefore, the M must be the middle letter. Hence, the palindromes will be in the form, a b c d e M e d c b a \overline{abcde}\text{M}\overline{edcba} Among the letters a b c d e \overline{abcde} , there must be 1 1 I, 2 2 S's and 2 2 P's. The number of ways to organise 5 5 elements is 5 ! = 120 5! = 120 , and since there are 2 2 S's and 2 2 P's we divide by 2 ! 2 ! = 2 2 = 4 2!2! = 2 \cdot 2 = 4 . Hence, the final answer is, 5 ! 2 ! 2 ! = 120 4 = 30 \frac{5!}{2!2!} = \frac{120}{4} = \fbox{30}

actually there are 4 I's and 2P's

Rishabh Jain - 7 years, 5 months ago
Isik Oz
Dec 17, 2013

There is only one letter "M", so the palindromes are supposed to look like _ _ _ _ _ M _ _ _ _ _. Since the left hand side is the same as the right hand side, just like in a mirror, then the problem boils down to placing 2 letter "I"s, 2 letter "S"s, and 1 letter "P" in 5 places. So the solution is: 5 ! 2 × 2 = 30 \frac{5!}{2\times2} = 30

Isak Falk
Dec 16, 2013

First we recognize that due to the palindrome constraint, we only need to consider half of the word. Furthermore as we have a lone M M it has to be in the middle. We are left with 5 5 letter: 2 I 2 I 's, 2 S 2 S 's and 1 P 1 P as we are considering half the word and the second half is mirrored and thus consist of the other half of the set of letters. This leaves us with 5 ! = 120 5! = 120 permutations, but as we have two pairs of doublettes, we have to divide this number by 2 2 = 4 2*2 = 4 in order to get the number of unique permutations. Thus the number of palindromes of M I S S I S S I P P I MISSISSIPPI are 30 \boxed{30}

'MISSISSIPPI' has 11 letters. Since there is only 1 'M,' it must be the 6th letter (the middle) as it is the only letter that doesn't need to match up with another. The last 5 letters will match up with the first 5, so we only care about the first 5 letters. Dividing the number of 'S's, 'I's, and 'P's by 2 to account for the matching up, we have 2 'S's, 2'I's, and 1 'P' for the first five letters. Out of the five "places" for the first 5 letters, we must choose 2 for the 'S's, 2 out of the remaining 3 for the 'I's, and the left over one is for the 'P'. Therefore, the answer is ( 5 2 ) ( 3 2 ) = 10 3 = 30 \binom{5}{2}\cdot\binom{3}{2}=10\cdot3=\boxed{30}

The word has 1 M \text{M} , 4 I \text{I} , 4 S \text{S} & 2 P \text{P} . So for a permutation to be a palindrome, the middlemost letter must be M M . Now 2 I I , 2 S S & 1 P P must remain on either side of M M . For each permutation of these letters on one side of M M there is a unique mirror image of it on the other side for the word to be palindrome. So the number of such words is the number of permutations of 2 I I , 2 S S & 1 P P , which are 5 ! 2 ! 2 ! = 30 \frac{5!}{2! 2!} = \boxed{30} in number.

Ashwin K
Feb 12, 2016

Interesting problem..

What we need to understand is for Palindrome only center letter i.e 6th letter will be unique which is M and either side of this letter will be a repetition (i.e)First 5 letters from starting will be same as last 5 letters in reverse order.

First 5 letters can take I,I,P,S,S which can be formed in 5!/2!2! = 30.
Ajay Maity
Dec 18, 2013

The number of letter in MISSISSIPPI is 11. So for the word to be a palindrome, the 1st letter should be same as 11th letter, 2nd same as 10th, 3rd same as 9th, 4th same as 8th and 5th same as 7th. So, the 6th letter is unique. Here, the only unique letter is M. So, the 6th letter in our case has to be M.

Now comes the remaining letters. We have the configuration:

_ _ _ _ _ _ _ _ _ _M _ _ _ _ _ _ _ _ _ _

We have 4 S's, 4 I's and 2 P's in the original word. So dividing them equally since we must have same letters on both sides of M to be a palindrome, we have 2 S's, 2 I's and 1 P on either side of M.

Number of ways in which 2 S's, 2 I's and 1 P can be permuted is ( 2 + 2 + 1 ) ! 2 ! × 2 ! × 1 ! \frac{(2 + 2 + 1)!}{2! \times 2! \times 1!} which comes out to be 30.

So we permuted all possible words on the left side of M. Now, on the right side of M, we can't actually have any permutation because if the left side of M has SSIIP, the right side of M must have PIISS for the whole word to be a palindrome.

So, the result we calculated must be the final result. Please be noted here, that the right side has no freedom to choose their letter. The degree of freedom is with the left hand side letter. Whatever 5 letters you chose for the left side, the right side has to choose the same sequence in reverse order.

Hope I am conveying my point properly. If you didn't understand any thing, just let me know in the comments.

Finally, 30 \boxed{30} is the correct answer!

Code 0987
Dec 18, 2013

Total letters = 11

No of M = 1, I = 4, S = 4, P = 2

Now since, length of palindrome word is a odd no. , so the center letter in palindrome word must be odd in count . Here, only M = 1 is satisfying condition .

So, our palindrome word is - _ _ _ _ _ M _ _ _ _ _ .

Now, when we start filling remaining letters, we've to fill 2 letters of same type, one from starting, one from ending as to make palindrome . Example - S I S I P M P I S I S S I S I P M P I S I S .

So, or word has only 5 places which are variable , rest are fixed automatically.

So, we've 2I, 2S & 1P left to fill. We can assume our palindrome word as a word of 5 letters and hence, it's permutations are given by 5 ! 2 ! 2 ! 1 ! = 30 \frac{5!}{2!2!1!} = \boxed{30}

Defination of palindrome A word, phrase, or sequence that reads the same backwards as forwards, e.g. madam or nurses run. Now we know in word "MISSISSIPPI" ther are 4I,4S,2Pand one M This means M should be in the center of any palindrome/word Now- the word looks like _ _ _ _ M _ _ _ _ with same word either side of M which is made up of 2I,2S and 1P Possible ways to do that are 5!/2!*2! i.e 30 please tell me how to post a solution

Pranav Vashistha - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...