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 [2]. 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 .

**References**

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

Hello Mike,

Thanks for posting this, and also for your 2010 paper in The College Mathematics Journal, and your 2011 Stack exchange note. All very interesting, and just what I needed to help me along recently when I was considering incomplete derangements.

My interest arose in connection with my volunteering at Bletchley Park, where I host student parties that visit the museum. I wanted to quantify how the Germans had actually helped the BP codebreakers by restricting the ‘legal’ assignments for rotor choice on the Enigma settiings sheets – for some networks, they decreed that no rotor should occupy the same position in the machine on two successive days.

I have subsequently written a couple of notes to document things for myself – nothing novel, I’m sure, but they include a few bits on generating functions that you might find interesting. Please say if you would like to see them.

Thanks again for publishing your material.

Mike

Thanks for your interest in my work. Sure; I’d be glad to take a look at your notes. You can track down my email address via my university affiliation.

Thanks for your interest, Mike – I have just sent off an email to your university address attaching my notes. Very sorry for the delay – I was waiting hopefully for an email and hadn’t thought to look here for your reply!