Number of possible $4$ letter words from a set of $3$ letters, where only one letter repeats twice.

combinatorics

I have a set $A$ of $3$ letters, $A=\{a,b,c\}$. How many $4$ letter words are there that be formed where exactly $1$ letter repeats twice. I think that I have to work out the number of such combinations where $a$ repeats twice, then again for $b$ and then $c$ and add these up. But I'm not sure how. The possible solutions are:

$2 \cdot 4!$
$1/2 \cdot 3! \cdot 3 \cdot 4$
$2 \cdot 3 \cdot {4 \choose 2}$
$2^4 \cdot {3 \choose 2}$

Edit 1 – The 3rd option is $4 \choose 2$ and not $4 \choose 3$.

Edit 2 – I did it the same way @fleabood did. As @Arthur suggested, it is easier to consider the case where only $a$ repeats itself twice since the number of way for such an arrangement is the same for when only the $b$ or $c$ repeats itself. If only the $a$ repeats itself twice, since we have $4$ available slots of where to place the $2$ $a's$, we have that the number of ways to place the $2$ $a's$ is $4 \choose 2$. The remaining two slots can be used for $b$ or $c$, to which only $2$ such arrangements exist. Therefore, for the case where only the $a$ repeats itself twice, we have that the number of such arrangements is ${4 \choose 2} = 6$. The same logic works for if only the $b$ or $c$ repeats itself twice, therefore the total number of possibilities is $2 \cdot 3 \cdot {4 \choose 2} = 36$.

There is however another answer: Option 2 $1/2 \cdot 3! \cdot 3 \cdot 4$, since this also equals 36. However, I'm not sure I understand the logic behind that. What I think is happening, is that in any $3$ of the $4$ slots, we do not place a repeated letter, i.e. only place one $a,b,c$. For such an arrangement there are $3!$ possibilities. Now for the $4^{th}$ slot we can choose any one of the letters to place. If we say that we want to repeat only $a$, then this $a$ can go in any one of the $4$ slots, therefore, we have $3! \cdot 4$ such possibilities for repeating only the letter $a$ twice. Applying the same logic for the previous answer we have $3 \cdot 4 \cdot 3!$. But I'm not sure why the $1/2$ is present there.

PS – Sorry for the long explanation. I'm just trying to make sure that I understand it fully.

Best Answer

There are four letters in the string. Exactly two of those letters are the same letter repeating twice. The other two letters must be distinct and different. So we use three different types of letters. And we only have three types of letters to choose from so we use all types.

We have a $1$ out of $3$ choice,( ${3\choose 1} = 3$), for which letter is repeated. Then we have a $2$ out of $4$ choice, (${4\choose 2}=\frac {4!}{2!2!}=\frac {3*4}2=6$), for where to position those letters. And of the remaining two slots we can arrange the remaining two distinct letters $2!=2$ ways.

So the solution is ${3\choose 1}{4\choose 2}2!$ or $3*2!{4\choose 2}$ or $3*6*2=36$ or some other similar representation.

So the answer is $c$.

To follow your idea:

You hae to place the $a$s.

You can do $aa--$ or $a-a-$ or $a--a$ or $-aa-$ or $-a-a$ or $--aa$. So there are $6$ ways.

This is small enough be do by hand but it may be better to get used to think: I have $4$ options to place the $a$ and I must choose $2$ of the. That is ${4\choose 2}$. I can have for options to choose the first $a'$ and then I have three remaining slots for the $a^*$. So that is $4*3$ ways. But the $a'$ and $a^*$ are indistinguishable so I overdid it. There for whatever order I put $a'$ and $a^*$ in I could switch them around so we have $\frac{4*3}2 =6$. In general... $n$ choose $r$ will be ${n\choose r} = \frac {n*(n-1)*.....*(n-r+1)}{r*(r-1)*....*2*1}=\frac {n!}{(n-r)!r!}$.

Then in the remaining two remaining spaces you must place the $b$ and $c$. You have two options: Place the $b$ in the first available slot and $c$ in the second, or ..... place the $b$ in the second and place the $c$ in the first. So that is $2$ ways

So $6*2=12$ ways to place the $2$ $a$s.

Then be symmetry, two $b$s and two $c$s are the same.

So there are $3*12 =36$ ways.

Related Solutions

Probability – How Many Distinct n-Letter Words Can Be Formed from a Set of k Letters with Repetitions?

There is a fairly systematic way to work this type of question. You were specifically wondering about:

How many 4-letter words can be formed from the letters: ABBCCC?

First, you write the 'source partition' for your word:

[C,B,A]
[3,2,1]  <-- this is the `source partition`

Note that the source partition provides for 1 triple, 1 double, and 1 single. Corresponding to that, you write every possible 'target partition' of 4-letters.

[3,1]    requests one triple and 1 single
[2,2]    requests 2 doubles
[2,1,1]  requests one double and 2 singles

For each 'target partition', you write an expression that gives the number of ways that the given target type can occur. An example of the target type [3,1] is:

CCBC                                   # type [3,1]

The expression for that type is:

nCr(1,1)*nCr(2,1) * fac(4)/fac(3)

'nCr( n, r)' is the function for 'combinations', which gives the number of ways you can make a unique selection from n distinct things, taking r at a time. 'fac( n)' is the function for the factorial of n.

Note that source [3,2,1] provides 1 triple, and target [3,1] requests 1 triple. Hence nCr(1,1). After the triple is used up, the source [3,2,1] can provide 2 singles, and the target [3,1] requests 1 single. Hence nCr(2,1) The call to fac(4), in each expression, always corresponds to the 4-letter word. Any division, if it occurs in an expression, corresponds to each multiple request of the corresponding target partition. That's all there is to the method, but it isn't always easy to get every last detail correct. The entire computation, as I did it in the programming language Python, follows:

# The `source partition` for the word 'ABBCCC' is:
#                 [3,2,1]
#                                                # target
w = 0                                            # ------
w += nCr(1,1)*nCr(2,1) * fac(4)/fac(3)           # [3,1]
w += nCr(2,2)          * fac(4)/(fac(2)*fac(2))  # [2,2]
w += nCr(2,1)*nCr(2,2) * fac(4)/fac(2)           # [2,1,1]
#
# The answer is 38

Combinatorics – Number of Ways to Form 4 Letter Words Using ‘RAMANA’

Suppose you have a $4$ letter string composed of, say, $1$ distinct and $3$ identical letters

There would be $\frac{4!}{1!3!}$ permutations, also expressible as a multinomial coefficient, $\binom{4}{1,3}$

Similarly, for $2$ distinct, $2$ identical, and $3$ distinct, $1$ identical,
it would be $\binom{4}{2,2}\;$ and $\binom{4}{3,1}$ respectively.

In the polynomial expression $4!(1+x/1!)^3(1+x+x^2/2!+x^3/3!)$,
the 4! corresponds to the numerator, whatever the combination; the first term in $( )$ corresponds to choosing one or more from $R,M,N$; and the other term corresponds to choosing $1,2,$ or $3 A's$

It will become evident why this approach works if we expand the first term in ( ), and compare serially with your case approach by just using the appropriate coefficients to get terms in $x^4$

$4!(1 + 3x + 3x^2 + x^3)(1 + x + x^2/2! + x^3/3!)$

To find the coefficient of $x^4$, consider the three cases that produce $x^4$

One from $R,M,N, 3A's : 4!\cdot3\cdot\frac{1}{3!} = 12$
Two from $R,M,N, 2A's : 4!\cdot3\cdot\frac1{2!} = 36$
Three from $R,M,N, 1A : 4!\cdot1\cdot 1 = 24$

Coefficient of $x^4 = 12+36+24 = 72$

We can now clearly see why the coefficient of $x^4$ in the expression automatically gives all possible permutations of $4$ letters

Best Answer

Related Solutions

Probability – How Many Distinct n-Letter Words Can Be Formed from a Set of k Letters with Repetitions?

Combinatorics – Number of Ways to Form 4 Letter Words Using ‘RAMANA’

Related Question