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 *.
Best Answer
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.