2
$\begingroup$

How do I find the number of permutations of the digits 1 through 9 in which none of the blocks 34, 45 and 738 appears?

I know that I can probably brute force the solution, but is there a concept I can apply here that makes finding the solution quicker?

ATTEMPT AT SOLUTION:

The total number of permutations of digits 1 through 9 is $9!$

The block 34 can occur in $8!$ ways if we treat "34" as a single symbol in an 8 digit alphabet. Similarly, the block 45 can occur $8!$ ways and the block 738 can occur $7!$ ways.

*The blocks 34 and 45 can both occur together if the block 345 is in the permutation. This can occur $7!$ times.
The blocks 34 and 738 cannot both occur together since 3 can only be used once.
The blocks 45 and 738 can occur together $6!$ ways by treating 34 and 738 as single symbols in a 6 digit alphabet.

The blocks 34, 45, and 738 cannot all occur together.

Therefore, by Inclusion-Exclusion, the total number of permutations satisfying the conditions is given by: $$9! - (8! + 8! + 7!) + (7! + 0 + 6!) - (0) = 282,960$$

Does my logic look alright? Particularly the line denoted by the asterisk *.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

It would probably make sense to instead construct all permutations of the digits 1 through 9 in which the blocks 34, 45, and 738 appears, then subtract that quantity from the total number of permutations, but you have to do so being aware of the potential overlaps.

More formally, as suggested by N. F. Taussig, the Inclusion-Exclusion Principle.

$\endgroup$
2
  • 1
    $\begingroup$ Could you guys take a look at my attempt at the solution and see if the logic looks correct? I appreciate it. I feel that there is potential overlap @AmitSaxena $\endgroup$
    – vyxl
    Commented Nov 20, 2015 at 19:46
  • $\begingroup$ Oh, I didn't know you were going till 9 digits. The logic is correct. :) $\endgroup$ Commented Nov 21, 2015 at 8:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .