3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – N. Shales Mar 1 '18 at 2:15
  • $\begingroup$ 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. $\endgroup$ – rachelhoward Mar 1 '18 at 2:20
  • $\begingroup$ 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 $\endgroup$ – N. Shales Mar 1 '18 at 2:24
2
$\begingroup$

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

check that these answers match.

$\endgroup$
  • 1
    $\begingroup$ and what if each word had to be distinct? $\endgroup$ – rachelhoward Mar 1 '18 at 5:23
  • $\begingroup$ @rachelhoward, that's a good question. I think I would have to use inclusion-exclusion and count the cases where words are repeated then subtract them from the total. Notice that you can only have 2 repeated words, and they must come from the set of double and triple letters. $\endgroup$ – N. Shales Mar 1 '18 at 11:44
  • $\begingroup$ Yes but there would be a lot of cases to consider. Like repeated words with 1 and 2 letters of the repeated 6 letters.... each would change the value of the divisor. It could be done but sounds tedious....hmmm $\endgroup$ – rachelhoward Mar 1 '18 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$ – N. Shales Mar 2 '18 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.