# Permutation of a multiset with restrictions on two characters.

Consider the following: apples?and?oranges.

I have to find the number of arrangements with the restriction that the two ? can't be together and they can't be located at the ends like ?applesandoranges?. In other words, there must 3 words(words don't have to mean anything) with at least 1 letter.

My solution: Let T be the number of permutations without any restrictions. Let S be the number of arrangements where the two ? are together and let R be the number of arrangements with the two ? at the ends.

Since we are finding the arrangements of the multiset $X = \{3*a, 2*p, 2*n, 2*e, 1*l, 2*s, 1*d, 1*o, 1*r, 1*g, 2*?\}$ and $|X| = 18$ then

T = $\frac{18!}{3!2!2!2!2!2!}$

S = $\frac{17!}{3!2!2!2!2!}$ (The divisor has one less 2 because the two ? are being considered as one character so their permutation is not being considered )

R = $\frac{16!}{3!2!2!2!2!}$ (The two ? are not being considered at all here)

Number of arrangements = T -(R+S)

Did I overlook something? I'd appreciate some feedback.

EDIT: I will add the restriction that each word must be distinct.

Thank you.

• What about cases where you have a ? at one end like in the example case ??applesandoranges or the case ?applesand?oranges. Don't you want to subtract those too? Be careful of you do because they overlap with some of your previous ones. – N. Shales Mar 1 '18 at 2:15
• The first case you mentioned is covered by S because S counts the arrangements where you have ??. Or am i missing something there too? Ahh I did not think about the second case you pointed ou. I will redo this. – rachelhoward Mar 1 '18 at 2:20
• There is a much easier way: Ignore the ?s to begin with and just count the ways of arranging the 16 letters. Then, for each arrangement, choose 2 of the 15 gaps between letters to place the ?s – N. Shales Mar 1 '18 at 2:24

The easy way to do this is to arrange the $16$ letters in $16!/(3!2!^4)$ ways then, for each, choose $2$ of the $15$ gaps between letters to place the ?s in $\binom{15}{2}$ ways.

$$\frac{16!}{3!2!^4}\binom{15}{2}\tag{Answer 1}$$

Alternatively we can push through with your method and create $3$ overlapping sets of arrangements $L$ (the set where a ? is on the left), $R$ (the set where a ? is on the right) and $T$ (the set where ?? are together).

It should be clear that

$$|L|=|R|=|T|=\frac{17!}{3!2^4}$$

and that their intersections have

$$|L\cap R|=|L\cap T|=|R\cap T|=\frac{16!}{3!2!^4}$$

and

$$|L\cap R\cap T|=0$$

then the number of "bad" arrangements is

$$|L|+|R|+|T|-|L\cap R|-|L\cap T|-|R\cap T|+|L\cap R\cap T|= 3\left(\frac{17!}{3!2^4}-\frac{16!}{3!2!^4}\right)$$

which means the number of "good" arrangements is

$$\frac{18!}{3!2!^5}-3\left(\frac{17!}{3!2^4}-\frac{16!}{3!2!^4}\right)\tag{Answer 2}$$

• Actually, I don't think it's all that bad (for this example anyway). There are 9 mutually exclusive cases to consider so we don't even need to use inclusion-exclusion as I originally thought. I calculate a total of $127\,863\,360$ arrangements with repeat words. – N. Shales Mar 2 '18 at 14:44