# Homework Help: Determine the order of a subset of S_n

1. Oct 11, 2014

### minor_embedding

1. The problem statement, all variables and given/known data
We have a set S = {a,b,c,d} and a set X such that X = {$f:S \rightarrow S|$ f is bijective and $f(x) \neq x$ for each $x \in S$}. What is the order of the set?

2. Attempt at Solution/My Reasoning

The order of the set of all bijective functions is simply the 4!. There is one element of set of all bijective functions such that f(x) = x, so we subtract 1 from the order of that set.

Now we keep one element set equal to itself and find all functions such that only that element returns itself. Then you have 3 spots in which the other elements can be mapped to. However, you don't want an element to be mapped to itself so you only have 2 ways in which you can complete this. So you have ${4 \choose 3} \cdot 2!$ ways in which you can do this. Where ${4 \choose 3}$ is the number of ways you can choose that one element.

Next we keep two elements equal to themselves and find all functions where the other two are not. So we have only 1 way in which they can be mapped so then we have ${4 \choose 2} \cdot 1!$ functions such that this is true.

In total we should have 9 functions that satisfy the requirements of X. Is my way of thinking about this right? How can we generally determine the order of this subset of functions?

2. Oct 11, 2014

### Dick

Yes, it's correct. Permutations like this are called 'derangements'. You can Google that if you want the general case.