Editing Involution (mathematics) (section)

== Involutions on finite sets ==
The number of involutions, including the identity involution, on a set with {{math|1=''n'' = 0, 1, 2, ...}} elements is given by a [[recurrence relation]] found by [[Heinrich August Rothe]] in 1800:
: <math>a_0 = a_1 = 1</math> and <math>a_n = a_{n - 1} + (n - 1)a_{n-2}</math> for <math>n > 1.</math>
The first few terms of this sequence are [[1 (number)|1]], 1, [[2 (number)|2]], [[4 (number)|4]], [[10 (number)|10]], [[26 (number)|26]], [[76 (number)|76]], [[232 (number)|232]] {{OEIS|id=A000085}}; these numbers are called the [[Telephone number (mathematics)|telephone numbers]], and they also count the number of [[Young tableau]]x with a given number of cells.<ref>
{{citation
 | last = Knuth | first = Donald E. | author-link = Donald Knuth
 | location = Reading, Mass.
 | mr = 0445948
 | pages = 48, 65
 | publisher = Addison-Wesley
 | title = [[The Art of Computer Programming]], Volume 3: Sorting and Searching
 | year = 1973
}}</ref>
The number {{math|''a''{{sub|''n''}}}} can also be expressed by non-recursive formulas, such as the sum
<math display="block">a_n = \sum_{m=0}^{\lfloor \frac{n}{2} \rfloor} \frac{n!}{2^m m! (n-2m)!} .</math>

The number of fixed points of an involution on a finite set and its [[Cardinality|number of elements]] have the same [[parity (mathematics)|parity]]. Thus the number of fixed points of all the involutions on a given finite set have the same parity. In particular, every involution on an [[odd number]] of elements has at least one [[Fixed point (mathematics)|fixed point]]. This can be used to prove [[Fermat's theorem on sums of two squares#Zagier's "one-sentence proof"|Fermat's two squares theorem]].<ref>
{{citation
 | last = Zagier | first = D. | author-link = Don Zagier
 | doi = 10.2307/2323918
 | issue = 2
 | journal = [[American Mathematical Monthly]]
 | mr = 1041893
 | page = 144
 | title = A one-sentence proof that every prime ''p'' ≡ 1 (mod 4) is a sum of two squares
 | volume = 97
 | year = 1990
 | jstor = 2323918
}}.</ref>