How many words can you create of length 6 with given properties

combinatoricscombinatorics-on-words

How many words can you create of length 6, from the letters a, b, c
and d if

  1. you must include each letter at least once
  2. you must include each letter at least once, and a must appear exactly once.

My take:

1.a b c d _ _, I first try to find every variation of abcd fitting into 6 places, I have less elements then places so I flip the roles and think like, 6 places going into 4 elements so I get:

$P(^6_4)$

Now I multiply this by the amount of variations with repetition that abcd can take in _ _. Which is:

$$\bar{P}\binom42= n^p=4^2 = 16$$

So my answer is:

$$P\binom 64\cdot16$$

However the answer sheet tells me it's $
3*\binom6{2,2,1,1} = 540$ and I have no idea why

Best Answer

You are wrong and the answer sheet is wrong.

If every letter occurs at least once, then either

(A) One letter occurs three times and the others occur once each.

or

(B) Two letters occur twice and the other letters occur once.

  1. (A) there are four ways to pick which letter occurs three times, and then $\binom6{3,1,1,1}$ ways to order the letters.
    (B) There are $\binom{4}{2}=6$ ways to pick two letters to occur twice, and then $\binom6{2,2,1,1}$ ways to order them

  2. The second case is similar, but the number of ways of selecting the letters to occur more than once are smaller since $a$ cannot occur more than once. I will leave that to you.

When $6$ is replaced by a larger value, it is harder to enumerate cases like (A) and (B). The more advanced answer is to use “inclusion-exclusion” to count the words.

In the (1) case, the inclusion-exclusion turns into:

$$4^6-\binom{4}{1}3^6+\binom422^6-\binom431^6$$

In the (2) case it becomes:

$$6\left(3^5-\binom31 2^5+\binom321^5\right)$$

Related Question