Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Your final version is correct. This is the inclusion-exclusion principle for three sets. –  Brian M. Scott Apr 5 '12 at 23:58
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.