I've been given the following as a homework problem:
Say you have a group of 12 integers, numbered 1 through 12 (1, 2, ...) Permutations are represented as such: The permutation in the first position is X(1). Thus, if X(1) = 3, our permutation looks like (3, ...). How many permutations are there such that X(1) = 1 or X(2) = 2 or X(3) = 3?
To try to figure this out, I started by considering a group of just 3 numbers, (1, 2, 3). In that group, there are 3! = 6
permutations, and 4 of them satisfy this condition. My intuition then, with the set of three, is that the number of permutations is 4 = 2! + 2! + 2! - 2
(2! each for the permutations where X(1) = 1, X(2) = 2, X(3) = 3).
However, these events aren't mutually exclusive, and I'm having trouble where the "- 2" comes from. It's NOT the permutations where
X(1) = 1 and X(2) = 2 and X(3) = 3
,
since that = 1
.
It's also not the permutations of each pair added together
[X(1) = 1 and X(2) = 2] + [X(1) = 1 and X(3) = 3] + [X(2) = 2 and X(3) = 3]
since that = 3
.
It seems like it's the permutations where
[X(1) = 1 and X(2) = 2] + [X(1) = 1 and X(3) = 3] + [X(2) = 2 and X(3) = 3] - [X(1) = 1 and X(2) = 2 and X(3) = 3]
since that = 2 = 1! + 1! + 1! - 0!
. This seems kind of complex though....is this final intuition the correct one? Or where am I going wrong with my logic?
P.S. - This is HW so I'm not looking for the numerical solution to the problem.