Involution Number

Count permutations of n labeled elements consisting only of fixed points and transpositions exactly, including the empty involution; n is capped at 2,000.

Description

An involution is a permutation that becomes the identity when applied twice.

An involution is a permutation that becomes the identity when applied twice. Its cycles consist only of fixed points and two-element transpositions.^[1]

The tool returns value. The indexing and output conventions below determine how to read these values.

When to use Involution Number

Use this for the following task: Count permutations of n labeled elements consisting only of fixed points and transpositions exactly, including the empty involution; n is capped at 2,000. Use the input and output conventions below to reproduce the intended mathematical quantity.

How to use Involution Number and understand its results

Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
Enter n according to the field table, then run the tool.
Read value. Preserve exact decimal strings and the stated indexing or coefficient order.
Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.

Input field	Meaning	Value type and bounds	Requirement
n	Permutation size (resource limit 2000)	integer; minimum 0; maximum 2000	Required

Maintain the previous two BigInt counts and apply the recurrence through the supplied set size. Return an exact decimal string.

I(0)=I(1)=1; I(n)=I(n−1)+(n−1)×I(n−2)

The symbols and boundary conditions refer to the supplied fields and the implementation described above.

Output field	Meaning	Value type
value	Involution count	string (integer/arbitrary)

json

{
  "input": {
    "n": 6
  },
  "output": {
    "value": "76"
  }
}

Limitations and assumptions

The size is at most 2000. The empty involution counts as one; permutations are counted without enumeration or restrictions on the number of fixed points.

Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.

Alternative or Complementary methods

Choose Rencontres Number when you need its operation: Count permutations of n labeled elements with exactly k fixed points using C(n,k)·D(n−k), returning zero for k>n; indices are capped at 1,000. Choose Derangement Number for the complementary operation: Count permutations of n labeled elements with no fixed points exactly, including one empty derangement; n is capped at 2,000.

Background reference: OEIS A000085.

References

OEIS A000085 — OEIS Foundation

Similar or alternative tools

Rencontres Number
Count permutations of n labeled elements with exactly k fixed points using C(n,k)·D(n−k), returning zero for k>n; indices are capped at 1,000.
Derangement Number
Count permutations of n labeled elements with no fixed points exactly, including one empty derangement; n is capped at 2,000.