Suppose we have a permutation on the set . A fixed point of is a value such that . If , then we say has a succession at . Take, for example, the permutation 213596784. It has four fixed points: 3, 6, 7, and 8. It has two successions: at 7 and 8.
It turns out that there is a close relationship between the number of permutations with fixed points and the number of permutations with successions (which I would not have guessed). It’s not that a permutation has the same number of fixed points as it does successions; that doesn’t make sense, and we can see it from the example above anyway. However, suppose we extend the definition of succession and define , so that we allow to have a succession at 1 when . Then the following holds.
Theorem: The number of permutations with of these extended successions equals the number of permutations with fixed points.
Why is this? It turns out that there is a bijection between the two sets, which I first learned of by reading a paper of Clarke, Han, and Zeng . Suppose we have a permutation expressed in one-line notation; i.e., . Define to be the permutation . Now, express as a product of cycles of the form , where is the largest element in the cycle, and where the cycles are in decreasing order by the sizes of the largest cycle values . Call this . Finally, define to be the permutation obtained by removing the parentheses in . Then the set of fixed points in is the equal to the set of extended succession values in .
Let’s take a look at our example permutation above and apply the process in both directions. If , then . Expressing this as a product of cycles gives us , and then . Comparing fixed points and successions, has 3, 6, 7, 8 as fixed points, and has 3, 6, 7, 8 as successions. For an example that reverses the process, take . Inserting parentheses while preserving the decreasing order of the largest cycle value can be done in only one way and gives us . Expressing this permutation in one-line notation yields and then . We see that has successions at 7 and 8, and has 7 and 8 as fixed points.
Hopefully the example shows why this process is a bijection. If for then . Converting to cycle notation places in front of , creating a succession at when the parentheses are removed. Writing the cycles in decreasing order by largest value ensures that no additional successions are introduced when the parentheses are removed. Finally, if 1 is a fixed point in then , which means that the cycle beginning with 1 and ending with is the first cycle in , yielding 1 as a fixed point when the parentheses are removed. Reversing the process turns extended successions into fixed points.
All of this gives a combinatorial explanation of a result I came across in Charlambides’s Enumerative Combinatorics [1, p. 178] while thinking about my answer to “the number of permutations with no successions” on math.SE:
Theorem: If is the number of permutations of with no successions, then , where is the number of derangements (no fixed points) on .
Proof: The permutations counted by can be divided into two groups: those with an extended succession at 1 and those without. The number without, by the bijection above, is . By removing 1 from a permutation in the group with an extended succession at 1 and reindexing we obtain a permutation on with no extended successions. Thus the number of permutations with an extended succession at 1 but no successions elsewhere, by the bijection above, is equal to .
- Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 2002.
- Robert J. Clarke, Guo-Niu Han, and Jiang Zeng, “A combinatorial interpretation of the Seidel generation of q-derangement numbers,” Annals of Combinatorics 4 (1997), 313-327.