Ménage Numbers and Ménage Permutations

Yiting Li Department of Mathematics Brandeis University 415 South Street Waltham, MA 02453 USA

                     yitingli@brandeis.edu

Abstract

In this paper, we study the combinatorial structures of straight and ordinary ménage permutations. Based on these structures, we prove four formulas. The first two formulas define a relationship between the ménage numbers and the Catalan numbers. The other two formulas count the ménage permutations by number of cycles.

1 Introduction

1.1 Straight ménage permutations and straight ménage numbers

The straight ménage problem asks for the number of ways one can arrange n male-female pairs along a linearly arranged table in such a way that men and women alternate but no woman sits next to her partner.

We call a permutation π ∈ S_{n} a straight ménage permutation if π(i) ≠ i and π(i) ≠ i+1 for 1 ≤ i ≤ n. Use V_{n} to denote the number of straight ménage permutations in S_{n}. We call V_{n} the nth straight menage number.

The straight ménage problem is equivalent to finding V_{n}. Label the seats along the table as 1, 2, …, 2n. Sit the men at positions with even numbers and women at positions with odd numbers. Let π be the permutation such that the man at position 2i is the partner of the woman at position 2π(i)−1 for 1 ≤ i ≤ n. Then, the requirement of the straight ménage problem is equivalent to the condition that π(i) is neither i nor i + 1 for 1 ≤ i ≤ n.

1.2 Ordinary ménage permutations and ordinary ménage numbers

The ordinary ménage problem asks for the number of ways one can arrange n male-female pairs around a circular table in such a way that men and women alternate, but no woman sits next to her partner.

We call a permutation π ∈ S_{n} an ordinary ménage permutation if π(i) ≠ i and π(i) ≢ i + 1 (mod n) for 1 ≤ i ≤ n. Use U_{n} to denote the number of ordinary ménage permutations in S_{n}. We call U_{n} the nth ordinary ménage number.

The ordinary ménage problem is equivalent to finding U_{n}. Label the seats around the table as 1, 2, …, 2n. Sit the men at positions with even numbers and women at positions with odd numbers. Let π be the permutation such that the man at position 2i is the partner of the woman at position 2π(i) − 1 for all 1 ≤ i ≤ n. Then, the requirement of the ordinary ménage problem is equivalent to the condition that π(i) is neither i nor i + 1 (mod n) for 1 ≤ i ≤ n.

We hold the convention that the empty permutation π_{∅} ∈ S_{0} is both a straight ménage permutation and an ordinary ménage permutation, so U_{0} = V_{0} = 1.

1.3 Background

Lucas [7, pp. 491–495] first posed the problem of finding ordinary ménage numbers. Touchard [11] first found the following explicit formula (1). Kaplansky and Riordan [6] also proved an explicit formula for ordinary ménage numbers. For other early work in ménage numbers, we refer interested readers to the work of Kaplansky [5] and the paper of Moser and Wyman [8] and references therein. Among more recent papers, there are some using bijective methods to study ménage numbers. For example, Canfield and Wormald [2] used graphs to address the question. The following formulas of ménage numbers are well known [1, 9, 11]:

U_{m} = ∑_{k=0}^{m}(−1)^{k} \frac{2m}{2m − k} \binom{2m − k}{k}(m − k)! (m ≥ 2);  (1)

V_{n} = ∑_{k=0}^{n}(−1)^{k}\binom{2n − k}{k}(n − k)! (n ≥ 0).  (2)

In particular, the interesting method of Bogart and Doyle [1] can also induce (4) and (5) of Theorem 1 in a different way as this paper.

We remark that the generating function [4, p. 372]

∑_{n=0}^{∞} U_{n}x^{n} = x + \frac{1 − x}{1 + x} ∑_{n=0}^{∞} n!(\frac{x}{(1 + x)^{2}} )^{n}  (3)

is equivalent to (5) of Theorem 1.

The purpose of the current paper is to study the combinatorial structures of straight and ordinary ménage permutations and to use these structures to prove some formulas of straight and ordinary ménage numbers. We also give an analytical proof of Theorem 1 in Section 7.

1.4 Main results

Let C_{k} be the kth Catalan number:

C_{k} = \frac{(2k)!}{k! (k + 1)!}

and c(x) = ∑_{k=0}^{∞} c_{k}x^{k}. Our first main result is the following theorem.

Theorem 1.

∑_{n=0}^{∞} n! x^{n} = ∑_{n=0}^{∞} V_{n}x^{n}c(x)^{2n+1},  (4)

∑_{n=0}^{∞} n! x^{n} = c(x) + c′(x) ∑_{n=1}^{∞} U_{n}x^{n}c(x)^{2n−2}.  (5)

Our second main result counts the straight and ordinary ménage permutations by the number of cycles.

For k ∈ ℕ, use (α)_{k} to denote α(α+1) ⋯ (α+k −1). Define (α)_{0} = 1. For k ≤ n, use C_{n}^{k} (D_{n}^{k}) to denote the number of straight (ordinary) ménage permutations in S_{n} with k cycles.

Theorem 2.

1 + ∑_{n=1}^{∞} ∑_{j=1}^{n} C_{n}^{j}α^{j}x^{n} = ∑_{n=0}^{∞}(α)_{n} \frac{x^{n}}{(1 + x)^{n}(1 + αx)^{n+1}} ,  (6)

1 + ∑_{n=1}^{∞} ∑_{j=1}^{n} D_{n}^{j}α^{j}x^{n} = \frac{x + αx^{2}}{1 + x} + (1 − αx^{2}) ∑_{n=0}^{∞}(α)_{n} \frac{x^{n}}{(1 + x)^{n+1}(1 + αx)^{n+1}} .  (7)

1.5 Outline

We give some preliminary concepts and facts in Section 2. In Section 3, we define three types of reductions and the nice bijection. Then, we study the structure of straight ménage permutations and prove (4) in Section 4. In Section 5, we study the structure of ordinary ménage permutations and prove (5). Finally, we count the straight and ordinary ménage permutations by number of cycles and prove (6) and (7) in Section 6.

2 Preliminaries

For n ∈ ℕ, we use [n] to denote {1, …, n}. Define [0] to be ∅.

Definition 3. Suppose n > 0 and π ∈ S_{n}. If π(i) = i+1, then we call {i, i+1} a succession of π. If π(i) ≡ i + 1 (mod n), then we call {i, π(i)} a generalized succession of π.

2.1 Partitions and Catalan numbers

Suppose n > 0. A partition ϵ of [n] is a collection of disjoint subsets of [n] whose union is [n]. We call each subset a block of ϵ. We also describe a partition as an equivalence relation: p ∼_{ϵ} q if and only if p and q belong to a same block of ϵ.

If a partition ϵ satisfies that for any p ∼_{ϵ} p′ and q ∼_{ϵ} q′, p < q < p′ < q′ implies p ∼_{ϵ} q; then, we call ϵ a noncrossing partition.

For n ∈ ℕ, suppose ϵ = {V_{1}, …, V_{k}} is a noncrossing partition of [n] and V_{i} = {a_{1}^{i}, …, a_{j_{i}}^{i}}, where a_{1}^{i} < ⋯ < a_{j_{i}}^{i}. Then, ϵ induces a permutation π ∈ S_{n}: π(a_{r(i)}^{i}) = a_{r(i)+1}^{i} for 1 ≤ r(i) ≤ j_{i} − 1 and π(a_{j_{i}}^{i}) = a_{1}^{i}. It is not difficult to see that different noncrossing partitions induce different permutations.

The following lemma is well known [10, pp. 176–178].

Lemma 4. For n ∈ ℕ, there are C_{n} noncrossing partitions of [n].

It is well known that the generating function of the Catalan numbers is

c(x) = ∑_{n=0}^{∞} C_{n}x^{n} = \frac{1 − \sqrt{1 − 4x}}{2x}.

It is also well known that one can define the Catalan numbers by recurrence relation

C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k}  (8)

with initial condition C_{0} = 1.

Lemma 5. The generating function of the Catalan numbers c(x) satisfies

c(x) = \frac{1}{1 − xc(x)} = 1 + xc^{2}(x) and \frac{c^{3}(x)}{1 − xc^{2}(x)} = c′(x).

Proof of Lemma 5. The first formula is well known. By the first formula,

c′(x) = c^{2}(x) + 2xc(x)c′(x) = \frac{c^{2}(x)}{1 − 2xc(x)}.  (9)

Thus, to prove the second formula, we only have to show that \frac{c(x)}{1 − xc^{2}(x)} = \frac{1}{1 − 2xc(x)}

which is equivalent to c(x) − 2xc^{2}(x) = 1 − xc^{2}(x). This follows from the first formula.

2.2 Diagram representation of permutations

2.2.1 Diagram of horizontal type

For n > 0 and π ∈ S_{n}, we use a diagram of horizontal type to represent π. To do this, draw n points on a horizontal line. The points represent the numbers 1, …, n from left to right. For each i ∈ [n], we draw a directed arc from i to π(i). The permutation uniquely determines the diagram. For example, if π = (1, 5, 4)(2)(3)(6), then its diagram is

Figure 1: Circular diagram of π = (1, 5, 4)(2)(3)(6).

2.2.2 Diagram of circular type

For n > 0 and π ∈ S_{n}, we also use a diagram of circular type to represent π. To do this, draw n points uniformly distributed on a circle. Specify a point that represents the number 1. The other points represent 2, …, n in counter-clockwise order. For each i, draw a directed arc from i to π(i). The permutation uniquely determines the diagram (up to rotation). For example, if π = (1, 5, 4)(2)(3)(6), then its diagram is

Figure 2: Horizontal diagram of π = (1, 5, 4)(2)(3)(6).

2.3 The empty permutation

The empty permutation π_{∅} ∈ S_{0} is a permutation with no fixed points, no (generalized) successions and no cycles.

3 Reductions and nice bijections

In this section, we introduce reductions and nice bijections which serve as our main tools to study ménage permutations.

3.1 Reduction of type 1

Intuitively speaking, to perform a reduction of type 1 is to remove a fixed point from a permutation. Suppose n ≥ 1, π ∈ S_{n} and π(i) = i. Define π′ ∈ S_{n−1} such that:

π′(j) = \begin{cases}π(j), & if j < i and π(j) < i; \\ π(j) − 1, & if j < i and π(j) > i; \\ π(j + 1), & if j ≥ i and π(j + 1) < i; \\ π(j + 1) − 1, & if j ≥ i and π(j + 1) > i \end{cases}  (10)

when n > 1. When n = 1, define π′ to be π_{∅}. If we represent π by a diagram (of either type), erase the point corresponding to i and the arc connected to the point (and number other points appropriately for the circular case); then we obtain the diagram of π′. We call this procedure of obtaining a new permutation by removing a fixed point a reduction of type 1. For example, if

π = (1, 5, 6, 4)(2)(3)(7) ∈ S_{7},

then by removing the fixed point 3 we obtain π′ = (1, 4, 5, 3)(2)(6) ∈ S_{6}.

3.2 Reduction of type 2

Intuitively speaking, to do a reduction of type 2 is to glue a succession {k, k + 1} together. Suppose n ≥ 2, π ∈ S_{n} and π(i) = i + 1. Define π′ ∈ S_{n−1} such that:

π′(j) = \begin{cases}π(j), & if j < i and π(j) ≤ i; \\ π(j) − 1, & if j < i and π(j) > i + 1; \\ π(j + 1), & if j ≥ i and π(j + 1) ≤ i; \\ π(j + 1) − 1, & if j ≥ i and π(j + 1) > i + 1. \end{cases}  (11)

If we represent π by the diagram of the horizontal type, erase the arc from i to i + 1, and glue the points corresponding to i and i + 1 together; then, we obtain the diagram of π′. We call this procedure of obtaining a new permutation by gluing a succession together a reduction of type 2. For example, if

π = (1, 5, 6, 4)(2)(3)(7) ∈ S_{7},

then by gluing 5 and 6 together, we obtain π′ = (1, 5, 4)(2)(3)(6) ∈ S_{6}.

3.3 Reduction of type 3

Intuitively speaking, to perform a reduction of type 3 is to glue a generalized succession {k, k + 1 (mod n)} together. Suppose n ≥ 1, π ∈ S_{n} and π(i) ≡ i + 1 (mod n). Define π′ to be the same as in (11) when i ≠ n. When i = n > 1, define π′ to be

π′(j) = \begin{cases}π(j), & if j ≠ π^{−1}(n); \\ 1, & if j = π^{−1}(n). \end{cases}

When i = n = 1, define π′ to be π_{∅}. If we represent π by a diagram of the circular type, erase the arc from i to i + 1 (mod n), glue the points corresponding to i and i + 1 (mod n) together and number the points appropriately; then, we obtain the diagram of π′. We call this procedure of obtaining a new permutation by gluing a generalized succession together a reduction of type 3. For example, if

π = (1, 5, 6, 7)(2)(3)(4) ∈ S_{7},

then by gluing 1 and 7 together, we obtain π′ = (1, 5, 6)(2)(3)(4) ∈ S_{6}.

3.4 Nice bijections

Suppose n ≥ 1 and f is a bijection from [n] to {2, …, n + 1}. We can also represent f by a diagram of horizontal type as for permutations. The bijection uniquely determines the diagram. If f has a fixed point or there exists i such that f(i) = i + 1, then we can also perform reductions of type 1 or type 2 on f as above. In the latter case, we also call {i, i+1} a succession of f. We can reduce f to a bijection with no fixed points and no successions by a series of reductions. It is easy to see that the resulting bijection does not depend on the order of the reductions.

The following diagram shows an example of reduction of type 2 on the bijection by gluing the succession 2 and 3 together.

Figure 3: Reduction of type 2 by gluing the succession 2 and 3 together.

Definition 6. Suppose f is a bijection from [n] to {2, …, n + 1}. If there exist a series of reductions of type 1 or type 2 by which one can reduce f to the simplest bijection 1 ↦ 2, then we call f a nice bijection.

Suppose π ∈ S_{n} and p is a point of π. We can replace p by a bijection f from [k] to {2, …, k + 1} and obtain a new permutation π′ ∈ S_{n+k} by the following steps:

(1) represent π by the horizontal diagram;

(2) add a point q right before p and add an arc from q to p ;

(3) replace the arc from π^{−1}(p) to p by an arc from π^{−1}(p) to q ;

(4) replace the arc from q to p by the diagram of f. For example, if π, p and f are as below,

Figure 4: Example: π, p and f.

then, we can replace p by f and obtain the following permutation:

Figure 5: Replace p by f.

It is easy to see, by the definition of the nice bijection, that if f is a nice bijection, then we can reduce π′ back to π: first, we can reduce π′ to the permutation obtained in Step (3) because f is nice; then, by gluing the succession p and q together, we obtain π. Notice that the bijection f in the above example is not nice.

For the circular diagram of a permutation π, we can also use Steps (2)–(4) shown above to obtain a new diagram. However, to obtain a permutation π′, we need to specify the point representing number 1 in the new diagram. See the example in the proof of Theorem 11.

Lemma 7. For n ≥ 2, let a_{n} be the number of nice bijections from [n − 1] to {2, …, n}. Define a_{1} = 1. The generating function of a_{n} satisfies the following equation:

g(x) := a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ⋯ = xc(x)

where c(x) = ∑_{n=0}^{∞} C_{k}x^{k} is the generating function of the Catalan numbers.

Proof of Lemma 7. Suppose n ≥ 2 and f is a nice bijection from [n − 1] to {2, …, n} such that f(1) = k.

Suppose p < k. We claim that f(p) < k. If not, suppose q = f(p) > k. Then, neither {1, k} nor {p, q} is a succession. Consider the horizontal diagram of f. If we perform a reduction of type 1 or type 2 on f, then the arc we remove is neither the arc from 1 to k nor the arc from p to q. By induction, no matter how many reductions we perform, there always exists an arc from 1 to k′ and an arc from p′ to q′ such that p′ < k′ < q′. In other words, we can never reduce the bijection to 1 ↦ 2. Thus, we proved the claim.

Thus, the image of {2, …, k − 1} under f must be {2, …, k − 1}, and therefore, the image of {k, …, n − 1} under f must be {k + 1, …, n}.

This implies that f|_{{2,...,k−1}} has the same diagram as a permutation τ ∈ S_{k−2} and we can reduce τ to π_{∅}. This also implies that f|_{{k,...,n−1}} has the same diagram as a nice bijection from [n − k] to {2, …, n − k + 1}. By Lemma 8, the number of nice bijections from [n − 1] to

{2, …, n} such that f(1) = k is C_{k−2}a_{n−k+1}. Letting k vary, we obtain a_{n} = ∑_{k=2}^{n} C_{k−2}a_{n−k+1}.

By (8), (C_{n})_{n≥0} and (a_{n+1})_{n≥0} have the same recurrence relation and the same initial condition C_{0} = a_{1} = 1, so C_{n} = a_{n+1}(n ≥ 0). Therefore g(x) = xc(x).

4 Structure of straight ménage permutations

In Section 4, when we mention a reduction, we mean a reduction of type 1 or type 2.

If a permutation π is not a straight ménage permutation, then π has at least one fixed point or succession. Thus, we can apply a reduction to π. By induction, we can reduce π to a straight ménage permutation π′ by a series of reductions. For example, we can reduce π_{1} = (1, 3)(2)(4, 5, 6) to π_{∅}: (1, 3)(2)(4, 5, 6) → (1, 2)(3, 4, 5) → (1)(2, 3, 4) → (1, 2, 3) → (1, 2) → (1) → π_{∅}. We can reduce π_{2} = (1, 5, 4)(2)(3)(6) ∈ S_{6} to (1, 3, 2): (1, 5, 4)(2)(3)(6) → (1, 5, 4)(2)(3) → (1, 4, 3)(2) → (1, 3, 2). It is easy to see that the resulting straight ménage permutation does not depend on the order of the reductions. Recall that we defined the permutation induced from a noncrossing partition in Section 2.1.

Lemma 8. Suppose π ∈ S_{n}. We can reduce π to π_{∅} by reductions of type 1 and type 2 if and only if there is a noncrossing partition inducing π. In particular, there are C_{n} such permutations in S_{n}.

Proof. ⇒: Suppose we can reduce π ∈ S_{n} to π_{∅}. Then, π has at least one fixed point or succession. We use induction on n. If n = 1, the conclusion is trivial. Suppose n > 1.

If π has a fixed point i, then by reduction of type 1 on i we obtain π′ satisfying (10). By induction assumption, there is a noncrossing partition Φ = {V_{1}, …, V_{k}} inducing π′. Now, we define a new noncrossing partition Π_{1}(Φ, i) as follows. Set

Ṽ_{r} = {x + 1|x ∈ V_{r} and x ≥ i} ∪ {x|x ∈ V_{r} and x < i}

for 1 ≤ r ≤ k and Ṽ_{k+1} = {i}. Define Π_{1}(Φ, i) = {Ṽ_{1}, …, Ṽ_{k+1}}. It is not difficult to check that Π_{1}(Φ, i) is a noncrossing partition inducing π.

If π has a succession {i, i + 1}, then by reduction of type 2 on {i, i + 1}, we obtain π′′ satisfying (11). By induction assumption, there is a noncrossing partition Φ = {U_{1}, …, U_{s}} inducing π′′. Now, we define a new noncrossing partition Π_{2}(Φ, i) as follows. Set

Ũ_{t} = \begin{cases}\{x + 1|x ∈ U_{t} and x > i\} ∪ \{x|x ∈ U_{t} and x < i\}, & if t ≠ t_{0}; \\ \{x + 1|x ∈ U_{t} and x > i\} ∪ \{x|x ∈ U_{t} and x < i\} ∪ \{i, i + 1\}, & if t = t_{0}. \end{cases}

Define Π_{2}(Φ, i) = {Ũ_{1}, …, Ũ_{s}}. It is not difficult to check that Π_{2}(Φ, i) is a noncrossing partition inducing π.

⇐: Suppose there is a noncrossing partition {V_{1}, …, V_{k}} inducing π where V_{r} = {a_{1}^{r}, …, a_{j_{r}}^{r}} and a_{1}^{r} < ⋯ < a_{j_{r}}^{r}. We prove by using induction on n. The case n = 1 is trivial. Suppose n > 1. For r_{1} ≠ r_{2}, if [a_{1}^{r_{1}}, a_{j_{r_{1}}}^{r_{1}}] ∩ [a_{1}^{r_{2}}, a_{j_{r_{2}}}^{r_{2}}] ≠ ∅, then either [a_{1}^{r_{1}}, a_{j_{r_{1}}}^{r_{1}}] ⊂ [a_{1}^{r_{2}}, a_{j_{r_{2}}}^{r_{2}}] or [a_{1}^{r_{2}}, a_{j_{r_{2}}}^{r_{2}}] ⊂ [a_{1}^{r_{1}}, a_{j_{r_{1}}}^{r_{1}}]; otherwise, the partition cannot be noncrossing. Thus, there exists p such that [a_{1}^{p}, a_{j_{p}}^{p}] ∩ [a_{1}^{q}, a_{j_{q}}^{q}] = ∅ for all q ≠ p. If j_{p} = 1, then a_{1}^{p} is a fixed point of π. If j_{p} > 1, then {a_{1}^{p}, a_{2}^{p}} is a succession of π.

For the case j_{p} = 1, perform a reduction of type 1 on a_{1}^{p} and obtain π′ ∈ S_{n−1}. Then, {Ṽ_{r}|r ≠ p} is a noncrossing partition inducing π′, where

Ṽ_{r} = {x − 1|x ∈ V_{r} and x > a_{1}^{p}} ∪ {x|x ∈ V_{r} and x < a_{1}^{p}}.  (12)

By induction assumption, we can reduce π′ to π_{∅}; then, we can also reduce π to π_{∅}.

For the case j_{p} > 1, perform a reduction of type 2 on {a_{1}^{p}, a_{2}^{p}} and get π′ ∈ S_{n−1}. Then, {Ṽ_{r}|1 ≤ r ≤ k} is a noncrossing partition inducing π′, where Ṽ_{r} is the same as in (12). By induction assumption, we can reduce π′ to π_{∅}; then, we can also reduce π to π_{∅}.

Conversely, for a given straight ménage permutation π ∈ S_{m}, what is the cardinality of the set

{τ ∈ S_{m+n}| we can reduce τ to π by reductions of type 1 and type 2}?  (13)

Interestingly the answer only depends on m and n; it does not depend on the choice of π. In fact, we have

Theorem 9. Suppose m ≥ 0 and π ∈ S_{m} is a straight ménage permutation. Suppose n ≥ 0 and w_{m}^{n} is the cardinality of the set in (13). Set W_{m}(x) = w_{m}^{0} + w_{m}^{1}x + w_{m}^{2}x^{2} + w_{m}^{3}x^{3} + ⋯; then,

W_{m}(x) = c(x)^{2m+1}.

Proof of Theorem 9. If m = 0, then π = π_{∅}, and the conclusion follows from Lemma 8. Thus, we only consider the case that m > 0.

Obviously, w_{m}^{0} = 1. Now, suppose n ≥ 1.

Represent π by a horizontal diagram. The diagram has m + 1 gaps: one gap before the first point, one gap after the last point and one gap between each pair of adjacent points.

Let A be the set in (13). To obtain a permutation in A, we add points to π in the following two ways:

(a) add a permutation induced by a noncrossing partition Φ_{p} of [d_{p}] into the pth gap of π, where 1 ≤ p ≤ m + 1 and d_{p} ≥ 0 (d_{p} = 0 means that we add nothing into the pth gap);

(b) replace the qth point of π by a nice bijection f_{q} from [r_{q}] to {2, …, r_{q} + 1}, where 1 ≤ q ≤ m and r_{q} ≥ 0 (r_{q} = 0 means that we do not change the qth point).

For example, if π and f are as below,

Figure 6: Example: π and f.

then we can add the permutation (1, 2) between p and q, add the permutation (1)(2, 3) after the last point and replace p by f. Then, we obtain a permutation in A that is:

Figure 7: Add the permutation (1, 2) between p and q, add the permutation (1)(2, 3) after the last point and replace p by f.

Statement: The set of permutations constructed from (a) and (b) equals A. It is easy to see that we can reduce a permutation constructed through (a) and (b) to π. Conversely, suppose we can reduce π′ ∈ S_{m+n} to π. Now, we show that one can construct π′ through (a) and (b). Use induction on n. The case that n = 0 is trivial. Suppose n > 0. Then, π′ has at least one fixed point or succession. For a nice bijection f from [s] to {2, …, s + 1} and 1 < w_{1} < s + 1, 1 ≤ w_{2} ≤ s + 1, define nice bijections B_{1}(f, w_{1}) and B_{2}(f, w_{2}) as

B_{1}(f, w_{1}) = \begin{cases}f(x), & if x < w_{1} and f(x) < w_{1}; \\ f(x) + 1, & if x < w_{1} and f(x) ≥ w_{1}; \\ f(x − 1), & if x > w_{1} and f(x) < w_{1}; \\ f(x − 1) + 1, & if x > w_{1} and f(x) ≥ w_{1}; \\ w_{1}, & if x = w_{1}; \end{cases}  (14)

B_{2}(f, w_{2}) = \begin{cases}f(x), & if x < w_{2} and f(x) ≤ w_{2}; \\ f(x) + 1, & if x < w_{2} and f(x) > w_{2}; \\ f(x − 1), & if x > w_{2} and f(x) ≤ w_{2}; \\ f(x − 1) + 1, & if x > w_{2} and f(x) > w_{2}; \\ w_{2} + 1, & if x = w_{2}. \end{cases}  (15)

We can reduce B_{1}(f, w_{1}) to f by a reduction of type 1 on the fixed point w_{1}. We can reduce B_{2}(f, w_{2}) to f by a reduction of type 2 on the succession {w_{2}, w_{2} + 1}.

Case 1: π′ has a fixed point i. Using a reduction of type 1 on i, we obtain π′′ ∈ S_{m+n−1}. By induction assumption, we can construct π′′ from π by (a) and (b). According to the value of i, there is either a k such that

1 ≤ i − ∑_{j<k}(d_{j} + r_{j} + 1) ≤ d_{k} + 1  (16)

or a k′ such that

1 < i − (∑_{j<k′}(d_{j} + r_{j} + 1) + d_{k′}) ≤ r_{k′} + 1.  (17)

If there is a k such that (16) holds, then we can construct π′ from π by (a) and (b), except that we add the permutation induced by Π_{1}(Φ_{k}, i − ∑_{j<k}(d_{j} + r_{j} + 1)) instead of Φ_{k} into the kth gap, where Π_{1} is the same as in the proof of Lemma 8. Conversely, if there exists a k′ such that (17) holds, then we can construct π′ from π by (a) and (b), except that we replace the k′th point of π by B_{1}(f_{k′}, i − ∑_{j<k′}(d_{j} + r_{j} + 1)) instead of f_{k′}, where B_{1} is the same as in (14).

Case 2: π′ has a succession {i, i + 1}. By reduction of type 2 on {i, i + 1} we obtain π′′ ∈ S_{m+n−1}. By induction assumption, we can construct π′′ from π by (a) and (b). According to the value of i, there is either a k such that

0 < i − ∑_{j<k}(d_{j} + r_{j} + 1) ≤ d_{k}  (18)

or a k′ such that

0 < i − (∑_{j<k′}(d_{j} + r_{j} + 1) + d_{k′}) ≤ r_{k′} + 1.  (19)

If there is a k such that (18) holds, then we can construct π′ from π by (a) and (b), except that we add the permutation induced by Π_{2}(Φ_{k}, i − ∑_{j<k}(d_{j} + r_{j} + 1)) instead of Φ_{k} into the kth gap, where Π_{2} is the same as in the proof of Lemma 8. Conversely, if there exists a k′ such that (19) holds, then we can construct π′ from π by (a) and (b), except that we replace the k′th point of π by B_{2}(f_{k′}, i − ∑_{j<k′}(d_{j} + r_{j} + 1)) instead of f_{k′}, where B_{2} is the same as in (15).

Thus, we have proved the statement.

Now, add points to π by (a) and (b). The total number of points added to π is d_{1} + ⋯ + d_{m+1} + r_{1} + ⋯ + r_{m}. To obtain a permutation in S_{m+n} ∩ A, d_{1} + ⋯ + d_{m+1} + r_{1} + ⋯ + r_{m} should be n. Therefore, the number of permutations in S_{m+n} ∩ A is

w_{m}^{n} = ∑_{{d_{1},...,d_{m+1} \atop r_{1},...,rm}} C_{d_{1}} ⋯ C_{d_{m+1}}a_{1+r_{1}} ⋯ a_{1+r_{m}}

where C_{k} is the kth Catalan number and a_{k} is the same as in Lemma 7 and the sum runs over all (2m + 1)-triples (d_{1}, …, d_{m+1}, r_{1}, …, r_{m}) of nonnegative numbers with sum n.

By Lemma 7, the generating function of w_{m}^{n} is

c(x)^{m+1}(\frac{g(x)}{x})^{m} = c(x)^{2m+1}.

Proof of (4). We can reduce each permutation in S_{n} to a straight ménage permutation in S_{i} (0 ≤ i ≤ n). Thus, we have

n! = ∑_{i=0}^{n} w_{i}^{n−i}V_{i}

where V_{i} is the ith straight ménage number and w_{i}^{n−i} is the same as in Theorem 9. Thus,

∑_{n=0}^{∞} n! x^{n} = ∑_{n=0}^{∞} ∑_{i=0}^{n} w_{i}^{n−i}V_{i}x^{n} = ∑_{i=0}^{∞} ∑_{n=i}^{∞} w_{i}^{n−i}V_{i}x^{n} = ∑_{i=0}^{∞} ∑_{n=0}^{∞} w_{i}^{n}V_{i}x^{n}x^{i} = ∑_{i=0}^{∞} c(x)^{2i+1}V_{i}x^{i}

where the last equality is from Theorem 9.

5 Structure of ordinary ménage permutations

By definition, a permutation τ is an ordinary ménage permutation if and only if we cannot apply reductions of either type 1 or type 3 on τ. Similarly as in Section 4, we can reduce each permutation π to an ordinary ménage permutation by reductions of type 1 and type 3. The resulting permutation does not depend on the order of the reductions.

By the circular diagram representation of permutations, it is not difficult to see that we can reduce a permutation π to π_{∅} by reductions of type 1 and type 2 if and only if we can reduce π to π_{∅} by reductions of type 1 and type 3. Thus, we have the following lemma:

Lemma 10. Suppose π ∈ S_{n}. We can reduce π to π_{∅} by reductions of type 1 and type 3 if and only if there is a noncrossing partition inducing π. In particular, there are C_{n} permutations of this type in S_{n}.

In the following parts of Section 5, when we mention reductions, we mean reductions of type 1 or type 3 unless otherwise specified.

Theorem 11. Suppose m ≥ 0 and π ∈ S_{m} is an ordinary ménage permutation. Let r_{m}^{n} denote the cardinality of the set

{τ ∈ S_{m+n}|we can reduce τ to π by reductions of type 1 and type 3}.  (20)

Then, the generating function of r_{m}^{n} satisfies

R_{m}(x) := r_{m}^{0} + r_{m}^{1}x + r_{m}^{2}x^{2} + r_{m}^{3}x^{3} + ⋯ = \begin{cases}c′(x)c(x)^{2m−2}, & if m > 0; \\ c(x), & if m = 0. \end{cases}

Proof. When m = 0, r_{m}^{n} = C_{n} by Lemma 10. So R_{0}(x) = c(x). Now, suppose m > 0. Obviously r_{m}^{0} = 1. Suppose n > 0. Represent π by a circular diagram. The diagram has m gaps: one gap between each pair

of adjacent points. Call the point corresponding to number i point i.

Let A denote the set in (20). To obtain a permutation in A we can add points into π by the following steps:

(a) Add a permutation induced by a noncrossing partition Φ_{i} of [d_{i}] into the gap between point i and point i + 1 (mod m), where 1 ≤ i ≤ m and d_{p} ≥ 0 (d_{p} = 0 means we add nothing into the gap). Use Q_{i} to denote the set of points added into the gap between point i and point i + 1 (mod m).

(b) Replace point i by a nice bijection f_{i} from [t_{i}] to {2, …, t_{i} + 1}, where 1 ≤ i ≤ m and t_{i} ≥ 0 (t_{i} = 0 means that we do not change the ith point). Use P_{i} to denote the set of points obtained from this replacement. Thus, P_{i} contains t_{i} + 1 points.

(c) Specify a point in P_{1} ⋃ Q_{m} to correspond to the number 1 of the new permutation π′.

Steps (a) and (b) are the same as in the proof of Theorem 9, but Step (c) needs some explanation.

In the proof of Theorem 9, after adding points into the permutation by (a) and (b), we defined π′ from the resulting horizontal diagram in a natural way, that is, the left most point corresponds to 1, and the following points correspond to 2, 3, 4, … respectively. However, now there is no natural way to define π′ from the resulting circular diagram because we have more than one choice of the point corresponding to number 1 of π′.

Note that π′ can become π by a series of reductions of type 1 or type 3. Then, for each 1 ≤ u ≤ m, the points in P_{u} will become point u of π after the reductions. Thus, we can choose any point of P_{1} to be the one corresponding to the number 1 of π′. Moreover, we can also choose any point of Q_{m} to be the one corresponding to the number 1 of π′. The reason is that if a permutation in S_{k} has a cycle (1, k), then a reduction of type 3 will reduce (1, k) to the cycle (1). Thus, we can choose any point in P_{1} ⋃ Q_{m} to be the point corresponding to number 1 of π′. To see this more clearly, let us look at an example. Suppose π and f are as below:

Figure 8: Example: π and f.

Then, we can add the permutation (1, 2) between point 2 and point 3, add the permutation (1)(2, 3) between point 6 and point 1 and replace point 2 by f. Then, we obtain a new diagram:

Figure 9: Add the permutation (1, 2) between point 2 and point 3, add the permutation (1)(2, 3) between point 6 and point 1 and replace point 2 by f.

Now, we can choose point 1 or any of the three points between point 1 and point 6 to be the point corresponding to number 1 of the new permutation π′.

For instance, if we set point 1 to be the point corresponding to number 1 of π′, then

π′ = (1, 8, 2, 5)(3, 4)(6, 7)(9, 11, 10)(12)(13, 14).

If we set point w to be the point corresponding to number 1 of π′, then

π′ = (1, 14)(2, 9, 3, 6)(4, 5)(7, 8)(10, 12, 11)(13).

Now, continue the proof. By a similar argument to the one we used to prove the statement in the proof of Theorem 9, we have that the set of permutations constructed by (a)–(c) equals A.

Now, add points to π by (a)–(c). Then, P_{1} ⋃ Q_{m} contains, in total, d_{m} + (t_{1} + 1) points. Thus, we have d_{m} + (t_{1} + 1) ways to specify the point corresponding to number 1 in π′. The total number added to π is d_{1} + ⋯ + d_{m} + t_{1} + ⋯ + t_{m}. Therefore, the number of permutations in S_{m+n} ∩ A is

r_{m}^{n} = ∑_{{d_{1},...,dm \atop t_{1},...,tm}} C_{d_{1}} ⋯ C_{d_{m}}a_{1+t_{1}} ⋯ a_{1+t_{m}}(d_{m} + t_{1} + 1)

where C_{k} is the kth Catalan number, a_{k} is the same as in Lemma 7, and the sum runs over all 2m-triples (d_{1}, …, d_{m}, t_{1}, …, t_{m}) of nonnegative integers such that ∑_{u=1}^{m}(t_{u} + d_{u}) = n.

Set η_{k} = ∑_{r=0}^{k} a_{r+1}C_{k−r}(k + 1); from Lemma 7, we have

1 + \frac{η_{1}}{2} x + \frac{η_{2}}{3} x^{2} + \frac{η_{3}}{4} x^{3} + ⋯ = c^{2}(x).

By Lemma 5, the generating function of η_{k} is 1 + η_{1}x + η_{2}x^{2} + η_{3}x^{3} + ⋯ = (xc^{2}(x))′ = c′(x). Thus, the generating function of r_{m}^{n} is c(x)^{2m−2}c′(x).

Proof of (5). We can reduce each permutation in S_{n} to an ordinary ménage permutation. Thus, we have

n! = ∑_{i=0}^{n} r_{i}^{n−i}U_{i}

where U_{i} is the ith ordinary ménage number and r_{i}^{n−i} is the same as in Theorem 11. Thus,

∑_{n=0}^{∞} n! x^{n} = ∑_{n=0}^{∞} ∑_{i=0}^{n} r_{i}^{n−i}U_{i}x^{n} = ∑_{i=0}^{∞} ∑_{n=i}^{∞} r_{i}^{n−i}U_{i}x^{n}

= ∑_{i=0}^{∞} ∑_{n=0}^{∞} r_{i}^{n}U_{i}x^{n}x^{i} = c(x) + ∑_{i=1}^{∞} c′(x)c(x)^{2i−2}U_{i}x^{i}

where the last equality follows from Theorem 11.

6 Counting ménage permutations by number of cycles

We prove (6) in Section 6.2 and prove (7) in Section 6.3. Our main method is coloring. We remark that one can also prove (6) and (7) by using the inclusion-exclusion principle in a similar way as Gessel [3].

6.1 Coloring and weights

For a permutation π, we use f(π), g(π), h(π) and r(π) to denote the number of its cycles, fixed points, successions and generalized successions, respectively. The following lemma is well known.

Lemma 12. For n ≥ 0,

∑_{π∈S_{n}} α^{f(π)} = (α)_{n}.

For a permutation, color some of its fixed points red and color some of its generalized successions yellow. Then, we obtain a colored permutation. Here and in the following sections, we use the phrase colored permutation as follows: if two permutations are the same as maps but have different colors, then they are different colored permutations.

Define 𝕊_{n} to be the set of colored permutations on n objects. Set A_{n} to be the subset of 𝕊_{n} consisting of colored permutations with a colored generalized succession {n, 1}. Set B_{n} = 𝕊_{n}\A_{n}. So we can consider S_{n} as a subset of 𝕊_{n} consisting of permutations with no color. In particular, 𝕊_{0} = S_{0}.

Set

M_{n}^{α}(t, u) = ∑_{π∈S_{n}} α^{f(π)}t^{g(π)}u^{h(π)} and L_{n}^{α}(t, u) = ∑_{π∈S_{n}} α^{f(π)}t^{g(π)}u^{τ(π)}.

For a colored permutation ϵ ∈ 𝕊_{n}, define two weights W_{1} and W_{2} of ϵ as:

W_{1}(ϵ) = x^{n} · α^{f(ϵ)} · t^{number of colored fixed points} · u^{number of colored successions},
W_{2}(ϵ) = x^{n} · α^{f(ϵ)} · t^{number of colored fixed points} · u^{number of colored generalized successions}.

Lemma 13. ∑_{ϵ∈B_{n}} W_{1}(ϵ) = ∑_{ϵ∈B_{n}} W_{2}(ϵ) = M_{n}^{α}(1 + t, 1 + u)x^{n}, ∑_{ϵ∈𝕊_{n}} W_{2}(ϵ) = L_{n}^{α}(1 + t, 1 + u)x^{n}.

Proof. The lemma follows directly from the definitions of M_{n}^{α}, L_{n}^{α}, B_{n}, W_{1} and W_{2}.

6.2 Counting straight ménage permutations by number of cycles

In this subsection, we represent permutations by diagrams of horizontal type.

Suppose n ≥ 0 and π ∈ S_{n}. Then, π has n + 1 gaps: one gap before the first point, one gap after the last point and one gap between each pair of adjacent points. We can add points to π by the following steps.

(a) Add the identity permutation of S_{(d_{p})} into the pth gap of π, where 1 ≤ p ≤ n + 1 and d_{p} ≥ 0 (d_{p} = 0 means that we add nothing into the pth gap).

(b) Replace the qth point of π by a nice bijection from [r_{q}] to {2, …, r_{q} + 1}, which sends each i to i + 1. Here, 1 ≤ q ≤ n and r_{q} ≥ 0 (r_{q} = 0 means that we do not change the qth point).

(c) Color the fixed points added by (a) red, and color the successions added by (b) yellow. Then (a), (b) and (c) give a colored permutation in ⋃_{n=0}^{∞} B_{n}.

Lemma 14. Suppose π ∈ S_{n}. The sum of the W_{1}-weights of all colored permutations constructed from π by (a)–(c) is

x^{n} · α^{f(π)} · \frac{1}{(1 − αtx)^{n+1}} · \frac{1}{(1 − ux)^{n}} .

Proof. In Step (a), we added d_{p} fixed points into the pth gap. They contribute (xtα)^{d_{p}} to the weight because each of them is a single cycle and a colored fixed point. Because d_{p} can be any nonnegative integer, the total contribution of the fixed points added into a gap is \frac{1}{(1−αtx)}. Thus, the total contribution of the fixed points added into all the gaps is \frac{1}{(1−αtx)^{n+1}} .

In Step (b), through the replacement on the qth point, we added r_{q} points and r_{q} successions to π (each of which received a color in Step (c)). Thus, the contribution of this replacement to the weight is (ux)^{d_{q}}. Because d_{q} can be any nonnegative integer, the total contribution of the nice bijections replacing the qth point is \frac{1}{(1−ux)}. Thus, the total contribution of the nice bijections corresponding to all points is \frac{1}{(1−ux)^{n}}.

Observing that the W_{1}-weight of π is x^{n} · α^{f(π)}, we complete the proof.

Suppose ϵ is a colored permutation in ⋃_{n=0}^{∞} B_{n}. If we perform reductions of type 1 on the colored fixed points and perform reductions of type 2 on the colored successions, then we obtain a new permutation ϵ′ with no color. This ϵ′ is the only permutation in ⋃_{n=0}^{∞} S_{n} from which we can obtain ϵ by Steps (a)–(c). Therefore, there is a bijection between ⋃_{n=0}^{∞} B_{n} and

⋃_{n=0}^{∞} ⋃_{π∈S_{n}}{colored permutation constructed from π through Steps (a)–(c)}.

Because of the bijection, Lemmas 13 and 14 imply that

∑_{n=0}^{∞} M_{n}^{α}(1 + t, 1 + u)x^{n} = ∑_{n=0}^{∞} ∑_{π∈S_{n}} \frac{x^{n}α^{f(π)}}{(1 − αtx)^{n+1}(1 − ux)^{n}} .  (21)

Proof of (6). By Lemma 12 and (21), the sum of the W_{1}-weights of colored permutations in

⋃_{n=0}^{∞} B_{n} is

∑_{n=0}^{∞} M_{n}^{α}(1 + t, 1 + u)x^{n} = ∑_{n=0}^{∞} \frac{x^{n}(α)_{n}}{(1 − αtx)^{n+1}(1 − ux)^{n}} .  (22)

Setting t = u = −1, we have

∑_{n=0}^{∞} M_{n}^{α}(0, 0)x^{n} = ∑_{n=0}^{∞} \frac{x^{n}(α)_{n}}{(1 + αx)^{n+1}(1 + x)^{n}} .

Recall that straight ménage permutations are permutations with no fixed points or successions. Thus, for n > 0, M_{n}^{α}(0, 0) is the sum of the W_{1}-weights of straight ménage per-

mutations in S_{n}, which is ∑_{j=1}^{n} C_{n}^{j}α^{j}x^{n}. Furthermore, M_{0}^{α}(0, 0) = 1. Thus, we have proved

(6).

6.3 Counting ordinary ménage permutations by number of cycles

In this subsection, we represent permutations by diagrams of the horizontal type.

Suppose n ≥ 0 and π ∈ S_{n}. Define 𝕊_{m}(π) to be the a subset of 𝕊_{m}: τ ∈ 𝕊_{m} is in 𝕊_{m}(π) if and only if when we apply reductions of type 1 on the colored fixed points of τ and apply reductions of type 3 on the colored generalized successions of τ, we obtain π. Define A_{m}(π) = 𝕊_{m}(π) ∩ A_{m} and B_{m}(π) = 𝕊_{m}(π)\A_{m}(π).

Lemma 15. The W_{2}-weights of colored permutations in ⋃_{n=0}^{∞} A_{n} are

∑_{n=1}^{∞} x^{n}(α)_{n} · \frac{1}{(1 − αtx)^{n}} · \frac{1}{(1 − ux)^{n+1}} · ux + αutx + \frac{αux}{1 − ux}.

Proof. We first evaluate the sum of W_{2}-weights of colored permutations in ⋃_{m=n}^{∞} A_{m}(π) and then add them up with respect to π ∈ S_{n} and n ≥ 0.

Case 1: n > 0. In this case, for π ∈ S_{n}, we can construct a colored permutation in ⋃_{m=n}^{∞} A_{m}(π) by the following steps.

(a′) Define π̃ to be a permutation in S_{n+1} that sends π^{−1}(1) to n + 1, sends n + 1 to 1 and sends all other j to π(j). Represent π̃ by a horizontal diagram.

(b′) For 1 ≤ p ≤ n − 1, add the identity permutation of S_{(d_{p})} into the gap of π̃ between number p and p + 1, where d_{p} ≥ 0 (d_{p} = 0 means we add nothing into the gap).

(c′) Replace the qth point of π̃ by a nice bijection from [r_{q}] to {2, …, r_{q} +1}, which maps each i to i + 1. Here, 1 ≤ q ≤ n and r_{q} ≥ 0 (r_{q} = 0 means that we do not change the qth point).

(d′) Color the generalized succession consisting of 1 and the largest number yellow. Color the fixed points and generalized successions added by (b′)–(c′) red and yellow, respectively.

Suppose ϵ ∈ ⋃_{m=n}^{∞} A_{m}(π). If we perform reductions of type 1 on its colored fixed points and perform reductions of type 3 on its colored generalized successions, we obtain π. Furthermore, π is the only permutation in ⋃_{k=0}^{∞} S_{k} from which we can obtain ϵ through (a′)–(d′). Therefore, there is a bijection between ⋃_{m=n}^{∞} A_{m}(π) and

{colored permutations constructed from π through (a′)–(d′)}.

Now, we can claim that the sum of W_{2}-weight of the colored permutations in ⋃_{m=n}^{∞} A_{m}(π) is

x^{n}α^{f(π)} · \frac{1}{(1 − αtx)^{n}} · \frac{1}{(1 − ux)^{n+1}} · ux.  (23)

In (23), x^{n}α^{f(π)} is the W_{2}-weight of π. The term \frac{1}{(1−αtx)^{n}} corresponds to the fixed points added to the permutation in (b′). The term \frac{1}{(1−ux)^{n+1}} corresponds to the successions added to the permutation in (c′). The term ux corresponds to the generalized succession {n + 1, 1} added to the permutation in (a′).

Case 2: n = 0 and m = 0. In this case, A_{0}(π_{∅}) is empty.

Case 3: n = 0 and m ≥ 2. In this case, A_{m}(π_{∅}) contains one element: the cyclic permutation π_{C}, which maps each i to i + 1 (mod m). Each generalized succession of π_{C} has a color, so the sum of the W_{2}-weight of the colored permutations in A_{m}(π_{∅}) is α(ux)^{m}.

Case 4: n = 0 and m = 1. In this case, A_{1}(π_{∅}) contains one map: id_{1} ∈ S_{1}. However, id_{1} can have two types of color, namely, yellow and red+yellow, because id_{1} has one fixed point and one generalized succession. Thus, A_{1}(π_{∅}) contains two colored permutations, and the sum of their W_{2}-weights is αux + αtux.

We remark that the identity permutation id_{1} actually corresponds to four colored permutations. In addition to the two in A_{1}(π_{∅}), the other two are id_{1}, with a red color for its fixed point, and id_{1}, with no color. We have considered these colored permutations in B_{1}(π_{∅}) and B_{1}(id_{1}), respectively.

Because ⋃_{n=0}^{∞} A_{n} = ⋃_{n=0}^{∞} ⋃_{π∈S_{n}} ⋃_{m=n}^{∞} A_{m}(π), the sum of the W_{2}-weights of the colored permutations in ⋃_{n=0}^{∞} A_{n} equals the sum of the weights found in Cases 1–4. Thus, the sum is

( ∑_{n=1}^{∞} ∑_{π∈S_{n}} x^{n}α^{f(π)} · \frac{1}{(1 − αtx)^{n}} · \frac{1}{(1 − ux)^{n+1}} · ux) + ( ∑_{m=2}^{∞} α(ux)^{m}) + (αux + αtux)

= ∑_{n=1}^{∞} x^{n}(α)_{n} · \frac{1}{(1 − αtx)^{n}} · \frac{1}{(1 − ux)^{n+1}} · ux + αutx + \frac{αux}{1 − ux}

where we used Lemma 12.

Proof of (7). By Lemma 13, ∑_{n=0}^{∞} L_{n}^{α}(1+t, 1+u)x^{n} is the sum of the W_{2}-weights of the colored

permutations in ⋃_{n=0}^{∞} 𝕊_{n}. By Lemma 13 and (22), the sum of the W_{2}-weights of all colored permutations in ⋃_{n=0}^{∞} B_{n} is

∑_{n=0}^{∞} \frac{x^{n}(α)_{n}}{(1 − αtx)^{n+1}(1 − ux)^{n}} .

Because ⋃_{n=0}^{∞} 𝕊_{n} = (⋃_{n=0}^{∞} B_{n}) ⋃(⋃_{n=0}^{∞} A_{n}), Lemma 15 implies

∑_{n=0}^{∞} L_{n}^{α}(1 + t, 1 + u)x^{n}

=( ∑_{n=0}^{∞} \frac{x^{n}(α)_{n}}{(1 − αtx)^{n+1}(1 − ux)^{n}} ) + ( ∑_{n=1}^{∞} x^{n}(α)_{n} · \frac{1}{(1 − αtx)^{n}} · \frac{1}{(1 − ux)^{n+1}} · ux + αutx + \frac{αux}{1 − ux})

= ∑_{n=0}^{∞} [\frac{x^{n}(α)_{n}}{(1 − αtx)^{n+1}(1 − ux)^{n+1}} (1 − αtux^{2})] + αutx + \frac{(α − 1)ux}{1 − ux}.  (24)

Recall that ordinary ménage permutations are permutations with no fixed points and no generalized successions. By definition, L_{0}^{α}(0, 0)x^{0} = 1. When n ≥ 1, L_{n}^{α}(0, 0)x^{n} is the sum of

the W_{2}-weights of all ordinary ménage permutations in S_{n}, which equals ∑_{j=1}^{n} D_{n}^{j}α^{j}x^{n}. Thus,

∑_{n=0}^{∞} L_{n}^{α}(0, 0)x^{n} equals the left side of (7). When we set t = u = −1, the left side of (24)

equals the left side of (7), and the right side of (24) equals the right side of (7). We have proved (7).

7 An analytical proof of (4) and (5)

Now, we derive (4) and (5) from (1) and (2). By (2),

∑_{n=0}^{∞} V_{n}x^{n} = ∑_{n=0}^{∞} ∑_{k=0}^{n}(−1)^{k}\binom{2n − k}{k}(n − k)! x^{n} = ∑_{k=0}^{∞} ∑_{n=k}^{∞}(−1)^{k}\binom{2n − k}{k}(n − k)! x^{n}

= ∑_{k=0}^{∞} ∑_{n=0}^{∞}(−1)^{k}\binom{2n + k}{k}n! x^{n+k} = ∑_{n=0}^{∞} n! x^{n}[ ∑_{k=0}^{∞}(−1)^{k}\binom{2n + k}{k}x^{k}]

= ∑_{n=0}^{∞} n! \frac{x^{n}}{(1 + x)^{2n+1}} .  (25)

Letting x = zc^{2}(z), from Lemma 5 we have 1 + x = c(z), \frac{x}{(1 + x)^{2}} = z and

∑_{n=0}^{∞} V_{n}z^{n}c^{2n}(z) = ∑_{n=0}^{∞} V_{n}x^{n} = ∑_{n=0}^{∞} n! \frac{x^{n}}{(1 + x)^{2n+1}} = ∑_{n=0}^{∞} n! \frac{z^{n}}{c(z)}.

which implies (4). From (1),

U_{n} = \begin{cases}1, & if n = 0; \\ 0, & if n = 1; \\ ∑_{k=0}^{n}(−1)^{k}\binom{2n−k}{k}(n − k)! + ∑_{k=1}^{n}(−1)^{k}\binom{2n−k−1}{k−1}(n − k)!, & if n > 1. \end{cases}

Thus

∑_{n=0}^{∞} U_{n}x^{n} = x + ∑_{n=0}^{∞} ∑_{k=0}^{n}(−1)^{k}\binom{2n − k}{k}(n − k)! x^{n} + ∑_{n=1}^{∞} ∑_{k=1}^{n}(−1)^{k}\binom{2n − k − 1}{k − 1}(n − k)! x^{n}

= x + ∑_{n=0}^{∞} ∑_{k=0}^{n}(−1)^{k}\binom{2n − k}{k}(n − k)! x^{n} + ∑_{n=0}^{∞} ∑_{k=0}^{n}(−1)^{k+1}\binom{2n − k}{k}(n − k)! x^{n+1}

= x + (1 − x) ∑_{n=0}^{∞} ∑_{k=0}^{n}(−1)^{k}\binom{2n − k}{k}(n − k)! x^{n}.

Then, by (25),

∑_{n=0}^{∞} U_{n}x^{n} = x + (1 − x) ∑_{n=0}^{∞} n! \frac{x^{n}}{(1 + x)^{2n+1}} .

Noticing U_{0} = 1 we have

1 − x + ∑_{n=1}^{∞} U_{n}x^{n} = (1 − x) ∑_{n=0}^{∞} n! \frac{x^{n}}{(1 + x)^{2n+1}}

and

1 + x + \frac{1 + x}{1 − x} ∑_{n=1}^{∞} U_{n}x^{n} = ∑_{n=0}^{∞} n! \frac{x^{n}}{(1 + x)^{2n}} .  (26)

Letting x = zc^{2}(z), from Lemma 5 and (26), we have 1 + x = c(z), \frac{x}{(1 + x)^{2}} = z and

∑_{n=0}^{∞} n! z^{n} = c(z) + \frac{c(z)}{1 − zc^{2}(z)} ∑_{n=1}^{∞} U_{n}z^{n}(c(z))^{2n} = c(z) + \frac{(c(z))^{3}}{1 − zc^{2}(z)} ∑_{n=1}^{∞} U_{n}z^{n}(c(z))^{2n−2}.

Then, (5) follows from the above equation and Lemma 5.

8 Acknowledgments

It is a pleasure to thank Ira Gessel for introducing me to this topic and for some helpful conversations and Olivier Bernardi for some helpful suggestions. I also thank the anonymous referee for the comments and for pointing out that: (i) the method of Bogart and Doyle [1] can induce (4) and (5); (ii) (3) is equivalent to (5).

References

[1] K. Bogart and G. Doyle, Non-sexist solution of the ménage problem, Amer. Math. Monthly 93 (1986), 514–518.

[2] E. Canfield and N. Wormald, Ménage numbers, bijections and precursiveness, Discrete Math. 63 (1987), 117–129.

[3] I. Gessel, Generalized rook polynomials and orthogonal polynomials, in q-Series and Partitions, IMA Volumes in Mathematics and its Applications, Vol. 18, Springer-Verlag, 1989, pp. 159–176.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] I. Kaplansky, Solution of the probléme des ménages, Bull. Amer. Math. Soc. 49 (1943), 784–785.

[6] I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12 (1946), 113–124.

[7] E. Lucas, Théorie des Nombres, Gauthier-Villars, 1891.

[8] L. Moser and M. Wyman, On the problème des ménages, Canad. J. Math. 10 (1958), 468–480.

[9] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[10] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[11] J. Touchard, Sur un problème de permutations, C. R. Acad. Sci. Paris 198 (1934), 631–633.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: straight ménage number, ordinary ménage number, straight ménage permutation, ordinary ménage permutation.

(Concerned with sequences \underline{A000108}, \underline{A000179}, and \underline{A000271}.)

Received January 16 2015; revised versions received February 21 2015; June 11 2015; June 15 2015. Published in Journal of Integer Sequences, June 16 2015.

Return to Journal of Integer Sequences home page.