# Cycles in permutations of a given size

How would I find the number of permutations of $[n]$ in which all cycles have length $1$ or $2$?

I know how to do this if I have, say, $8$ numbers from ${{1,2,3,...,8}}$ and I want them to be broken into Count$(4, 3, 1)$. But not when I don't know how many cycles of $2$ and $1$ I want.

Note: I'm looking for a way to derive a formula or something. I need to use it to prove by induction, I'm assuming, $r(n + 1) = r(n) + n · r(n − 1)$.

-
Is $[n] = \{1, 2, \cdots, n\}$? – user123454321 Jan 28 '13 at 3:36
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$. – Erick Wong Jan 28 '13 at 3:39
@GilYoungCheong: yes! – MITjanitor Jan 28 '13 at 3:44

## 1 Answer

These permutations are involutions, meaning $\sigma \in S_n$ with $\sigma^2=1$.

Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496

• a(n) is also the number of matchings in the complete graph K(n).
• a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
• a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
• a(n) = a(n-1) + (n-1)*a(n-2)
-
Involutions are not cycles, are they? Let me know if I am not right about this! – user123454321 Jan 28 '13 at 3:43
Oops. I misunderstood the question! – user123454321 Jan 28 '13 at 3:44