Let $S = \{a,b,c,d \}$ and $X = \{ f: S \to S \mid f \text{ is bijective and} f(x) \neq x \}$. What is $|X| = ?$ Let $S = \{a,b,c,d \}$ and $X = \{ f: S \to S \mid f \text{ is bijective and} f(x) \neq x \}$. What is $|X| = ?$
So, I see that this question has been answered before, but I wish to know specifically where my logic is going wrong. I've been thinking about this problem for awhile know and have only succeeded in doubting if I understand permutations and combinations at all.
I arrived at the correct answer by bashing: 9
Now I want to do it in a nice way.
My strategy is counting the compliment: (Total bijective function) - (Bijective functions with 4,3,2,1 fixed points).
There are 4! total bijective functions clearly.
There is 1 bijective function with exactly one fixed point.
There are 0 bijective functions with exactly three fixed points.
There are C(4,2) bijective functions with exactly two fixed points.
There are 8 bijective functions with exactly 1 fixed points.
Therefore, my final answer is: 4! - 1 - C(4,2) - 0 - 4 = 13, but this is wrong. So, where in the above am I incorrect?
Here is my reasoning. There is only 1 bijective function with four fixed points. There are no bijective functions with exactly three fixed points as otherwise the function would not be bijective. Regarding two fixed points, we simply pick pairs out of the four available variables. Hence, C(4,2). Regarding one fixed point: fix one of the variables. Then the rest of the variables have only two options to be mapped to. e.g., fix a. So we have: a->a, b->c, c->d , d->c and a->a b->d, c->b, d->b. So there are 2 bijective functions per fixed variable. So 2*4 = 8 total bijective functions with one fixed point.
EDIT: I think the issue may be with how I count the number of bijective functions with two fixed points. C(4,2) means I am "picking a two things out of 4 things". But lets translate what we are doing to actual math. There are 4! ways to list out a,b,c,d. I want to pick two of them - so lets do that. This is 43 = 4!/2! ways. Now the other two variables are the variables which are *not fixed points. However, each variable has only one one option to be mapped to. Therefore, there are 12 bijective functions with exactly two fixed points. I don't see why we would care about removing the order.
but this now means my final computation is 4! - 1 - 0 - 12 - 4 = -1.... clearly wrong.
 A: There are 4! total bijective functions.
There is 1 bijective function with exactly four fixed points.
There are 0 bijective functions with exactly three fixed points.
There are indeed C(4,2) bijective functions with exactly two fixed points.
There are 8 bijective functions with exactly 1 fixed point.
Therefore, your final answer is: 4! - 1 - C(4,2) - 0 - 8 = 9, which is what you counted.
A: Note that this problem will eventually boil down to finding the number of derangements of a set of size $4$. The table on Wikipedia does indeed give $9$ as this answer.
To try and solve it your way, rather than subtract off the number of permutations which have one fixed value, two fixed, etc, let's subtract off the ones which map $1 \to 1$, then $2\to 2$, and so on, and then apply inclusion exclusion (add back all the ones that map two elements to themselves, then subtract off all the ones that map three elements to themselves, then finally add back the identity function)
From here we get $$4! - 4(3!) + 6(2!) - 4(1!) + 1 = 24-24+12-4+1 = 9$$
