Combinatorics: Permutations with Repetition

Welcome to permutations level II! This post involves the concept of permutation, but with an added layer of complexity. Consider the word MISSISSIPPI; how would one go about getting the number of different ways this word can be arranged (permutation)? If you attempted to calculate this problem using the original formula you would get 11! which would be incorrect. You would be over counting for all of the repeated letters.

In order to complete this permutation you must think of each repeated letter as occupying a certain position in the sequence. For example, if we were to place the S’s first there would be 11 places that the S’s can go (e.g. {1,3,6,11}. We can use our combination formula to calculate the number of different subsets to place the S’s, equaling {11}\choose {4}. The rest of the calculation proceeds in a similar fashion and we arrive at the following:

{11}\choose {4}  \cdot {7}\choose {4} \cdot  {3}\choose {2} \cdot {1}\choose {1} = 34,650

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s