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

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$$

$$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

• What is $V?{}{}{}$ Commented May 23, 2021 at 16:38
• Permutation, I'll change it. (I was using the notation my teacher showed me, but I guess it's not that common) Commented May 23, 2021 at 16:39
• The answer $\binom{6}{2, 2, 1, 1}$ counts those arrangements in which two letters each appear twice and two other letters each appear once. However, it does not count those arrangements in which one letter appears three times and each of the letters appears once. Commented May 23, 2021 at 16:45
• You are going to get a lot of over counting your way. For example setting up BA-D-C and filling in $BA\color{red}BD\color{red}AC$ will give the same result as setting up --BDAC and filling in $\color{red}B\color{red}ABDAC$. In fact you will count $BABDAC$ four separate times. Commented May 23, 2021 at 16:51
• @fleablood omg thank you so much, I didn't see that! I was mainly angry due to not understanding my mistake. Commented May 23, 2021 at 16:53

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)$$

• Answer sheet is indeed wrong, I literally copied the question, but in the answer sheet it was stated that they had to use different letters (while it wasn't stated in the question sheet), that's why they only had 3*(^6_{3,1,1,1}) without adding the possibilities with repetition. Commented May 23, 2021 at 17:25
• " but in the answer sheet it was stated that they had to use different letters" I don't think that is meaningful or at all clear. If you can only choose from four letters and you choose six of them then you can't use "different" letters. some letters must be repeated. If they are assuming no letter may be repeated more than once again... well, that's a heck of an unverified assumption. Commented May 23, 2021 at 18:35
• I think OP meant “different letters for repetition.” That is, they didn’t count the case where one letter occurs three times. It would explain the result $3\cdot\binom6{2,2,1,1}=540.$ @fleablood Commented May 23, 2021 at 18:39
• "I think OP meant “different letters for repetition.”" Yes.. that is a very clear way of stating what I was intuitively trying to express. But I still maintain that that is a very unwarranted assumption... Commented May 23, 2021 at 19:03
• Actually it would be interesting to try to calculate this the OPs way and dividing by the factor of overcounting. If two different letters are repeated you are over counting by 4, and if one letter is repeated you are over counting by 3. If I'm not mistaken (I'm not actually combing it out) there would be ${6\choose 4}\times 4!(\frac {12}4+ \frac 43)$ total. I'll let someone verify if I am right or complete talking out of my hat. Commented May 23, 2021 at 19:07

Your solution involves double counting. To show this, take a string $$ABCAAD$$. For the sake of clarity, let the a's be numbered i.e. the string becomes $$A_1BCA_2A_3D$$. Then you have 3 ways of making this string:

1. $$A_1BC--D$$
2. $$-BCA_2 -D$$
3. $$-BC\_ A_3D$$

Thus, this string is counted 3 times.

Also, when you select the positions for the initial $$4$$ letters, you make a combination, which does not tell the position of an individual letter.

To count the number of strings correctly, take two cases:

Case A: 3 of one type, 1 of others

Choose the letter appearing thrice in $$4$$ ways and select its positions in $$20$$ ways. Now permute the other $$3$$ letters in $$6$$ ways. So we get $$4 \times 20 \times 6 = 480$$

Case B: 2 of one type, 2 of second type, 1 of others

Choose the letters appearing twice in $$6$$ ways and select their positions in $$15 \times 6$$ ways. Permute the other two letters in $$2$$ ways. So we get $$6 \times 15 \times 6 \times 2 = 1080$$

In total we get $$1560$$ ways to make the word.

• This answer outputs 480 which is false, it should be 540 Commented May 23, 2021 at 17:19
• @Betraxa This is a correct answer to the first part of the question. Commented May 23, 2021 at 17:26
• @N.F.Taussig answer by Thomas Andrews gives 900 not 1560. Commented May 23, 2021 at 17:32
• @Betraxa Thomas Andrews' answer does indeed give $1560$. \begin{align*} 4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 -\binom{4}{3}1^6 & = 4096 - 4 \cdot 729 + 6 \cdot 64 - 4 \cdot 1\\ & = 4096 - 2916 + 384 - 4\\ & = 1560 \end{align*} His other method also gives $1560$. \begin{align*} 4\binom{6}{3, 1, 1} + 6\binom{6}{2, 2, 1, 1} & = 4 \cdot \frac{6!}{3!1!1!1!} + 6\frac{6!}{2!2!1!1!}\\ & = 4 \cdot 120 + 6 \cdot 180\\ & = 480 + 1080\\ & = 1560 \end{align*} Commented May 23, 2021 at 17:40
• Oh I miscalculated, indeed this answer is right too. Commented May 23, 2021 at 17:50

Apparently, I misinterpreted the question. I thought that there was only a single question, with two constraints.

Therefore, the kludgy analysis below only applies to the 2nd question, which prohibits having more than 1 "a".

In my opinion, the easiest way to attack this problem is by examining separate cases.

You start with a,b,c,d,-,- in some order. The first thing to do is identify the mutually exclusive ways that the two -,- slots can be filled in. Either both slots are the same letter, or they are not.

$$\underline{\text{Case 1: both slots are the same letter}}.$$
There are 3 choices for the triplet, either b, c, or d.
Without loss of generality, assume a triplet of b,b,b.

Then, you have to determine how many distinct permutations of a,c,d,b,b,b that there are.
The "a" can go in 6 slots.
Then, the "c" can go in 5 slots.
Then, the "d" can go in 4 slots.

Therefore, once the "b" triplet is decided, the 6 letters can be arranged in $$\frac{6!}{3!}$$ ways.

Therefore, the computation for Case 1 is

$$T_1 = 3 \times \frac{6!}{3!}.$$

$$\underline{\text{Case 2: the two slots are different letters}}.$$
There are 3 choices for which letter will not be paired, either b, c, or d.
Without loss of generality, assume that d is not paired, so the collection of letters is a, b,b, c,c, d.

Then, you have to determine how many distinct permutations of a, b,b, c,c, d that there are.
The "a" can go in 6 slots.
Then, the "d" can go in 5 slots.

Then, the "b,b" can go in $$\binom{4}{2}$$ slots.

Therefore, once the lone "d" is decided, the 6 letters can be arranged in $$\frac{6!}{4!} \times \binom{4}{2}$$ ways.

Therefore, the computation for Case 2 is

$$T_2 = 3 \times \frac{6!}{4!} \times \binom{4}{2}.$$

Therefore, the final computation is

$$T_1 + T_2.$$

• @N.F.Taussig Thomas Andrews answer is allowing the "a" to occur more than once. This is prohibited by the constraints of the problem. Commented May 23, 2021 at 17:14
• For the first part of the question, you are not restricted to use 1 a, it is stated in the question. Commented May 23, 2021 at 17:18
• @Betraxa Apparently, I misinterpreted the question. I thought that there was only a single question, with two constraints. I will edit my answer accordingly. Commented May 23, 2021 at 17:20

Just for shigs and gittles:

Select $$4$$ slots for the four letters that must occur. (Ex. x-xx-x). There are $${6\choose 4} = 15$$ ways to do that.

Select a permutation of $$A,B,C,D$$ for the occupied slots. (Ex. D-AC-B). There are $$4!= 24$$ ways to do that.

There are $$4^2 = 16$$ ways to choose the remaining letters but that double counts. Ex. $$D\color{red}BAC\color{red}AB$$ will be the same as first choosing xx-xx- first; permuting DB-CA- and choosing $$DB\color{blue}ACA\color{blue}B$$. If we choose $$2$$ different letters to be repeated, we are over counting by $$2^2 = 4$$ because there are two positions for each letter that could be the "original" position. If we choose $$1$$ letter to be repeated three times, we are overcounting by $$3$$ (as there are three positions that could be the "original").

Of the $$16$$ ways to choose the remaining two letters there are $$4$$ ways to choose the the same letter twice. And $$16-4 =12$$ ways to pick two different letters.

So taking into account over counting there ought to be

$${6\choose 4}\times 4! (\frac {12}4 + \frac {4}3)=$$

$$15\cdot 24(3+\frac 43)=$$

$$15\cdot 24\cdot 3 + 15\cdot 8\cdot 4=$$

$$15\cdot 8\cdot(9+4)= 120\cdot 13= 1560$$ ways to do it.

=====

That was an alternative (for "shigs and gittles"). I really do not recommend doing it this way. gabrupo or Thomas Andrew both really have the best way to do it.