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.

 

Advertisements
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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s