## Permutations with Fixed Points and Successions

Suppose we have a permutation $\sigma$ on the set $\{1, 2, \ldots, n\}$.  A fixed point of $\sigma$ is a value $i$ such that $\sigma(i) = i$.  If $\sigma(i) = \sigma(i-1)+1$, then we say $\sigma$ has a succession at $\sigma(i)$.  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 $k$ fixed points and the number of permutations with $k$ 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 $\sigma(0) = 0$, so that we allow $\sigma$ to have a succession at 1 when $\sigma(1) = 1$.  Then the following holds.

Theorem: The number of permutations with $k$ of these extended successions equals the number of permutations with $k$ 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., $\sigma = \sigma(1) \sigma(2) \cdots, \sigma(n)$.  Define $\sigma^d$ to be the permutation $\sigma(2) \cdots \sigma(n) \sigma(1)$.  Now, express $\sigma^d$ as a product of cycles of the form $(a, \sigma(a), \sigma(\sigma(a)), \ldots, \sigma^m(a))$, where $\sigma^m(a)$ is the largest element in the cycle, and where the cycles are in decreasing order by the sizes of the largest cycle values $\sigma^m(a)$.  Call this $\bar{\sigma}^d$.  Finally, define $\phi(\bar{\sigma}^d)$ to be the permutation obtained by removing the parentheses in $\bar{\sigma}^d$.  Then the set of fixed points in $\sigma$ is the equal to the set of extended succession values in $\phi(\bar{\sigma}^d)$.

Let’s take a look at our example permutation above and apply the process in both directions.  If $\sigma = 213596784$, then $\sigma^d = 135967842$.  Expressing this as a product of cycles gives us $\bar{\sigma}^d = (23567849)(1)$, and then $\phi(\bar{\sigma}^d) = 235678491$.  Comparing fixed points and successions, $\sigma$ has 3, 6, 7, 8 as fixed points, and $\phi(\bar{\sigma}^d)$ has 3, 6, 7, 8 as successions.  For an example that reverses the process, take $\phi(\bar{\sigma'}^d) = \sigma = 213596784$.  Inserting parentheses while preserving the decreasing order of the largest cycle value can be done in only one way and gives us $\bar{\sigma'}^d = (21359)(678)(4)$.  Expressing this permutation in one-line notation yields $\sigma'^d = 315497862$ and then $\sigma' = 231549786$.  We see that $\sigma$ has successions at 7 and 8, and $\sigma'$ has 7 and 8 as fixed points.

Hopefully the example shows why this process is a bijection.  If $\sigma(i) = i$ for $i > 1$ then $\sigma^d (i-1) = i$.  Converting to cycle notation places $i-1$ in front of $i$, creating a succession at $i$ 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 $\sigma$ then $\sigma^d(n) = 1$, which means that the cycle beginning with 1 and ending with $n$ is the first cycle in $\bar{\sigma}^d$, 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 $S_n$ is the number of permutations of $\{1, 2, \ldots, n\}$ with no successions, then $S_n = D_n + D_{n-1}$, where $D_n$ is the number of derangements (no fixed points) on  $\{1, 2, \ldots, n\}$.

Proof: The permutations counted by $S_n$ can be divided into two groups: those with an extended succession at 1 and those without.  The number without, by the bijection above, is $D_n$.  By removing 1 from a permutation in the group with an extended succession at 1 and reindexing we obtain a permutation on $\{1, 2, \ldots, n-1\}$ 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 $D_{n-1}$.

References

1. Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 2002.
2. 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.

This entry was posted in combinatorics, permutations. Bookmark the permalink.

### 3 Responses to Permutations with Fixed Points and Successions

1. Mike Clayton says:

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

2. mzspivey says:

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.

• Mike Clayton says:

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!