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.

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)$.

share|improve this question
    
Is $[n] = \{1, 2, \cdots, n\}$? –  GYC Jan 28 '13 at 3:36
1  
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 1

up vote 2 down vote accepted

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)
share|improve this answer
    
Involutions are not cycles, are they? Let me know if I am not right about this! –  GYC Jan 28 '13 at 3:43
    
Oops. I misunderstood the question! –  GYC Jan 28 '13 at 3:44

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.