Let \(\alpha(n)\) denote the number of perfect square permutations in the symmetric group \(S_n\). The conjecture \(\alpha(2n+1) = (2n+1) \alpha(2n)\), provided by Stanley [4], was proved by Blum [1] using generating functions. However, several structural questions about these special permutations remained open. This paper presents an alternative and constructive proof for this conjecture, which highlights the deeper interplay between cycle structures and square properties. At the same time, we demonstrate that all permutations with an even number of even cycles in both \(S_{2n}\) and \(S_{2n+1}\) can be categorized into three disjoint types that correspond to each other.
Let \(n\) be a positive integer and \([n] = \{1,2,…,n\}\) denote the set of positive integers at most \(n\). We know that every permutation in the symmetric group \(S_n\) can be written as a product of disjoint cycles. Given \(m\) distinct numbers \(a_1, a_2, …, a_m\) in \([n]\), \((a_1, a_2, … ,a_m)\) denotes the \(m\)-cycle \(a_1\rightarrow a_2\rightarrow \cdots \rightarrow a_m \rightarrow a_1\).
To begin with, let us recall the notions provided by Stanley [4] (p.13). Let \(w\in S_n\). We say that \(w\) is a perfect square permutation if there exists \(u\in S_n\) such that \(u^2 = w\). We define \(\alpha(n)\) to be the number of perfect square permutations in \(S_n\). Some direct enumerations are provided in the table below [3].
By observing Table 1, it seems to be true that \(\alpha(2n+1) = (2n+1)\alpha(2n)\) for all \(n\in \mathbb{Z}^+\). This suggests an intriguing relationship between the numbers of perfect square permutations in \(S_{2n}\) and \(S_{2n+1}\). In particular, this means the ratio between the two counts is always \(2n+1\). In 1973, Blum [1] proved this conjecture using a generating function. In this paper, we give a combinatorial proof.
| \(n\) | \(\alpha(n)\) |
|---|---|
| 2 | 1 |
| 3 | 3 |
| 4 | 12 |
| 5 | 60 |
| 6 | 270 |
| 7 | 1890 |
| 8 | 14280 |
| 9 | 128520 |
| 10 | 1096200 |
| 11 | 12058200 |
| 12 | 139043520 |
| 13 | 1807565760 |
| 14 | 22642139520 |
| 15 | 339632092800 |
| 16 | 5237183952000 |
| 17 | 89032127184000 |
In order to enhance clarity and ease of understanding, a Table 2 summarizing some basic notations used in this paper is provided below.
| Notations | Descriptions |
|---|---|
| \(PS\) | Perfect square permutation(s) |
| \(NPS\) | Non-perfect square permutation(s) |
| \(EE\) | Permutation(s) with an even number of even cycles |
| \(OE\) | Permutation(s) with an odd number of even cycles |
| \(PS_n\) | The set of perfect square permutations in \(S_n\) |
| \(NPS_n\) | The set of non-perfect square permutations in \(S_n\) |
| \(EE_{n}\) | The set of permutations in \(S_n\) with an even number of even cycles |
| \(OE_{n}\) | The set of permutations in \(S_n\) with an odd number of even cycles |
Lemma 1.1. Let \(n, m\in \mathbb{Z}^+\) and \(m\leq n\). Let \(u=(a_1, a_2, … ,a_m)\) be an \(m\)-cycle in \(S_n\).
(a) If \(m\) is even, then \(u^2\) splits into two disjoint cycles with the length \(\frac{m}{2}\).
(b) If \(m\) is odd, then \(u^2\) remains an \(m\)-cycle.
Proof. It is readily checked that for all \(k\in \mathbb{Z}^+\), \((a_1, a_2, … ,a_{2k})^2= \\(a_1, a_3, …, a_{2k-1})(a_2, a_4, …, a_{2k})\), \((a_1, a_2, … ,a_{2k+1})^2= (a_1, a_3, …, a_{2k+1}, a_2, a_4, …, a_{2k})\). ◻
Remark 1.2. Every odd cycle is a perfect square.
Lemma 1.3(Necessary Condition).Let \(n\in \mathbb{Z}^+\). If \(w\in PS_n\), then \(w\in EE_n\).
Proof. Assume \(w=u^2\) for some \(u\in S_n\). We write \(u\) as a product of disjoint cycles \[u = \displaystyle\prod_{i\in [k]}u_i,\] for some \(k\in \mathbb{Z}^+\) and \(k\leq n\).
By Lemma 1.1, each even cycle of \(u\) splits into two disjoint cycles of half the length, while each odd cycle remains of the same length after squaring. Consequently, in \(u^2\) the even cycles always appear in pairs, so,\(\displaystyle\prod_{i\in [k]}u_i\) consists of disjoint and pairs of even cycles. ◻
Remark 1.4. Since all odd cycles are perfect squares (by Remark 1.2), the determination of whether a permutation is \(PS\) or \(NPS\) depends solely on the partition of its even cycles – specifically, the number of even cycles with the same length in \(PS\) must be even. Some examples are provided below.
Example 1.5(\(PS\) and \(NPS\) in \(EE_n\)).\[\begin{aligned} &(1,2)(3,4)(5)(6)(7)(8) \in PS_8\\ &(1,2)(3,4,9,10)(5)(6)(7)(8) \in NPS_{10}\\ &(1,2)(3,4)(5,6,7,8)(9,10,11,12)(13) \in PS_{13}\\ &(1,2,3,4,5,6)(7,8)(9)\in NPS_9. \end{aligned}\]
By the necessary condition discussed in Lemma 1.3, we may focus only on permutations with an even number of even cycles. A direct bijective proof may be tempting, but after considering various partitions, we decide to divide both \(EE_{2n}\) and \(EE_{2n+1}\) into three different types, and then construct bijections between corresponding types.
Furthermore, now that \(PS_{n} \subset EE_n\), we can analyze the perfect square permutations within each type. We will later show that it is possible to establish bijections between \([2n+1] \times PS_{2n}\) and \(PS_{2n+1}\) for each type.
Definition 1.6. Let \(n\in \mathbb{Z}^+\). We divide \(EE_{2n}\) into three disjoint types:
Type \(1\), denoted as \(EE^{(1)}_{2n}:= \{w\in EE_{2n}:w\) has only even cycles}.
Type \(2\), denoted as \(EE^{(2)}_{2n}:= \{w \in EE_{2n}:w\) has only odd cycles}.
Type \(3\), denoted as \(EE^{(3)}_{2n}:= \{w\in EE_{2n}:w\) has both even and odd cycles}.
Note that: \[|EE_{2n}| = \displaystyle\sum_{i\in [3]} |EE_{2n}^{(i)}|.\]
Definition 1.7. Let \(n\in \mathbb{Z}^+\). We divide \(EE_{2n+1}\) into three disjoint types:
Type \(1\), denoted as \(EE^{(1)}_{2n+1}:=\{w\in EE_{2n+1}:w\) consists of even cycles and one \(1\)-cycle}.
Type \(2\), denoted as \(EE^{(2)}_{2n+1}:=\{w\in EE_{2n+1}:w\) has only odd cycles}.
Type \(3\), denoted as \(EE^{(3)}_{2n+1}:=\{w\in EE_{2n+1}:w\) has both even and odd cycles}\(\backslash EE^{(1)}_{2n+1}\).
Note that: \[|EE_{2n+1}| = \displaystyle\sum_{i\in [3]} |EE_{2n+1}^{(i)}|.\]
Definition 1.8. Let \(i\in [3]\) and \(n\in \mathbb{Z}^+\). Define \(PS_n^{(i)}:= EE_n^{(i)} \cap PS_n\).
We are now ready to state our main results.
Theorem 1.9. \(|EE^{(i)}_{2n+1}| = (2n+1)|EE^{(i)}_{2n}|\) for every \(i\in [3]\).
Theorem 1.10. \(|PS^{(i)}_{2n+1}| = (2n+1)|PS^{(i)}_{2n}|\) for every \(i\in [3]\).
Corollary 1.11. \(\alpha(2n+1) = (2n+1)\alpha(2n)\).
This paper employs a special mapping method that plays an important role in the proofs of the theorems presented later. In this section, we explain how the Adding and Swapping Mapping Method works.
Definition 1.12(Adding and swapping mapping).Let \(n \in \mathbb{Z}^+\) and let \(w \in S_{2n}\) be a permutation with no \(1\)-cycle. We associate to \(w\) a family of \(2n+1\) permutations in \(S_{2n+1}\), denoted \(D_i(w)\) for \(1 \leq i \leq 2n+1\), as follows:
\(D_{2n+1}(w) := w \, (2n+1)\).
For \(1 \leq i \leq 2n\), \(D_i(w)\) is obtained from \(w \,(2n+1)\) by swapping the elements \(i\) and \(2n+1\).
Example 1.13. Take \(w=(1,2)(3,4,5,6)\in S_6\). Then \[\begin{aligned} D_1(w)&=(7,2)(3,4,5,6)(1),\\ D_2(w)&=(1,7)(3,4,5,6)(2),\\ D_3(w)&=(1,2)(7,4,5,6)(3),\\ D_4(w)&=(1,2)(3,7,5,6)(4),\\ D_5(w) &= (1,2)(3,4,7,6)(5),\\ D_6(w) &= (1,2)(3,4,5,7)(6),\\ D_7(w)&=(1,2)(3,4,5,6)(7). \end{aligned}\]
Remark 1.14. For our purpose, we define the Adding and Swapping Mapping Method from \(S_{2n}\) to \(S_{2n+1}\). Indeed, this mapping method can be defined from \(S_n\) to \(S_{n+1}\), for all \(n\in \mathbb{Z}^+\).
In this section, we introduce some simple lemmas that serve as prototypes for Theorem 1.9 and Theorem 1.10.
Lemma 1.15. If \(n \geq 2\), \(|EE_n| = |OE_n|\).
The simple proof of this lemma is left to the reader. A bijective proof is provided in [2].
Lemma 1.16. \(|EE_{2n+1}| = (2n+1)|EE_{2n}|\).
This can be proved easily by realizing \(EE\) and \(OE\) are equally distributed in \(S_n\) (Lemma 1.15).
Remark 1.17. The lemmas above imply that \(|OE_{2n+1}| = (2n+1)|OE_{2n}|\).
In this section, we prove Theorem 1.9.
Note that: \[\begin{aligned} \sum_{i\in[3]}|EE^{(i)}_{2n+1}| &= |EE_{2n+1}| &\qquad &(\text{By Definition 1.7})\\ &= (2n+1)|EE_{2n}| &\qquad & (\text{By Lemma 1.16})\\ &= (2n+1)\sum_{i\in [3]}|EE^{(i)}_{2n}|. &\qquad &(\text{By Definition 1.6}) \end{aligned}\]
We will study the three types of \(EE_n\) separately. For type 1, we establish the following proposition.
Proposition 2.1. \(|EE^{(1)}_{2n+1}|= (2n+1)|EE^{(1)}_{2n}|\).
Proof. Note that all cycles in \(EE^{(1)}_{2n}\) have their cycle lengths greater than \(1\) (Definition 1.6).
In this case, we can apply the Subsection 1.3. Each permutation in \(EE^{(1)}_{2n}\) gets mapped to \((2n+1)\) different permutations in \(EE^{(1)}_{2n+1}\). ◻
Building on Theorem 1.9: type 1 in Proposition 2.1, we know that \[\label{1} |EE^{(2)}_{2n+1}|= (2n+1)|EE^{(2)}_{2n}| \iff |EE^{(3)}_{2n+1}|= (2n+1)|EE^{(3)}_{2n}|. \tag{1}\]
As a result, it is sufficient to prove just one of the two equations on either side of the double arrow.
We next give a proof for \(|EE_{2n+1}^{(i)}|= (2n+1)|EE_{2n}^{(i)}|\) for \(i=2,3\). Additionally, we will prove one of the three types for Theorem 1.10, which is \(PS^{(3)}_{2n+1} = (2n+1)PS^{(3)}_{2n}\).
Definition 2.2. Let \(n\in \mathbb{Z}^+\) and \(\eta \in EE^{(3)}_{n}\). Define \(A_\eta\) to be the set of all elements in odd cycles in \(\eta\).
Definition 2.3. Let \(n\in \mathbb{Z}^+\) and \(A\subset [n]\). Define \[EE^{(3):A}_{n} := \{\eta \in EE^{(3)}_{n}: A_\eta = A\}.\]
Lemma 2.4. If \(A\subset [2n+1]\), \(|A| = 2c+1\) for some \(c\in \mathbb{Z}^+\) and \(c < n\). Then \[EE^{(3):A}_{2n+1} \cong (EE^{(1)}_{2n-2c} \times EE^{(2)}_{2c+1}).\]
Proof. \[\begin{aligned} EE^{(3):A}_{2n+1} &= \{\eta \in EE^{(3)}_{2n+1}: A_\eta = A\}\\ &= \{\eta\in S_{2n+1}: \{i\in [2n+1]: \text{the length of the cycle containing $i$ is odd}\} = A\}\\ &\cong (EE^{(1)}_{2n-2c} \times EE^{(2)}_{2c+1}). \end{aligned}\]
The insight behind the last line is that, instead of focusing on the partition of the entire \(EE^{(3)}_{2n+1}\), we examine each permutation in two separate parts: the partition of even cycles and the partition of odd cycles. Referring to the three types of \(EE_{2n+1}\) in Definition 1.7, the partition of only odd or only even cycles can be found in \(EE^{(1)}_{2n}\) or \(EE^{(2)}_{2n+1}\), respectively. ◻
Example 2.5. Take \(A = \{5,6,7\}\) and \((1,2)(3,4)(5,6,7) \in EE^{(3):A}_{7}\).
This permutation has a partition \((2,2,3)\). By focusing on the partitions of even and odd cycles separately, we see \((1,2)(3,4)\) as \((2,2)\), a partition of \(EE^{(1)}_{4}\), and \((5,6,7)\) as \((3)\), a partition of \(EE^{(2)}_3\).
Proposition 2.6. (a) \(|EE^{(2)}_{2n+1}|= (2n+1)|EE^{(2)}_{2n}|\).
(b) \(|EE^{(3)}_{2n+1}|= (2n+1)|EE^{(3)}_{2n}|\).
We will use strong induction to show some interim results and then bijectively prove Proposition 2.6. Furthermore, we will present a partial result for Theorem 1.10.
Proof. Assume \(|EE^{(i)}_{2k+1}| = (2k+1)|EE^{(i)}_{2k}|,\) for all \(k\in \mathbb{Z}^+, 1\leq k\leq n-1\) and \(i = 2,3.\)
Fix \(a\in A \subset [2n+1]\), \(|A| = 2c+1, 1\leq c \leq n-1.\)
By induction hypothesis, with \((k=c,\ i=2)\), we have \(|EE^{(2)}_{2c+1}|= (2c+1)|EE^{(2)}_{2c}|.\)
We use strong induction to show that \[\label{(2)} \displaystyle \sum_{\substack{\eta \in EE_{2n+1}^{(3)} \\ A_\eta = A}} 1 = (2c+1) \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = A \backslash \{a\}}}1. \tag{2}\]
Moreover, \[\displaystyle \sum_{\substack{\eta \in PS_{2n+1}^{(3)} \\ A_\eta = A}} 1 = (2c+1) \sum_{\substack{\eta \in PS_{2n}^{(3)} \\ A_\eta = A \backslash \{a\}}}1.\]
For LHS: \[\begin{aligned} \displaystyle \sum_{\substack{\eta \in EE_{2n+1}^{(3)} \\ A_\eta = A}} 1 &= |EE^{(3):A}_{2n+1}|\\ &= |EE^{(1)}_{2n-2c} \times EE^{(2)}_{2c+1}| &\qquad &(\text{By Lemma 2.4})\\ &= |EE^{(1)}_{2n-2c} \times [2c+1] \times EE^{(2)}_{2c}| &\qquad &(\text{By induction hypothesis})\\ &= (2c+1) \left| EE^{(1)}_{2n-2c} \right| \left| EE^{(2)}_{2c} \right|. \end{aligned}\]
For RHS: \[\begin{aligned} (2c+1) \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = A \backslash \{a\}}}1 &= (2c+1) |\{\eta \in S_{2n}: A_\eta = A \backslash \{a\}\} |\\ &=(2c+1)|EE^{(1)}_{2n-2c}||EE^{(2)}_{2c}|. \end{aligned}\]
Note that \(EE^{(3)}_{2n+1} = PS_{2n+1}^{(3)} \cup (NPS_{2n+1} \cap EE^{(3)}_{2n+1})\). In the proof above, we only apply induction to all odd cycles in \(EE^{(3)}_{2n+1}\), without loss of generality (by Remark 1.4): \[\displaystyle \sum_{\substack{\eta \in PS_{2n+1}^{(3)} \\ A_\eta = A}} 1 = (2c+1) \sum_{\substack{\eta \in PS_{2n}^{(3)} \\ A_\eta = A \backslash \{a\}}}1.\]
We will now bijectively show that: \[|EE^{(3)}_{2n+1}|= (2n+1)|EE^{(3)}_{2n}|.\]
Moreover, \[|PS^{(3)}_{2n+1}|= (2n+1)|PS^{(3)}_{2n}|.\]
For LHS: \[\begin{aligned} \left|EE^{(3)}_{2n+1}\right| &= \sum_{\substack{A \subset [2n+1] \\ 1 < |A| < 2n+1}} \sum_{a\in A} \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = A \backslash \{a\}}} 1 &\qquad &(\text{By (2) })\\ &= \sum_{a\in [2n+1]} \sum_{\substack{A \subset [2n+1] \\ 1 < |A| < 2n+1\\ a\in A}} \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = A \backslash \{a\}}} 1 &\qquad &(\text{Change the order})\\ &= (2n+1) \sum_{\substack{A \subset [2n+1] \\ 1 < |A| < 2n+1\\ 2n+1\in A}} \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = A \backslash \{2n+1\}}} 1. &\qquad &(\text {By symmetry}) \end{aligned}\]
For RHS: \[\begin{aligned} (2n+1)|EE^{(3)}_{2n}| = (2n+1)\sum_{\substack{B \subset [2n] \\ 1 < |B| < 2n}} \sum_{\substack{\eta \in EE^{(3)}_{2n} \\ A_\eta = B}} 1. \end{aligned}\]
Using change of variable: \(B = A \backslash \{2n+1\}\) and \(A = B \cup \{2n+1\}\), we know that, \(|EE^{(3)}_{2n+1}|= (2n+1)|EE^{(3)}_{2n}|\), which (according to (1)) implies the validity of \(|EE^{(2)}_{2n+1}|= (2n+1)|EE^{(2)}_{2n}|\). ◻
The bijective proof above focuses only on the odd cycles of each permutation in \(EE^{(3)}_{2n+1}\). Therefore, by Remark 1.4, the same method is applicable to \(PS^{(3)}_{2n+1} \subset EE^{(3)}_{2n+1}\). Thus we have the following.
Corollary 2.7. \(|PS^{(3)}_{2n+1}|= (2n+1)|PS^{(3)}_{2n}|\).
In this section, we prove Theorem 1.10.
The proof of this theorem is very similar to the Section 2. We will prove the equations for the three types individually.
Proposition 3.1. \(|PS^{(1)}_{2n+1}| = (2n+1)|PS^{(1)}_{2n}|\).
Proof. Note that \(PS_n^{(1)}\subset EE^{(1)}_n\) (by Definition 1.8), applying the same the adding and swapping mapping method (Subsection 1.3), we confirm that \(|PS^{(1)}_{2n+1}| = (2n+1)|PS^{(1)}_{2n}|\). ◻
Proposition 3.2. \(|PS^{(2)}_{2n+1}| = (2n+1)|PS^{(2)}_{2n}|\).
Proof. By Definition 1.8, we clearly have \(PS_n^{(2)}\subset EE^{(2)}_n\). Conversely, by Remark 1.2, it is clear that every odd cycle is a perfect square. Since every permutation in \(EE^{(2)}_n\) is a product of all odd cycles (recall Definition 1.6 and Definition 1.7), every permutation in \(EE^{(2)}_n\) is also in \(PS_n^{(2)}\). Thus, \(EE^{(2)}_n \subset PS^{(2)}_n\).
Now using the result from Theorem 1.9, we have \[|PS^{(2)}_{2n+1}| = |EE^{(2)}_{2n+1}| = (2n+1)|EE^{(2)}_{2n}| = (2n+1)|PS^{(2)}_{2n}|,\] proving the proposition. ◻
Regarding type 3, Corollary 2.7 in Section 2 gives the result.
Corollary 3.3. Finally, we give a combinatorial proof of Stanley’s conjecture.
Proof of Corollary 3.3. Recall that \(\alpha(n)\) represents the number of perfect square permutations in \(S_n\). Thus, we have \(\alpha(n) = \displaystyle\sum_{i\in [3]} |PS_n^{(i)}|\).
Therefore, by Theorem 1.10, \[\begin{aligned} \alpha(2n+1) = \sum_{i\in [3]}|PS^{(i)}_{2n+1}| = (2n+1)\sum_{i \in [3]}|PS^{(i)}_{2n}| = (2n+1)\alpha(2n), \end{aligned}\] as desired. ◻
After presenting our main results that are related to \(EE_n\), we now explore the possible types in \(OE_n\). Similar to Theorem 1.9, we will show that there are three disjoint types for both \(OE_{2n}\) and \(OE_{2n+1}\), which correspond to each other.
Definition 4.1. We divide \(OE_{2n}\) into three disjoint types:
Type 1, denoted \(OE_{2n}^{(1)}:=\{w\in OE_{2n}: w\) has only even cycles}.
Type 2, denoted \(OE_{2n}^{(2)}:=\{w\in OE_{2n}:w\) has no \(1\)-cycle} \(\backslash OE_{2n}^{(1)}\).
Type 3, denoted \(OE_{2n}^{(3)}:=\{w\in OE_{2n}:w\) has at least one \(1\)-cycle}.
Note that: \[|OE_{2n}| = \displaystyle\sum_{i\in [3]} |OE_{2n}^{(i)}|.\]
Definition 4.2. Let \(n\in \mathbb{Z}^+\). We can divide \(OE_{2n+1}\) into three distinct types:
Type 1, denoted \(OE_{2n+1}^{(1)}:=\{w\in OE_{2n+1}:w\) only has even cycles and one \(1\)-cycle}.
Type 2, denoted \(OE_{2n+1}^{(2)}:=\{w\in OE_{2n+1}:w\) only has one \(1\)-cycle} \(\backslash OE_{2n+1}^{(1)}\).
Type 3, denoted \(OE_{2n+1}^{(3)}:= OE_{2n+1}\) \(\backslash (OE_{2n+1}^{(2)} \cup OE_{2n+1}^{(1)})\).
Note that: \[|OE_{2n+1}| = \displaystyle\sum_{i\in [3]}|OE_{2n+1}^{(i)}|.\]
Corollary 4.3. \(|OE_{2n+1}^{(i)}| = (2n+1)|OE_{2n}^{(i)}|\), for all \(n\in \mathbb{Z}^+\) and \(i \in [3]\).
Proof. By applying the Subsection adding and swapping mapping method 1.3, we can effortlessly derive \[|OE_{2n+1}^{(i)}| = (2n+1)|OE_{2n}^{(i)}|\text{, for } i = 1, 2.\] By Remark 1.17, we confirm that \(|OE_{2n+1}| = (2n+1)|OE_{2n}|\). Therefore, \[|OE_{2n+1}^{(3)}| = (2n+1) |OE_{2n}^{(3)}|.\] ◻
We hope the methods demonstrated in this paper will be beneficial for future research in this area. We are particularly interested in identifying more potential types within \(S_{2n}\) and \(S_{2n+1}\) that may provide special formulations similar to those proposed in Theorem 1.9 and Theorem 1.10. Additionally, it will be very interesting to see if our methods can be applied when dealing with higher powers.
I wish to extend my sincere appreciation to my supervisor, Jiyuan (Maki) Lu, for his support, guidance, and mentorship throughout this research. Additionally, I would like to express my gratitude to Professor Richard P. Stanley for providing the formulation that served as the foundation of this work. Finally, I am thankful to my research group member, Parham Tayyebi, for the insightful discussions that have greatly enriched this research.