平等的；相等的；均等的

《Journal of Algebra》：Equal knapsack identities between symmetric group character degrees

　　

摘要

我们证明了关于对称群不可约特征标度的一整系列"背包"类型的等式。也就是说，我们找到了 n 的划分的若干不相交集，使得对应的两个特征标度之和相等。我们的主要结果深化了我们近期对 Riordan 数的描述——Riordan 数等于所有满足 λ 为 n 的三部分划分且三部分奇偶性相同时的特征标度 $f_\lambda$ 之和。特别地，"胖钩"度 $f_{(k,k,1^{n-2k})} + f_{(k+1,k+1,1^{n-2k-2})}$ 之和等于所有满足 λ 为三部分划分、第二部分等于 k 且第二、三部分奇偶性相同时的 $f_\lambda$ 之和。我们进一步证明了无穷多个额外的特征标度之间的"背包"恒等式。

引言

设 $\Sigma_n$ 为 n 个字母上的对称群，回忆一下，$\Sigma_n$ 的复不可约特征标由 n 的划分标记。与划分 $\lambda \vdash n$ 对应的不可约特征标的度等于形状为 $\lambda$ 的标准 Young 表的个数，记为 $f_\lambda$。

著名的 Catalan 数 $C(n)$ 枚举了数百个不同的集合 [8]，包括半长度为 n 的 Dyck 路径（即从 $(0,0)$ 到 $(2n,0)$ 使用步长 $U=(1,1)$ 和 $D=(-1,1)$ 且不越过 x 轴的路径）。它们也计算形状为 $(n,n)$ 的标准 Young 表的个数，即 $C(n) = f_{(n,n)}$。若允许水平步长，则得到 Motzkin 路径，即从 $(0,0)$ 到 $(n,0)$ 仅使用步长 $U=(1,1)$、$F=(1,0)$ 和 $D=(1,-1)$ 且不越过 x 轴的路径。这些路径由 Motzkin 数 $M(n)$ 枚举，即 [6] 中的序列 A001006。众所周知，$M(n)$ 也计算大小为 n 且行数不超过三行的标准 Young 表的个数；一个双射的例子见 [5]。在我们的记号中，这个计数可以表示为
$$M(n) = \sum_{\lambda=(\lambda_1,\lambda_2,\lambda_3)\vdash n} f_\lambda$$
这里及下文，我们允许部分为零。因此，(1.1) 对所有最多三个非零部分的划分求和。

Riordan 路径是额外的要求是 x 轴上不能有水平步 F 的 Motzkin 路径。设 $R(n)$ 为长度为 n 的 Riordan 路径的个数；这是 [6] 中的序列 A005043。Riordan 数 $R(n)$ 在对称群不可约特征标度方面还有以下解释。这是 Regev 在 OEIS 条目中给出的评论（证明见 [3]）。

命题 1.1 [3, 命题 1.2] 设 $0 \leq m < n$。长度为 n、有 m 个水平步和 k 个上升步（从而有 k 个下降步）的 Riordan 路径的个数为 $f_{(k,k,1^m)}$。

在 [3] 中，我们将 $R(n)$ 解释为 $f_\lambda$ 之和，但不是对所有三部分划分（如 $M(n)$ 那样），而是对那些三部分奇偶性相等的三部分划分（必然是 n 的奇偶性）求和。

定理 1.2 [3, 定理 4.5] 设 $X = \{(\lambda_1,\lambda_2,\lambda_3)\vdash n \mid \lambda_1 \equiv \lambda_2 \equiv \lambda_3 \pmod{2}\}$，$Y = \{(k,k,1^{n-2k}) \mid 1 \leq k \leq \lfloor n/2 \rfloor\}$。则：
$$\sum_{\lambda \in X} f_\lambda = \sum_{\mu \in Y} f_\mu = R(n)$$

我们注意到 [5] 中证明 (1.1) 的双射并不将 Riordan 路径映射到部分奇偶性相等的形状的表上。事实上，我们不知道定理 1.2 的双射证明。

在本文中，我们证明 (1.2) 中的等式可以细化为一组等式，每个选择第二部分的值 $\lambda_2$ 对应一个等式。例如，当 $n = 20$ 时，我们在 (1.3) 中证明了：
$$f_{(20)} = f_{(1^{20})}$$
$$f_{(18,2)} + f_{(16,2,2)} = f_{(2,2,1^{16})} + f_{(3,3,1^{14})}$$
$$f_{(16,4)} + f_{(14,4,2)} + f_{(12,4,4)} = f_{(4,4,1^{12})} + f_{(5,5,1^{10})}$$
$$f_{(14,6)} + f_{(12,6,2)} + f_{(10,6,4)} + f_{(8,6,6)} = f_{(6,6,1^{8})} + f_{(7,7,1^{6})}$$
$$f_{(12,8)} + f_{(10,8,2)} + f_{(8,8,4)} = f_{(8,8,1^{4})} + f_{(9,9,1^{2})}$$
$$f_{(10,10)} = f_{(10,10)}$$

我们尝试使用对称群不可约特征标的分支法则通过归纳法来证明这些恒等式。然而，分支法则不保持奇偶性条件，这要求我们发现并一起证明三组额外的恒等式，使用单个归纳证明。然而，即使这四个恒等式加在一起，也不在分支法则下保持不变，因此尝试归纳证明会产生不受归纳假设约束的误差项。这些误差项导致了在特征标度之间发现另外两组恒等式（见第 2 节），这些恒等式可以直接使用钩长公式证明，从而使我们可以用归纳法证明四个主要恒等式。

这四个恒等式记录在以下定理中，这是我们的第一个主要结果。注意，恒等式 (1.3) 在 $k \equiv n \pmod{2}$ 时始终成立，它足以证明我们上述描述的定理 1.2 的细化。

定理 1.3 设 n 和 k 为正整数，使得 $k \leq \frac{n}{2} - 1$。设
$$X_0(n,k) = \{(\lambda_1, k, \lambda_3)\vdash n \mid k \equiv \lambda_3 \pmod{2}\}$$
$$X_1(n,k) = \{(\lambda_1, k, \lambda_3)\vdash n \mid k \not\equiv \lambda_3 \pmod{2}\}$$

若 $k \leq \lceil \frac{n}{3} \rceil$ 或 $k \equiv n \pmod{2}$，则
$$\sum_{\lambda \in X_0(n,k)} f_\lambda = f_{(k,k,1^{n-2k})} + f_{(k+1,k+1,1^{n-2k-2})}$$
以及
$$\sum_{\lambda \in X_1(n,k)} f_\lambda = f_{(k+1,k,1^{n-2k-1})}$$

若 $k > \lceil \frac{n}{3} \rceil$ 且 $k \not\equiv n \pmod{2}$，则上述等式在 $X_0$ 和 $X_1$ 互换后成立。

若我们采用约定，当 λ 不是划分时 (1.3) 和 (1.4) 右端的任何项 $f_\lambda$ 为零，则定理 1.3 的陈述对所有非负整数 n 和 k 的值成立。

在上面，我们已经展示了 $n=20$ 且 $k \equiv n \pmod{2}$ 时的等式 (1.3)。接下来，我们简要展示 (1.3) 和 (1.4) 这两个等式对另外一些 n 和 k 的选择成立。例如，对于 $n=32$，$k=11$，两个等式变为：
$$f_{(20,11,1)} + f_{(18,11,3)} + f_{(16,11,5)} + f_{(14,11,7)} + f_{(12,11,9)} = f_{(11,11,1^{10})} + f_{(12,12,1^{8})}$$
$$f_{(21,11,0)} + f_{(19,11,2)} + f_{(17,11,4)} + f_{(15,11,6)} + f_{(13,11,8)} + f_{(11,11,10)} = f_{(12,11,1^{9})}$$

类似地，对于 $n=32$，$k=12$，等式为：
$$f_{(20,12,0)} + f_{(18,12,2)} + f_{(16,12,4)} + f_{(14,12,6)} + f_{(12,12,8)} = f_{(12,12,1^{8})} + f_{(13,13,1^{6})}$$
$$f_{(19,12,1)} + f_{(17,12,3)} + f_{(15,12,5)} + f_{(13,12,7)} = f_{(13,12,1^{7})}$$

另一方面，对于 $n=32$，$k=13$，我们得到：
$$f_{(18,13,1)} + f_{(16,13,3)} + f_{(14,13,5)} = f_{(14,13,1^{5})}$$
$$f_{(19,13,0)} + f_{(17,13,2)} + f_{(15,13,4)} + f_{(13,13,6)} = f_{(13,13,1^{6})} + f_{(14,14,1^{4})}$$

在下一节中，我们证明定理 1.3 归纳证明所需的两条辅助恒等式，然后在第 3 节中概述定理 1.3 的证明，完整细节见附录。在第 4 节中，我们展示了第 2 节的辅助恒等式可以大大扩展。作为这些扩展的应用，即我们的第二个主要结果，我们给出了定理 1.3 中恒等式 (1.3) 的另一种证明。最后，我们提出了额外的问题并猜想进一步的恒等式。

章节片段

辅助恒等式

在本节中，我们证明两条在特征标度之间的恒等式，它们具有独立的研究价值，并且是用分支法则归纳证明定理 1.3 的必要成分。与定理 1.3 中的恒等式不同，这两条辅助恒等式是固定长度的，因此我们能够直接利用钩长公式来证明它们。

回忆一下，对于划分 $\lambda \vdash n$ 及其共轭划分 $\lambda'$，形状为 $\lambda$ 的标准 Young 表的个数由著名的钩长公式给出。

定理 1.3 通过分支法则的证明

回忆一下，分支法则描述了当对称群 $\Sigma_n$ 的不可约特征标限制到 $\Sigma_{n-1}$ 时如何分解。对于 $\lambda \vdash n$，维数 $f_\lambda$ 等于所有通过从 λ 的 Young 图中移除一个格子使得结果仍是 $n-1$ 的合法划分的 $\gamma \vdash n-1$ 对应的 $f_\gamma$ 之和。

定理 1.3 的证明是对 n 进行归纳。由于小 n 值容易验证，我们假设定理中所有可能的等式对所有小于 n 的值成立。

一个扩展和一个替代证明

让我们考虑求和
$$L_d(k,m) = \sum_{j=0}^{d-1} f_{(k+j, k+j, 1^{m-2j})}$$

用这个记号，引理 2.3 表明
$$L_3(k,m) = f_{(k+2,k,1^{m-2})} + \begin{cases} f_{(k,k,m)}, & \text{若 } m \leq k, \\ 0, & \text{若 } m = k+1 \text{ 或 } m = k+2, \\ f_{(m-2,k+1,k+1)}, & \text{若 } m \geq k+3. \end{cases}$$

在本节中，我们表明这可以扩展到所有奇数 d 的求和 $L_d(k,m)$。然后我们展示这个扩展提供了一种替代方法来证明定理 1.3 中定理 1.2 的细化。

在讨论一般情况之前，我们首先强调 $d=5$ 的情况。

例子 4.1 设 $k \geq 2$ 且 $m \geq 4$。若 $m \leq k$，则
$$L_5(k,m) =$$

结论

我们的主要结果，定理 1.3 和定理 4.2，以及辅助结果如引理 2.3，都是以下形式的特征标度恒等式的实例：
$$\sum_{\lambda \in X_n} f_\lambda = \sum_{\mu \in Y_n} f_\mu$$
其中 $X_n$ 和 $Y_n$ 是大小 n 的划分的某些集合。可以将 (5.1) 理解为将各种 λ 作为书、$f_\lambda$ 作为相应的重量，装入两个"背包"中，使两个背包的重量相等。自然会想，是否还能找到更多具有 (5.1) 形式的有趣结果。

致谢

我们感谢匿名审稿人对本文早期草稿进行的非常详细和彻底的阅读。

David J. Hemmer | Armin Straub | Karlee J. Westrem