1
$\begingroup$

This issue is in the section of my textbook that deals with the inclusion-exclusion principle. I don't see how to apply it here. Any tips?

Determine the number of simple permutations of the nine digits 1,2,. . . ,9 in which blocks 12, 34, and 567 do not appear.

$\endgroup$
1
  • $\begingroup$ Try counting instead the permutations where at least one of the blocks 12, 34, 567 do appear. To do so, it might be helpful to replace one or more of the blocks as a whole with a single letter. $\endgroup$
    – JMoravitz
    Nov 4, 2019 at 20:40

1 Answer 1

Reset to default
0
$\begingroup$

There are $9!$ permutations in all. If $1,2$ are adjacent, consider them as a block; then there are $8!$ permutations of the resulting objects ($7$ remaining numbers, one block). Likewise, if $5,6,7$ are adjacent, there are $7!$ permutations of the resulting objects ($6$ remaining numbers, one block). To count the permutations in which several of the patterns appear, join each of them into a block. The result is

$$ 9!-8!-8!-7!+7!+6!+6!-5!=283560\;. $$

$\endgroup$

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.