Math 2.0

Combinatorics Lemma

Permutations fixing a given set of points

Builds on PermutationDerangement

Statement

Let nn be a natural number, and let SS be a subset of [n]={1,…,n}[n]=\{1,\dots,n\}. Let N(S)N(S) be the number of permutations of [n][n] that fix every element of SS. Then N(S)N(S) depends only on the size of SS. If ∣S∣=k|S|=k, then N(S)=(n−k)!N(S)=(n-k)!.

Remarks

A permutation that fixes each point of SS is determined by its values on the other n−kn-k points. These values form an arbitrary permutation of the n−kn-k remaining points. This count is the input for the inclusion-exclusion count of derangements.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Permutation, definition, no evidence levelPermutationdefinitionDerangement, definition, no evidence levelDerangementdefinitionPermutations fixing a given set of points, statement, no evidence levelPermutations fixing a…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Permutation definition
  2. Derangement definition
  3. Permutations fixing a given set of points statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_inclusion-exclusion_derangements.ptx#L42, source/s_inclusion-exclusion_derangements.ptx:42
About this page
TagN8YF97HHQ5
URIm2://N8YF97HHQ5
Kindstatement, lemma
WritingW1 stated
MSC05A05
StatusThis copy of the site has no build data. Run m2 status N8YF97HHQ5.
UsesPermutation, Derangement
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.