Derangements and Relative Derangements of Type B

William Y.C. Chen^{1} and Jessica C.Y. Zhang^{2}

Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071, P. R. China

1chen@nankai.edu.cn, ^{2}zhangcy@mail.nankai.edu.cn

Abstract

By introducing the notion of relative derangements of type B, also called signed relative derangements, which are defined in terms of signed permutations, we obtain a type B analogue of the well-known relation between relative derangements and the classical derangements. While this fact can be proved by using the principle of inclusion and exclusion, we present a combinatorial interpretation with the aid of the intermediate structure of signed skew derangements.

AMS Subject Classification: 05E15, 05A05

Keywords: signed permutations, relative derangement of type B, signed derangement, signed skew derangement

1 Introduction

A derangement on a set [n] = {1, 2, ⋯, n} is a permutation π = π_{1}π_{2} ⋯ π_{n} such that π_{i} ≠ i for all i ∈ [n]. A relative derangement π_{1}π_{2} ⋯ π_{n} on [n] is a permutation such that π_{i+1} ≠ π_{i} + 1 for 1 ≤ i ≤ n − 1. Let Q_{n} denote the number of relative derangements on [n], and let D_{n} denote the number of the derangements on [n]. The following relation is well-known, see Brualdi [2, Theorem 6.5.1], or Andreescu and Feng [1, Example 6.11]:

Q_{n} = D_{n} + D_{n−1}.  (1.1)

A combinatorial interpretation of (1.1) has been obtained by Chen [3] based on the intermediate structure of skew derangements, which are equivalent to the generalized derangements as studied by Hanson, Seyffarth and Weston [5] and Wang [8]. The main objective of this paper is to present a type B analogue of (1.1). This goal is achieved by introducing the notion of signed relative derangements, or relative derangements of type B. The concept of derangements of type B is introduced by Chow [4]. A signed permutation π on [n] can be viewed as a bijection on the set {¯1, ⋯, n̄, 1, ⋯, n} such that π(ī) = \overline{π(i)}. Intuitively, a signed permutation on [n] is just an ordinary permutation π_{1}π_{2} ⋯ π_{n} with some elements associated with a bar −. For example, 3 ¯2 ¯5 1 ¯4 is a signed permutation on {1, 2, 3, 4, 5}. The set of signed permutations on [n] is often denoted by B_{n}. The following order relation is often imposed on the elements of signed permutations for B_{n}, see, for example, Shareshian and Wachs [7]:

¯1 < ¯2 < ⋯ < n̄ < 1 < 2 < ⋯ < n.  (1.2)

According to the above ordering, for the above signed permutation 3 ¯2 ¯5 1 ¯4, 3 is the largest element and ¯2 is the smallest. We recall the following definition of derangements of type B.

Definition 1.1. A derangement of type B on [n] is a signed permutation π_{1}π_{2} ⋯ π_{n} such that π_{i} ≠ i, for all i ∈ [n].

For example, 3 ¯2 ¯5 1 ¯4 is a derangement in B_{5}, whereas 3 2 ¯4 1 ¯5 has a fixed point 2. Let D_{n}^{B} denote the number of derangements of type B on [n]. It is not hard to derive the following formula by using the principle of inclusion-exclusion [4, Chapter 2]:

D_{n}^{B} = n! ∑_{k=0}^{n} \frac{(−1)^{k} · 2^{n−k}}{k!}  (1.3)

In fact, it is also a consequence of the q-analogue given by Chow [4].

We now give the definition of relative derangements of type B on [n], or signed relative derangements, for short.

Definition 1.2. A relative derangement of type B on [n] is a signed permutation on [n] such that i is not followed by i + 1, and ī is not followed by \overline{i + 1}, for 1 ≤ i ≤ n − 1.

For example, 3 2 ¯4 1 ¯5 is a relative derangement in B_{5}, while 4 1 5 ¯2 ¯3 is not. Let Q_{n}^{B} be the number of relative derangements of type B. Our main result is the following type B analogue of the above relation (1.1).

Theorem 1.3. For n ≥ 2, we have

Q_{n}^{B} = D_{n}^{B} + D_{n−1}^{B}.  (1.4)

The first few values of Q_{n}^{B} starting with Q_{1}^{B} are given below:

2, 6, 34, 262, 2562, ⋯

In accordance with the relation (1.4), we adopt the convention that D_{0}^{B} = 1.

One way to prove the above result for Q_{n}^{B} and D_{n}^{B} is to derive the following formula for Q_{n}^{B} by using the principle of inclusion-exclusion:

Q_{n}^{B} = n! · 2^{n} + ∑_{k=1}^{n−1}(−1)^{k} · \binom{n − 1}{k} · (n − k)! · 2^{n−k}.  (1.5)

However, the details of the algebraic proof will be omitted. Instead, we will provide a combinatorial proof by introducing the structure of signed skew derangements.

2 Signed Skew Derangements

In this section, we first introduce the notion of signed skew derangements and establish a correspondence between signed relative derangements and signed skew derangements. Then we give a characterization of signed permutations that correspond to signed skew derangements. Then we show how to transform a signed skew derangement into a signed derangements. This leads to a combinatorial interpretation of the relation (1.4).

Recall that a skew derangement f on [n] is a bijection from [n] onto {0, 1, ⋯, n−1} with f(i) ≠ i for any i ∈ [n], see [3]. For signed permutations, we will define signed skew derangements, or skew derangements of type B. Let us begin with the definition of a signed set on [n]. A signed set on [n] can be considered the underlying set of a signed permutation. In other words, a signed set on [n] is just the set [n] with some elements bearing bars. For example, X = {1, ¯2, 3, 4, ¯5} is a signed set on {1, 2, 3, 4, 5}.

Given a signed set X on [n], we denote by X − 1 the signed set obtained from X by subtracting 1 from each element in X, where we define the subtraction for barred elements by the rule

\overline{i} − 1 = \overline{i − 1}.  (2.1)

Conversely, the addition to a barred element is given by

\overline{i} + 1 = \overline{i + 1}.  (2.2)

Definition 2.1. Let X be a signed set on [n]. A signed skew derangement on [n] is a bijection f from X to Y = X − 1 such that f(x) ≠ x for any x ∈ X, where x may be a barred element.

For example, let n = 2, X = {¯1, 2} and Y = {¯0, 1}. Then there are two signed skew derangements from X to Y: f_{1}(¯1) = ¯0, f_{1}(2) = 1 and f_{2}(¯1) = 1, f_{2}(2) = ¯0. The following theorem establishes a bijection between signed relative derangements and signed skew derangements.

Theorem 2.2. There is a one-to-one correspondence between the set of signed relative derangements on [n] and the set of signed skew derangements on [n].

Proof. First, given a signed relative derangement π = π_{1}π_{2} ⋯ π_{n} on [n], we proceed to construct a signed skew derangement f on [n]. Let u be the maximum element in the signed permutation π_{1}π_{2} ⋯ π_{n} with respect to the order (1.2). Note that in the case of signed permutations, the maximum element is not necessarily the element n. Suppose that π_{k} = u. Let us consider the segment π_{1}π_{2} ⋯ π_{k}. Define

f(π_{1}) = π_{2} − 1, f(π_{2}) = π_{3} − 1, ⋯, f(π_{k−1}) = π_{k} − 1, f(π_{k}) = π_{1} − 1,

subject to the above subtraction rule (2.1) if an element π_{t} is a barred element.

By the definition of signed relative derangement, we claim that f satisfies the condition of a signed skew derangement with respect to the elements π_{1}, π_{2}, …, π_{k}, namely,

f(π_{1}) ≠ π_{1}, f(π_{2}) ≠ π_{2}, …, f(π_{k}) ≠ π_{k}.

For any r = 1, 2, ⋯, k − 1, since π is a signed relative derangement, in view of the addition operation (2.2) we see that π_{r+1} ≠ π_{r} + 1 no matter whether π_{r} is a barred element or not. So we have

f(π_{r}) = π_{r+1} − 1 ≠ π_{r}

for r = 1, 2, ⋯, k − 1. We now consider π_{k}. Since π_{k} is the maximum element of π, we find π_{1} − 1 ≠ π_{k}. This implies that f(π_{k}) = π_{1} − 1 ≠ π_{k}.

Now we can repeat the above procedure for the remaining sequence σ = π_{k+1}π_{k+2} ⋯ π_{n}. The next step is still to choose the maximum element π_{t} in σ, then assign the images of f for the elements π_{k+1}, π_{k+2}, …, π_{t}. If there are still elements left, we may iterate this procedure until f is completely determined.

It remains to construct the inverse procedure. Given a signed skew derangement f on [n], we aim to find the corresponding signed relative derangement.

Suppose f is a bijection from a signed set X to X −1. The first step is to determine π_{1}. Assume that u is the maximum element in X with respect to the order (1.2). Then we set π_{1} = f(u)+1, subject to the above addition rule (2.2) if f(u) is a barred element. Suppose π_{r} is already located. If π_{r} ≠ u, then we set π_{r+1} = f(π_{r}) + 1, using the above rule (2.2) if f(π_{r}) is a barred element, and repeat this process until we reach a step when π_{k} = u for some k.

At this point, we have obtained the segment i_{1}i_{2} ⋯ i_{k}. Since f(i_{r}) ≠ i_{r}, we see that i_{r+1} ≠ i_{r} + 1, for r = 1, ⋯, k. If k < n, then we may choose the maximum element in the remaining elements in X after removing the elements i_{1}, i_{2}, …, i_{k}, and iterate the above procedure until we obtain the desired signed relative derangement. Thus, we have shown that our construction is a bijection.

For example, the signed relative derangement ¯7 8 6 ¯1 ¯5 ¯3 4 2 corresponds to the following signed skew derangement:

f(¯7) = 8 − 1 = 7, f(8) = ¯7 − 1 = ¯6, f(6) = 6 − 1 = 5, f(¯1) = ¯5 − 1 = ¯4,

f(¯5) = ¯3 − 1 = ¯2, f(¯3) = 4 − 1 = 3, f(4) = ¯1 − 1 = ¯0, f(2) = 2 − 1 = 1.

We now turn our attention to a combinatorial interpretation of the fact that the number of signed skew derangements on [n] equals D_{n}^{B} + D_{n−1}^{B}. As the first step, we give a characterization of signed permutations on {0, 1, …, n − 1} that correspond to signed skew derangements on [n]. Let us consider bijections from a signed set X on [n] to X − 1. Assume that the elements of X are arranged by the increasing order of their underlying elements, say, X = {σ_{1}, σ_{2}, …, σ_{n}}. It is easy to observe the fact that a bijection f from X to X − 1 is determine by the signed permutation π = π_{1}π_{2} ⋯ π_{n}, where π_{i} = f(σ_{i}). In fact, this is a bijection, because for any signed permutation π on {0, 1, …, n − 1}, the elements {π_{1}, π_{2}, …, π_{n}} determines the signed set X − 1, which in turn determines X. Hence the map f from X to X − 1 is easily constructed. The signed permutation π is called the representation of f.

For the above signed skew derangement f, we have

X = {σ_{1}, σ_{2}, …, σ_{8}} = {¯1, 2, ¯3, 4, ¯5, 6, ¯7, 8}

and π = ¯4 1 3 ¯0 ¯2 5 7 ¯6.

The following lemma gives a characterization of signed permutations which are representations of signed skew derangements. A bar associated with an element is intuitively considered as a sign. Moreover, for a signed permutation π = π_{1}π_{2} ⋯ π_{n}, an element π_{i} is called a fixed point if π_{i} = i, whereas it is called a signed fixed point if π_{i} = i or ī. As will be seen, signed fixed points play an important role in establishing the correspondence between signed skew derangements and signed derangements.

Lemma 2.1. Let π be a signed permutation on {0, 1, …, n − 1}, and let X and f be the signed set and the bijection from X to X − 1 determined by π. Then f has a fixed point if π has a signed fixed point π_{i}, and i − 1 and i have the same sign in π.

The above lemma can be restated as follows. A signed permutation π is a representation of a signed skew derangement if and only if π_{i} = i implies that \overline{i − 1} appears in π, and π = ī implies that i − 1 appears in π.

Proof. Let π be a signed permutation on {0, 1, 2, …, n − 1}. Let f be a bijection from X to X − 1 such that π is the representation of f. Then X − 1 is determined by the entries of π. Hence X is uniquely determined by π. Let σ_{1}, σ_{2}, …, σ_{n} be the elements of X arranged in the increasing order of the underlying elements of X. If f has a fixed point, say, f(x) = x, for some x = σ_{i}. Then we have σ_{i} = i or ī, and f(σ_{i}) = σ_{i} = π_{i}. Since f is a bijection from X to X − 1, σ_{i} is a barred element if and only if i − 1 is a barred element. Thus, we conclude that π_{i} and i − 1 have the same sign. This completes the proof.

The above characterization indicates that signed skew derangements can be viewed as an intermediate structure between signed relative derangements and signed derangements. Using this characterization of representations of signed skew derangements on [n], we first consider a class of such signed permutations that are in one-to-one correspondence with signed derangements on [n − 1].

Lemma 2.2. There is a bijection between the set of representations of signed skew derangements on [n] that are of the form π = π_{1}π_{2} ⋯ π_{n−1}0 and the set of signed derangements on [n − 1].

For example, there are five signed derangements on {1, 2}: ¯1¯2, 21, 2¯1, ¯21, ¯2¯1. In the meantime, there are five representations signed skew derangements on {1, 2, 3} that are of the form π_{1}π_{2}0: ¯1¯20, 210, 2¯10, ¯210, ¯2¯10. As in this example, special attention should be paid to the signed derangement ¯1¯2 with signed fixed points, and to the representation ¯1¯20 which also have signed fixed points. In general, we can establish a correspondence as given in the following proof.

Proof. Let π = π_{1}π_{2} ⋯ π_{n−1}0 be a representation of a signed skew derangement on [n]. We aim to construct a signed derangement on [n − 1] from π. If π_{1}π_{2} ⋯ π_{n−1} has no signed fixed point, then it is automatically the desired signed derangement.

We now consider that case when there are some signed fixed points, namely, there exist some i such that π_{i} = i or ī. Taking the signed fixed point π_{i} with minimum index i, we observe that whether π_{i} has a bar or not is determined solely by the appearance of i − 1 in the sense that it is a barred element or an unbarred element. Iterating this argument, we may deduce that the signed fixed points are uniquely determined by the remaining elements in π. Hence we may always put ī as the signed fixed points in order to obtain a signed derangement.

Conversely, given a signed derangement τ = τ_{1}τ_{2} ⋯ τ_{n−1}, we may identify the signed fixed points τ_{i}. By the same argument as in the previous paragraph, we can determine the signed fixed points according to the characterization of representations of signed skew derangements so that the resulting signed permutation on {0, 1, …, n−1} corresponds to a signed skew derangement. This completes the proof.

For example, consider the signed skew derangement f on {1, 2, …, 8} which has the following representation

f(1) f(2) f(¯3) f(¯4) f(5) f(¯6) f(¯7) f(8) = ¯6 ¯2 1 4 ¯3 7 ¯5 0.

It corresponds to the signed derangement ¯6 ¯2 1 ¯4 ¯3 7 ¯5 on {1, 2, …, 7}.

To complete the combinatorial proof of Theorem 1.3, it suffices to consider the second case for the representations of signed skew derangements. The following lemma is concerned with this case.

Lemma 2.3. There is a one-to-one correspondence between representations π = π_{1}π_{2} ⋯ π_{n} of signed skew derangements on [n] with π_{n} ≠ 0 and signed derangements on [n].

For example, there are five representation π = π_{1}π_{2} of signed skew derangements on {1, 2} with π_{2} ≠ 0: 01, 0¯1, ¯01, ¯0¯1, 1¯0.

Proof. First, we show that from a representation π = π_{1}π_{2} ⋯ π_{n} of a signed skew derangement with π_{n} ≠ 0 we can construct a signed derangement τ = τ_{1}τ_{2} ⋯ τ_{n}. If there is no signed fixed point in π, then we can replace 0 or ¯0 by n or n̄ in π depending whether 0 or ¯0 appears. Since π_{n} ≠ 0, we have τ_{n} ≠ n and so the resulting signed permutation is a signed derangement on [n].

Otherwise, there are some signed fixed points π_{i} (1 ≤ i ≤ n − 1), namely, π_{i} = i or ī. Using the same argument as in the proof of Lemma 2.2, we see that the signed fixed points are completely determined by the remaining elements in the signed permutation. So we may set all the signed fixed points to barred elements in π. Finally, we may replace 0 by n or ¯0 by n̄ to get a signed derangement τ on [n].

It is easy to see that the above procedure is reversible. This completes the proof.

For example, consider the signed skew derangement f on {1, 2, …, 8} which has the following representation

f(¯1) f(2) f(¯3) f(4) f(¯5) f(6) f(¯7) f(8) = ¯4 1 3 ¯0 ¯2 5 7 ¯6.

The corresponding signed derangement turns out to be ¯4 1 ¯3 ¯8 ¯2 5 ¯7 ¯6.

Combining the preceding two lemmas leads to a combinatorial interpretation of Theorem 1.3. To conclude this paper, we remark that our bijection between signed relative derangements and signed skew derangements can be restricted to ordinary permutations. Hence the classical relation (1.1) is a consequence of Theorem 1.3.

Acknowledgments. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science and Technology, and the National Science Foundation of China.

References

[1] T. Andreescu and Z. Feng, A Path to Combinatorics for Undergraduates, Birkhäuser, Boston, 2004.

[2] R.A. Brualdi, Introductory Combinatorics, 2nd Ed., North-Holland, Amsterdam, 1992.

[3] W.Y.C. Chen, The skew, relative, and classical derangements, Discrete Mathematics, 160 (1996) 235–239.

[4] C.-O. Chow, On derangement polynomials of type B, Séminaire Lotharingien de Combinatorics, 55 (2006), Artical B55b.

[5] D. Hanson, K. Seyffarth and J.H. Weston, Matchings, derangements, rencontres, Math. Magazine, 56 (1983), 224-229.

[6] R.P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, Cambridge, 1997.

[7] J. Shareshian and M.L. Wachs, q-Eulerian polynomials: Excedance number and major index, Electronic Research Announcements of the Amer. Math. Soc., 13 (2007), 33-45.

[8] E.T.H. Wang, Elementary Problem 2947, Amer. Math. Monthly, 89 (1982), 334 (with solutions 92 (1985), 216).