Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if certain words may not appear as subwords.

Question

Good evening, any solutions or tips for this problem?

Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if none of the words $RET$, $SEK$ or $DIS$ may appear as subwords.

Answer 1

Hint:

Since there are no repetitions in the letters DISKRET, the total amount of words is 7!, or 5040. Now try eliminating the incorrect words from the total.

Solution:

Let's join RET, SEK, and DIS into single letters, so that in any arrangement, they always are together, making a subword. This gives of $3*5!$, or 360 faulty arrangements. This means there are $5040-360=4680$ combinations.

However, we have not yet calculated the amount of double counting that occured during elimination, as some sets had two of the three words chosen for elimination, and were eliminated twice! RET and SEK share the letter "E" in the middle, so it's impossible for them to be in the same word, but the other combinations are still to be evaluated.

For words with both RET&DIS, we combine each of the three letters into new letters, and there are 3! = 6 combinations that have both these words. Thus, we need to add 6 of these back to account for the overcounting. This leaves us with 4686 combinations.

For words with both DIS&SEK, the letter "S" is shared between the two words, meaning however they appear must be in the form DISEK. We merge the five letters again, and calculate that there were 3! = 6 overcounts. $4686+6=4692$.

We do not need to worry about situations where all three words are in the arrangement, since we've already proven that RET and SEK cannot appear in the same word. Therefore, our final answer would be 4692.