1
$\begingroup$

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.

  • 1
    Your final version is correct. This is the [inclusion-exclusion principle](http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) for three sets.2012-04-05

1 Answers 1

2

Try using the inclusion-exclusion principle. Apply the formula on the wikipedia page to find the size of $A_1 \cup A_2 \cup A_3$ where $A_i$ is the set of permutations $x$ with $x(i)=i$. If you don't see why this formula holds, draw a Venn diagram with three sets intersecting.