Combinatorics: Word Arrangement Problem

May 2017
6
0
United States
A screenshot to my problem: http://prntscr.com/md3hhc

mathematics.png

I found a Chegg answer to the word WISCONSIN, and I understand that you separate each letter into its appearance but afterwards they didn't really explain much about how to solve it. They just solved it with no explanation and I can't really follow along.

Thanks for the help!
 

Plato

MHF Helper
Aug 2006
22,507
8,664
There are five letters that do not repeat: $\_\_\_H\_\_\_E\_\_\_I\_\_\_C\_\_\_S\_\_\_$ we use those to separate those that do repeat.
Note that the five create six spaces for the repeaters: $MMAATT$
The separators can be arranged in $5!$ ways and the repeaters can be arranged in $\dfrac{6!}{(2!)^3}$ ways.
So what is the answer?
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
Here's how I would do that. Imagine labeling each of the repeated letters with a subscript so you can tell them apart: \(\displaystyle WI_1S_1CON_1S_2I_2N_2\). Then there are 9 distinct letters so 9! ways to arrange them. But two of those 9! arrangements are, for example \(\displaystyle WI_1S_1CON_1S_2I_2N_2\) and \(\displaystyle WI_2S_1CON_1S_2I_1N_2\), exactly the same except that the two "I"s have been swapped. That is, for every one of the 9! ways to arrange WISCONSIN, there is another that has only the "I"s swapped that we don't want to count as "different". To allow for that, divide by 2!= 2, the number of ways to arrange, or swap, the two "I"s. Similarly with the two "S"s and two "N"s. The number of distinct arrangements is \(\displaystyle \frac{9!}{2!2!2!}= \frac{362880}{8}= 45360\).

More generally, if a word has \(\displaystyle m\) letters, \(\displaystyle n_1\) of which are the same, \(\displaystyle n_2\) of which are the same but different from the first, … to \(\displaystyle n_i\) of which are the same, then the number of distinct arrangements is \(\displaystyle \frac{m!}{n_1!n_2!\cdot\cdot\cdot n_i!}\). Notice that, since 1!= 1, we can include "n"s that are equal to 1 requiring that \(\displaystyle n_1+ n_2+ \cdot\cdot\cdot+ n_i= m\).