I am looking to solve this problem:
A permutation $\alpha$ on the set $\{1, 2, . . . , n\}$ is an involution if $\alpha^2 (i)=i$ for all $i = 1,2,\ldots,n$. An element is a fixed point of $\alpha$ if $α(i)=i$. Use exponential generating function to find the number of fixed-point-free involutions on the set $\{1,2,\ldots,2m\}$.
Firstly, I am a bit confused as to the definition of an involution. I see online that an involution is a permutation that is it's own inverse, but I am not quite clear on what that means exactly. I saw somewhere that, for example, "the four involution permutations on $3$ elements are $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, and $\{3,2,1\}$." Is there a reason that $\{2,3,1\}$ and $\{3,1,2\}$ are excluded from this list?
Any guidance on the definition of an involution as well as how to solve this problem would be appreciated.
Best Answer
An involution is a permutation that is its own inverse, but that can be a bit hard to parse at first. Let's see a concrete example:
The map $x \mapsto -x$ from $\mathbb{Z} \to \mathbb{Z}$ is an involution. Intuitively why? Because we flip $\mathbb{Z}$ across $0$. Formally why? Because if we apply this transformation twice, we have $-(-x) = x$, and we've gotten back where we started. This is the defining characteristic of an involution: we can flip once, but if we flip again we get back where we started.
(As a quick exercise: consider the $8$ symmetries of a square. Which ones are involutions? The answer is below the fold.)
Every involution pairs up an element with somebody else, just look to see who you get flipped to. So the $x \mapsto -x$ involution from earlier pairs $1$ with $-1$, $2$ with $-2$, etc... Except there's a special point: $0$ gets paired with itself! We say that $0$ is a fixed point of the involution, and these are very special. Fixed points hold the answer to lots of counting problems, but I digress.
In this problem, we want to count the number of involutions where everybody gets a friend. That is, we want our involution to have no fixed points.
(As another quick exercise, can you come up with a fixed point-free involution on $\mathbb{Z}$? Again, I'll include one under the fold)
Now, it should be clear that a fixed point free involution (on a finite set) can only exist if we're permuting an even number of things. After all, if everyone has a friend, then we have $2m$ many elements where $m$ is the number of pairs. For your example of involutions on a $3$ element set, notice we can:
At this point, can you answer your own question about why the remaining two permutations are not involutions?
Ok, on to the main point of your question. How can we count the number of fixed point free involutions on the set $[2m] = \{1,2,3,\ldots,2m-1, 2m\}$? It's hard to know precisely how to answer this without knowing what aspects of exponential generating functions you've seen. But here's one approach which is hinting at the idea of species. I'm going to be somewhat quick with my description (this answer is already quite long), but you can read more in these excellent notes.
We know that an involution without fixed points divides a set into pairs. Conversely, if we divide a set into pairs, then we get a unique involution by swapping the two paired elements.
So we want to partition $2m$ into blocks of size $2$. In terms of "structure" (again, see the linked notes), this means we want to
But this nested notion of putting structure on blocks, each of which has structure is exactly where exponential generating functions show their full power! This maneuver corresponds to the composition of generating functions!
In particular, "I have $2$ elements" is expressed by the exponential generating function $\frac{x^2}{2!}$ (do you see why?). Then "I have no structure" is expressed by $e^x$ (again, do you see why?)
So now, by the composition theorem for exponential generating functions, we see the number of ways to divide $m$ objects into blocks of size $2$ is the composite of the above functions. That is, $e^{\frac{x^2}{2}}$. Indeed, we can check that
$$e^{\frac{x^2}{2}} = 1 + \frac{x^2}{2!} + 3 \frac{x^4}{4!} + 15 \frac{x^6}{6!} + 105 \frac{x^8}{8!} + \ldots$$
which matches what we expect for small values of $m$.
I hope this helps ^_^