4.8　习题Exercises

本页为译文 + 高中讲解合一：黑色正文（有序列表中的题目）为忠实翻译；每题之后的彩色框（解题思路 / 方法提示 / 分步推演 / 例 / 配图）是面向高中生的引导。习题只给出切入点与方法，不给完整最终答案（完整解答见对应“习题解答”一节）。本页所用记号沿用第 4 章：\(A(n,k)\) 为欧拉数（Eulerian number，统计有 \(k\) 个上升段的 \(n\) 排列个数），\(S(n,k)\) 为第二类斯特林数（Stirling number），\(s(n,k)\)、\(c(n,k)\) 为带符号 / 无符号第一类斯特林数，\(D(n)\) 为错位排列（derangement）数，\(C_n\) 为卡塔兰数（Catalan number），\(b(n,k)\) 为恰有 \(k\) 个逆序（inversion）的 \(n\) 排列个数，\(i(p)\) 为排列 \(p\) 的逆序数。

1. 证明：对所有满足 \(k\le n\) 的正整数 \(k,n\)，都有 \(A(n,k)=A(n,\,n+1-k)\)。试给出两种不同的解法。

   思路这是欧拉数的对称性。\(A(n,k)\) 数的是恰有 \(k\) 个上升段（ascending run，等价地 \(k-1\) 个下降位）的 \(n\) 排列。要建立 \(k\) 个上升段的排列与 \(n+1-k\) 个上升段的排列之间的一一对应（bijection）。

   1. 解法一（翻转对应）：取排列 \(p=p_1p_2\cdots p_n\)，作互补反转 \(\bar p_i=n+1-p_i\)。原来的上升 \(p_i<p_{i+1}\) 变成下降 \(\bar p_i>\bar p_{i+1}\)，于是上升位与下降位互换，上升段数从 \(k\) 变为 \(n+1-k\)。
   2. 解法二（生成多项式）：用欧拉多项式 \(A_n(t)=\sum_k A(n,k)t^k\) 满足 \(t^{n+1}A_n(1/t)=A_n(t)\) 的回文（palindrome）性质，逐项比较系数。
   具体例取 \(n=3\)：\(A(3,1)=1\)（仅 \(123\)），\(A(3,2)=4\)，\(A(3,3)=1\)（仅 \(321\)）。果然 \(A(3,1)=A(3,3)\)。如 \(123\xrightarrow{\bar p_i=4-p_i}321\)，一个上升段变成一个上升段……更典型地 \(132\)（2 段）映到 \(312\)（2 段）。

2. 设 \(S\subseteq[n-1]\)，记 \(\alpha(S)\) 为下降集（descent set）包含于 \(S\) 的 \(n\) 排列的个数。求使 \(\alpha(\{i\})\) 取最大值的单元素集 \(\{i\}\subseteq[n-1]\)。

   思路“下降集包含于 \(\{i\}\)”意味着排列除了可能在第 \(i\) 个位置下降外，其余位置全为上升。也就是 \(p_1<p_2<\cdots<p_i\) 且 \(p_{i+1}<\cdots<p_n\)：前 \(i\) 个递增、后 \(n-i\) 个递增。

   1. 这种排列完全由“前 \(i\) 个位置放哪 \(i\) 个数”决定，故 \(\alpha(\{i\})=\dbinom{n}{i}\)。
   2. 二项式系数在 \(i=\lfloor n/2\rfloor\)（或 \(\lceil n/2\rceil\)）处最大，故取中间值。

3. 设 \(n=10\)，\(S=[3,7]\)（即 \(\{3,4,5,6,7\}\)）。计算 \(\alpha(\{3,7\})\)。

   思路注意题目要算的是 \(\alpha(\{3,7\})\)（下降集 \(\subseteq\{3,7\}\)）。这类排列被 \(\{3,7\}\) 切成三个递增段：位置 \(1\!\sim\!3\)、\(4\!\sim\!7\)、\(8\!\sim\!10\)，各段内部严格递增。

   1. 计数方式为多重组合：把 \(10\) 个数分到三段（大小 \(3,4,3\)），段内顺序唯一。
   2. 故 \(\alpha(\{3,7\})=\dbinom{10}{3,\,4,\,3}=\dfrac{10!}{3!\,4!\,3!}\)。算出即得答案（用第 4 题的通式可直接套）。

4. 设 \(S=\{i_1,i_2,\cdots,i_k\}\subseteq[n-1]\)。求 \(\alpha(S)\) 的显式公式。

   思路由第 2、3 题的规律推广：下降集 \(\subseteq S\) 的排列被 \(S\) 中的位置切成 \(k+1\) 个各自递增的段，段长依次为 \(i_1,\,i_2-i_1,\,\cdots,\,n-i_k\)。

   于是 \(\alpha(S)\) 为多项式系数 \[\alpha(S)=\binom{n}{i_1,\;i_2-i_1,\;\cdots,\;n-i_k}=\frac{n!}{i_1!\,(i_2-i_1)!\cdots(n-i_k)!}.\]

5. 有多少个 \(10\) 排列，其下降集恰好等于 \(\{3,7\}\)？

   思路“恰好等于”比“包含于”更严格：要求位置 \(3,7\) 确实是下降，而其它位置都是上升。用容斥（inclusion–exclusion）从 \(\alpha\) 得到精确计数。

   1. “下降集 \(\subseteq\{3,7\}\)”的有 \(\alpha(\{3,7\})\) 个；但其中包含了下降集为 \(\{3\}\)、\(\{7\}\)、\(\varnothing\) 的情形。
   2. 故 \(\beta(\{3,7\})=\alpha(\{3,7\})-\alpha(\{3\})-\alpha(\{7\})+\alpha(\varnothing)\)，其中 \(\alpha(\varnothing)=1\)。这正是第 6 题通式的特例。

6. 设 \(S=\{i_1,i_2,\cdots,i_k\}\subseteq[n-1]\)。记 \(\beta(S)\) 为下降集恰好等于 \(S\) 的 \(n\) 排列个数。求 \(\beta(S)\) 的公式（答案可含 \(\alpha\) 函数）。

   思路这是“恰好”与“至多（包含于）”之间的标准翻译，用容斥原理对子集求和： \[\beta(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\,\alpha(T).\] 反过来也有 \(\alpha(S)=\sum_{T\subseteq S}\beta(T)\)，二者互为子集反演（Möbius / 子集求和反演）。

7. 令 \[M(n,k)=\sum_{j=1}^{k}A(n,j),\] 即 \(M(n,k)\) 为至多有 \(k\) 个上升段的 \(n\) 排列个数。通过构造一个适当的满射（surjection），证明 \[M(n,k)\le k!\,S(n,k).\]

   思路不等式 \(|X|\le|Y|\) 可由“从 \(Y\) 到 \(X\) 的满射”得到（满射保证 \(|Y|\ge|X|\)）。这里 \(k!\,S(n,k)\) 数的是把 \([n]\) 分成 \(k\) 个有标号非空块（即满射 \([n]\to[k]\)）的方式。

   1. 左边 \(M(n,k)\)：把每个至多 \(k\) 段的排列看作把它的上升段“贴标签”后的对象。
   2. 构造从 \(k!\,S(n,k)\) 的对象到至多 \(k\) 段排列的满射：把每个有序分块按块内升序排列、按标签顺序拼接，得到一个上升段数 \(\le k\) 的排列；说明每个目标排列至少被取到一次即可。

8. 排列 \(p\) 的阶（order）是使 \(p^k=\mathrm{id}\) 的最小正整数 \(k\)。

   1. 证明：若 \(p\) 与 \(q\) 有相同的型（type），则它们的阶相同。
   2. 已知 \(p,q\) 的型，如何求出该阶？
   思路排列分解为不相交循环（cycle）。一个长度为 \(\ell\) 的循环，其 \(m\) 次幂回到恒等当且仅当 \(\ell\mid m\)。

   1. (a) 阶只依赖各循环长度（即型），与具体元素无关，故同型同阶。
   2. (b) 整个排列回到恒等 \(\iff\) 每个循环都回到恒等 \(\iff\) 所有循环长度都整除 \(k\)。最小这样的 \(k\) 即各循环长度的最小公倍数 \(\mathrm{lcm}\)。
   具体例型为 \(2+3\)（一个 2-循环、一个 3-循环）的排列，阶 \(=\mathrm{lcm}(2,3)=6\)。

9. 设 \(S\) 是行用非负整数标号的无穷矩阵，第 \(n\) 行由斯特林数 \(S(n,0),S(n,1),\cdots\) 组成。设 \(s\) 为同样定义的无穷矩阵，但把 \(S(n,k)\) 换成带符号第一类斯特林数 \(s(n,k)\)。求矩阵 \(S\) 与 \(s\) 满足的一个矩阵恒等式。

   思路第一类与第二类斯特林数在幂基与下降阶乘基（falling factorial）之间互为转换矩阵，二者互逆。

   结论：\(S\,s=s\,S=I\)（单位矩阵）。等价的标量形式为正交关系 \[\sum_{j}S(n,j)\,s(j,m)=\sum_{j}s(n,j)\,S(j,m)=\delta_{nm}.\]

10. 一架飞机有 \(n\) 个座位，本次航班全部售出。乘客逐一登机，前 \(n-1\) 位乘客随机就座（不一定坐自己的票位）。当最后一位乘客登机时，他走向自己的票位：若空着就坐下；若被占，就请占位者让开，那人再去自己的票位，照此进行，直到当前正在移动的人发现自己的票位空着，于是再无人被请走。设 \(k\in[n]\)。求（连同最后一位乘客在内）因最后一位乘客的到来而恰好有 \(k\) 人移动的概率。

    思路这是经典“占座问题”。移动序列构成一条链：最后乘客 → 占其位者 → … 直到某人发现自己座位空。链长由前 \(n-1\) 位乘客的随机就座（一个随机函数 / 排列结构）决定。

    1. 把前 \(n-1\) 人的就座看成等可能的安排，分析“链长恰为 \(k\)”需要的占位关系。
    2. 用条件计数：恰好 \(k\) 人移动对应于某种长度为 \(k\) 的链且第 \(k\) 个座位恰空。结果是一个与 \(n,k\) 有关的简洁概率（提示：可先算 \(n\) 小时的特例 \(n=2,3\) 找规律）。

11. 所有 \(n\) 排列的不动点（fixed point）平均个数是多少？

    思路用期望的线性性（指示变量法），无需枚举。

    1. 对位置 \(i\)，令 \(X_i=1\) 当 \(p(i)=i\) 否则 \(0\)。在随机 \(n\) 排列中 \(P(p(i)=i)=\frac{(n-1)!}{n!}=\frac1n\)。
    2. 不动点总数 \(=\sum_{i=1}^n X_i\)，期望 \(=\sum_{i=1}^n\frac1n=1\)。所以平均恰为 \(1\)（与 \(n\) 无关）。

12. 有多少个 \(6\) 排列，其四次幂是恒等排列？

    思路由第 8 题，\(p^4=\mathrm{id}\iff\) 每个循环长度都整除 \(4\)，即循环长度 \(\in\{1,2,4\}\)。

    1. 枚举 \(6\) 的、循环长度只用 \(1,2,4\) 的所有型：如 \(1^6,\ 1^4 2,\ 1^2 2^2,\ 2^3,\ 1^2 4,\ 2\,4\)。
    2. 对每种型用公式 \(\dfrac{n!}{\prod_j j^{m_j}\,m_j!}\) 数出排列数，再求和。

13. 有多少个 \(6\) 排列，其六次幂是恒等排列？

    思路\(p^6=\mathrm{id}\iff\) 各循环长度整除 \(6\)，即 \(\in\{1,2,3,6\}\)。

    1. 列出 \(6\) 的、只用 \(1,2,3,6\) 作部分的所有型（含 \(6\) 本身、\(3+3\)、\(3+2+1\) 等）。
    2. 逐型用同一公式 \(\dfrac{6!}{\prod_j j^{m_j}\,m_j!}\) 计数并相加。

14. 有多少个 \(12\) 排列，其立方恰好含两个 \(3\)-循环？

    思路关键事实：长 \(\ell\) 的循环取立方后会裂成 \(\gcd(\ell,3)\) 个长 \(\ell/\gcd(\ell,3)\) 的循环。先弄清哪种 \(\ell\) 才能在立方后产生 \(3\)-循环。

    1. 要使立方后出现长 \(3\) 的循环，需 \(\ell/\gcd(\ell,3)=3\)。若 \(3\nmid\ell\)（\(\gcd=1\)）则要 \(\ell=3\)，与 \(3\nmid\ell\) 矛盾；若 \(3\mid\ell\)（\(\gcd=3\)）则 \(\ell=9\)。故只有长 \(9\) 的循环才贡献 3-循环，且每个长 \(9\) 循环恰好裂成三个 3-循环。（对照：长 \(3\) 立方变三个不动点，长 \(6\) 变三个 2-循环，长 \(12\) 变三个 4-循环，都不出 3-循环。）
    2. 于是 \(p^3\) 中 3-循环的个数总是 \(3\) 的倍数（\(0,3,6,\dots\)），永远不可能恰好等于 \(2\)；在 \(n=12\) 内至多容纳一个长 \(9\) 循环（给出 3 个 3-循环）。结论：满足条件的排列不存在，答案为 \(0\)。这是一道“陷阱”题。

15. 有多少个偶 \(6\) 排列的阶为 \(4\)？（阶的定义见第 8 题。）

    思路阶为 \(4\iff\) 各循环长的 \(\mathrm{lcm}=4\)，即必须出现长 \(4\) 的循环、且其余循环长 \(\in\{1,2,4\}\)。在 \(n=6\) 内，含 4-循环的型为 \(4+1+1\) 与 \(4+2\)。

    1. 判奇偶（parity）：长 \(\ell\) 的循环符号为 \((-1)^{\ell-1}\)。\(4\)-循环是奇置换；\(2\)-循环也是奇置换。
    2. 型 \(4+1+1\)：符号 \(=(-1)^3=-1\)（奇），排除。型 \(4+2\)：符号 \(=(-1)^3(-1)^1=+1\)（偶），保留。
    3. 对 \(4+2\) 用公式 \(\dfrac{6!}{4\cdot 2}=\dfrac{720}{8}=90\)。即答案为 \(90\)。

16. 求“立方为恒等排列的 \(n\) 排列个数”的指数生成函数（EGF）的显式公式。

    思路\(p^3=\mathrm{id}\iff\) 循环长 \(\in\{1,3\}\)。用指数公式（exponential formula）：若每种连通结构的 EGF 为 \(C(x)\)，则集合结构的 EGF 为 \(e^{C(x)}\)。

    单个 1-循环 EGF 为 \(x\)，单个 3-循环 EGF 为 \(\dfrac{x^3}{3}\)（\(=\frac{(3-1)!}{3!}x^3\)）。故 \[\sum_{n\ge0}a_n\frac{x^n}{n!}=\exp\!\Big(x+\frac{x^3}{3}\Big).\]

17. 求“阶为 \(6\) 的 \(n\) 排列个数”的指数生成函数的显式公式。

    思路阶为 \(6\) 的排列：所有循环长 \(\in\{1,2,3,6\}\)（保证 lcm 整除 6），且 lcm 恰为 \(6\)。用容斥从“lcm 整除 6”里减去“lcm 整除 1,2,3”等情形。

    1. 对约数集 \(d\)，记 \(E_d(x)=\exp\big(\sum_{\ell\mid d}\frac{x^\ell}{\ell}\big)\) 为“循环长都整除 \(d\)”的 EGF（即 \(p^d=\mathrm{id}\)）。
    2. 阶恰为 \(6\) 的 EGF \(=E_6-E_3-E_2+E_1\)（对 \(6\) 的真约数 \(1,2,3\) 做容斥）。

18. 不使用生成函数解本题。

    1. 设 \(H(n)\) 为 \(n\) 排列的平均循环数。证明 \[H(n)=\frac{n-1}{n}H(n-1)+\frac1n\big(H(n-1)+1\big).\]
    2. 求 \(H(n)\) 的显式公式。
    思路用“最后一个元素 \(n\) 插入哪里”的递推：在随机 \((n-1)\) 排列上插入 \(n\)。元素 \(n\) 以概率 \(\frac1n\) 自成一个新循环（循环数 +1），以概率 \(\frac{n-1}{n}\) 插入已有循环（循环数不变）。

    1. (a) 把两种情形按概率加权即得递推式（化简后其实是 \(H(n)=H(n-1)+\frac1n\)）。
    2. (b) 逐项展开：\(H(n)=1+\frac12+\frac13+\cdots+\frac1n=H_n\)，即第 \(n\) 个调和数（harmonic number）。

19. 证明：若 \(n\ge1\)，则 \[n!=\sum_{k=0}^{n}\binom{n}{k}D(k),\] 其中 \(D(k)\) 为长 \(k\) 的错位排列数，并约定 \(D(0)=1\)。

    思路组合恒等式，按不动点集合分类。每个 \(n\) 排列都唯一对应：哪一组元素是不动点（选法 \(\binom nk\)，这里选的是被错位的元素个数），其余元素上是一个无不动点的排列（错位排列）。

    1. 固定恰有 \(n-k\) 个不动点：先选这 \(n-k\) 个不动点（\(\binom{n}{n-k}=\binom nk\) 种），剩下 \(k\) 个元素作错位排列（\(D(k)\) 种）。
    2. 对 \(k=0,\dots,n\) 求和恰好数遍所有 \(n!\) 个排列。

20. 用组合论证证明：对所有 \(n\ge2\)， \[D(n)=(n-1)\big(D(n-1)+D(n-2)\big).\]

    思路看元素 \(1\) 被送到哪。设 \(p(1)=j\)，\(j\) 有 \(n-1\) 种选择（\(j\ne1\)）。再按 \(p(j)\) 是否等于 \(1\) 分两种情况。

    1. 情形 A：\(p(j)=1\)（即 \(1,j\) 互换）。其余 \(n-2\) 个元素作错位排列：\(D(n-2)\) 种。
    2. 情形 B：\(p(j)\ne1\)。把“\(1\) 不能去 \(j\)”这一禁令转移给 \(j\)，可证此情形数恰为 \(D(n-1)\)。
    3. 两情形相加再乘以 \(j\) 的 \(n-1\) 种选择，得递推式。

21. (a) 求“长 \(n\) 且每个循环长都能被 \(k\) 整除”的排列数 \(f_k(n)\) 的指数生成函数。

    (b) 求 (a) 中所定义 \(f_k(n)\) 的公式。

    (c) 给出 (b) 结果的组合证明。

    思路循环长只允许 \(k,2k,3k,\dots\)。单个长 \(jk\) 循环的 EGF 项为 \(\frac{x^{jk}}{jk}\)。

    1. (a) 由指数公式：\(\sum_n f_k(n)\frac{x^n}{n!}=\exp\Big(\sum_{j\ge1}\frac{x^{jk}}{jk}\Big)=\exp\Big(\frac1k\sum_{j\ge1}\frac{(x^k)^j}{j}\Big)=(1-x^k)^{-1/k}.\)
    2. (b) 展开 \((1-x^k)^{-1/k}\) 取系数，得 \(f_k(n)\)（仅当 \(k\mid n\) 非零，形如连乘 \(\prod\)）。
    3. (c) 组合证明：用“按规则逐元素建立长可被 \(k\) 整除的循环”的计数过程，对应 (b) 的连乘结构。

22. 设 \(p\) 为素数。对哪些 \(k\in[p]\)，\(c(p,k)\) 能被 \(p\) 整除？

    思路\(c(p,k)\) 是无符号第一类斯特林数（长 \(p\) 且有 \(k\) 个循环的排列数），其生成多项式 \(\sum_k c(p,k)x^k=x(x+1)\cdots(x+p-1)\)。

    1. 在模 \(p\) 下，\(x(x+1)\cdots(x+p-1)\equiv x^p-x\pmod p\)（费马小定理 / 多项式因式）。
    2. 比较系数：除 \(x^p\) 与 \(x^1\) 项外，所有中间系数 \(c(p,k)\)（\(2\le k\le p-1\)）都 \(\equiv0\pmod p\)。故除 \(k=1\) 与 \(k=p\) 外都被 \(p\) 整除。

23. （威尔逊定理，Wilson's theorem）设 \(p\) 为素数。证明 \((p-1)!+1\) 能被 \(p\) 整除。

    思路承接第 22 题。在 \(x(x+1)\cdots(x+p-1)\equiv x^p-x\pmod p\) 中比较常数项之外的低次项，或直接用 \((x-1)(x-2)\cdots(x-(p-1))\equiv x^{p-1}-1\pmod p\)。

    1. 取 \(x=0\) 比较 \((x-1)\cdots(x-(p-1))\equiv x^{p-1}-1\)：左边常数项 \(=(-1)^{p-1}(p-1)!\)，右边 \(=-1\)。
    2. 对奇素数 \(p\)，\((-1)^{p-1}=1\)，得 \((p-1)!\equiv-1\pmod p\)，即 \(p\mid(p-1)!+1\)；\(p=2\) 直接验证。

24. 计算 \(b(10,3)\)。

    思路\(b(n,k)\) 是恰有 \(k\) 个逆序的 \(n\) 排列个数（马洪数，Mahonian）。它是 \([n]_q!=\prod_{i=1}^{n}\frac{1-q^i}{1-q}\) 中 \(q^k\) 的系数。注意它并不等于 \(k\) 的分拆数（例如 \(b(n,1)=n-1\) 随 \(n\) 增长），最稳妥的是用第 25 题的递推 \(b(n,k)=b(n,k-1)+b(n-1,k)\)（当 \(n-1\ge k\)）建表逐格推进。

    1. 由 \(b(n,0)=1\)、\(b(n,1)=n-1\) 起步：\(b(n,2)=b(n,1)+b(n-1,2)\) 得 \(b(10,2)=44\)；再用 \(b(n,3)=b(n,2)+b(n-1,3)\)。
    2. 逐格得 \(b(4,3)=6,\;b(5,3)=15,\;b(6,3)=29,\;b(7,3)=49,\;b(8,3)=76,\;b(9,3)=111\)，最终 \(b(10,3)=44+111=155\)。

25. 证明：若 \(n-1\ge k\)，则 \[b(n,k)=b(n,k-1)+b(n-1,k).\tag{4.19}\]

    思路看元素 \(n\)（最大值）在 \(n\) 排列中的位置：它放在末尾不产生新逆序，放在更靠前每左移一格多一个逆序。等价地，看把 \(n\) 插入 \((n-1)\) 排列时贡献的逆序数 \(0,1,\dots,n-1\)。

    1. 设 \(n\) 贡献的逆序为 \(j\)（\(0\le j\le n-1\)），余下是逆序数为 \(k-j\) 的 \((n-1)\) 排列，得 \(b(n,k)=\sum_{j=0}^{n-1}b(n-1,k-j)\)。
    2. 对相邻 \(k\) 做差并利用 \(n-1\ge k\)（边界项消失），即得 (4.19)。

26. 把上一题的递推关系修改到 \(n-1<k\) 的情形。

    思路当 \(n-1<k\) 时，第 25 题推导中“\(n\) 贡献逆序 \(\ge n\)”不可能，求和上界被截断，边界项不再为 \(0\)。

    修正后为 \(b(n,k)=b(n,k-1)+b(n-1,k)-b(n-1,k-n)\)，多减去越界项 \(b(n-1,k-n)\)。

27. 设 \(k\le n-1\)。

    1. 有多少个 \(n\) 排列，其逆序数 \(i(p)\) 能被 \(k\) 整除？
    2. 有多少个 \(n\) 排列，其逆序数 \(i(p)\equiv r\pmod k\)（对某固定 \(r\)）？
    思路用逆序的生成多项式 \([n]_q!=\prod_{i=1}^{n}(1+q+\cdots+q^{i-1})=\sum_k b(n,k)q^k\)，再用单位根滤子（roots of unity filter）取出指定同余类的系数和。

    1. 令 \(\omega=e^{2\pi i/k}\)。当 \(k\le n-1\) 时，\(\prod_{i=1}^n[i]_q\) 含因子 \([k]_q=1+q+\cdots+q^{k-1}\)，它在 \(q=\omega^t\)（\(t\not\equiv0\)）处为 \(0\)。
    2. 故 \(\sum_{i(p)\equiv0}1=\frac1k\sum_{t=0}^{k-1}[n]_{\omega^t}!=\frac1k\cdot n!\)（只有 \(t=0\) 项存活）。即 (a) 答案为 \(n!/k\)；(b) 同理对每个 \(r\) 也是 \(n!/k\)（均匀分布）。

28. 设 \(\mathrm{Inv}(n,k)\) 为恰有 \(k\) 个逆序的 \(n\) 排列之集合。令 \[a_i=\big|\{\,p=p_1p_2\cdots p_n\in\mathrm{Inv}(n,k)\;:\;p_i>p_{i+1}\,\}\big|.\] 证明 \(a_i\) 与 \(i\) 无关。

    思路要证“恰 \(k\) 个逆序的排列中，在位置 \(i\) 处下降的个数”不依赖 \(i\)。构造一一对应在不同位置间转移下降。

    1. 用第 28 题常用技巧：对在位置 \(i,i+1\) 的两个元素做局部对换或借助逆序数守恒的双射，把“在位置 \(i\) 下降”的排列映到“在位置 \(i'\) 下降”的排列且保持逆序总数 \(k\)。
    2. 双射存在即得 \(a_i=a_{i'}\)，故与 \(i\) 无关。

29. 设 \(k\le n\) 为固定正整数。设多重集 \(K\) 由 \(k\) 个 \(1\) 与 \(n-k\) 个 \(2\) 组成。设 \(p\) 为 \(K\) 的一个排列，定义 \(p\) 的一个逆序为“一个 \(2\) 排在一个 \(1\) 之前”所成的对。例如 \(221\) 有两个逆序，而 \(1212\) 有一个逆序。已知 \(K\) 共有 \(\binom nk\) 个排列，现按逆序数对它们计数：定义 \[\binom nk_{\!q}=\sum_p q^{\,i(p)},\] 其中 \(i(p)\) 为 \(p\) 的逆序数，求和取遍 \(K\) 的所有排列。多项式 \(\binom nk_q\) 称为高斯系数、\(q\)-二项式系数（q-binomial coefficient）或高斯多项式。

    1. 计算 \(\binom42_q\)、\(\binom51_q\)、\(\binom53_q\)。
    2. 证明 \(\binom nk_q=\binom{n}{n-k}_q\)。
    思路(a) 直接枚举 0/1 序列（这里用 1、2 标记）按逆序数统计。例如 \(\binom51_q\)：把唯一一个 \(1\) 放在 5 个位置，其右侧的 \(2\) 个数即逆序数，得 \(1+q+q^2+q^3+q^4\)。

    1. (a) \(\binom42_q=1+q+2q^2+q^3+q^4\)；\(\binom51_q=1+q+q^2+q^3+q^4\)；\(\binom53_q=\binom52_q\)（用对称性算）。
    2. (b) 把每个排列中的 \(1\)、\(2\) 互换（取补），逆序数 \(i(p)\) 变为 \(k(n-k)-i(p)\)？更直接：交换 \(1\leftrightarrow2\) 给出 \(K'\)（\(n-k\) 个 1）的排列双射，且按对称恰得 \(\binom{n}{n-k}_q\)。

30. 证明 \[\binom nk_q=q^{\,n-k}\binom{n-1}{k-1}_q+\binom{n-1}{k}_q.\tag{4.20}\]

    思路对 \(K\) 排列按最后一个符号分类（参见第 29 题的 1/2 模型）。

    1. 若最后一位是 \(1\)：它与前面所有 \(n-k\) 个 \(2\) 各成一个逆序，贡献因子 \(q^{n-k}\)，其余是 \(\binom{n-1}{k-1}_q\)。
    2. 若最后一位是 \(2\)：它在末尾不产生新逆序，其余是 \(\binom{n-1}{k}_q\)。两类相加得 (4.20)。

31. 按大小枚举其费雷尔斯图（Ferrers shape）能放入 \(m\times n\) 矩形内的整数分拆。即令 \[p(m,n,q)=\sum_{a}q^{\,|a|},\] 其中 \(a\) 取遍至多 \(m\) 行、至多 \(n\) 列的整数分拆，\(|a|\) 为 \(a\) 所分拆的整数。例如 \(p(2,2,q)=1+q+2q^2+q^3+q^4\)。证明 \(p(m,n,q)=\binom{m+n}{m}_q\)。

    思路把放入 \(m\times n\) 矩形的费雷尔斯图的边界路径（从左下到右上、由 \(m\) 步“上”和 \(n\) 步“下”组成）编码为一个 1/2 序列，对应第 29 题的多重集排列模型。

    1. 边界路径有 \(\binom{m+n}{m}\) 条，每条路径下方的方格数 \(=\) 对应分拆的大小 \(=\) 序列的逆序数。
    2. 于是 \(\sum_a q^{|a|}=\sum_{\text{路径}}q^{i}=\binom{m+n}{m}_q\)，正是 \(q\)-二项式系数。

32. 我们说一个排列回避模式 132（avoids the pattern 132），若其中不存在三个元素彼此的相对大小关系与 \(1,3,2\) 相同。即若 \(p=p_1p_2\cdots p_n\)，则 \(p\) 回避 132 当且仅当不存在三个下标 \(i<j<k\) 使 \(p_j>p_k>p_i\)。也就是说 \(p\) 中没有三个元素，使最左者最小、中间者最大（正如 132）。例如 \(42351\) 回避 132，而 \(35241\) 不回避（因三个元素 \(3,5,4\)），故称 \(35241\) 包含 132。证明：回避 132 的 \(n\) 排列个数等于第 \(n\) 个卡塔兰数。

    思路按最大元素 \(n\) 的位置递归分解，导出卡塔兰递推 \(C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}\)。

    1. 设 \(n\) 在位置 \(i+1\)。回避 132 要求 \(n\) 左边的元素都小于右边的元素（否则与 \(n\) 构成 132 型）。
    2. 于是左段是 \(\{1,\dots,i\}\) 的回避 132 排列（\(C_i\) 种），右段是其余的回避 132 排列（\(C_{n-1-i}\) 种），求和得卡塔兰递推；初值 \(C_0=1\)，故计数为 \(C_n\)。

33. 设 \(q\) 为任一长 \(k\) 的排列，仿照回避 132 的方式定义“回避 \(q\)”的排列（以 \(q\) 代替 132）。设 \(S_n(q)\) 为回避模式 \(q\) 的 \(n\) 排列个数。对哪些排列 \(q\)，上一题的结果能立即推出 \(S_n(q)=C_n\)？

    思路利用模式回避在对称变换下的不变性：逆（inverse）、反转（reverse）、互补（complement）这三种操作把回避 \(q\) 的排列双射到回避另一模式的排列，且数目不变。

    1. 对长 3 的模式，把 132 经过这些对称作用生成的轨道里的所有模式 \(q\)，都自动有 \(S_n(q)=C_n\)。
    2. 实际上所有 6 个长 3 模式都给出 \(C_n\)，但“立即由 132 结果推出”的是与 132 同一对称轨道的那些（如 \(231,312,213\) 等）。

34. 证明：若 \(n\) 排列 \(p=p_1p_2\cdots p_n\) 包含一个 312-模式，则它必含一个 312-模式，其中扮演 312 中“3”和“1”的两个元素在 \(p\) 中是相邻的元素。

    思路从任一个 312-出现入手，逐步把“3”和“1”收紧到相邻，用极小性 / 反证论证。

    1. 在所有 312-出现中，取使扮演“3”“1”的两元素位置间距最小的那一个。
    2. 若它们之间还有元素 \(x\)，按 \(x\) 与“3”“1”“2”的大小关系分类，总能找到一个间距更小的 312-出现，与极小性矛盾。故“3”“1”相邻。

35. 为例 3.37 的结果找一个非生成函数的证明。

    思路例 3.37 的结论原先用生成函数得到；本题要求改用组合 / 双射或递推的方法重证同一恒等式。先回到 3.37 看清结论的组合意义，再为左右两边各自给出直接计数或建立双射。

36. 正四面体（regular tetrahedron）是有四个顶点、六条棱、三个面（注：原文如此，实为四个面），且各棱等长的立体。见图 4.5。

    1. 求正四面体所有对称（symmetry）的个数。
    2. 求正四面体中那些可由一系列旋转得到的对称的个数。
    3. 正四面体的对称是其顶点集上的排列。这种排列的符号（或奇偶性 parity）能否告诉我们对应的对称是否可由一系列旋转得到？
    思路正四面体的对称群同构于 \(S_4\)（4 个顶点的全部排列）。

    1. (a) 全部对称数 \(=|S_4|=4!=24\)。
    2. (b) 仅旋转得到的为旋转子群，同构于交错群 \(A_4\)，有 \(12\) 个。
    3. (c) 旋转 \(=\) 偶置换：偶排列（符号 \(+1\)）对应可由旋转实现的对称，奇排列（含镜面反射）则不行。故符号能判别。

37. (+) 我们在第 4.5.1 节、以及补充习题 16 中，已经见过如何计算长 \(n\) 的所有排列中所有循环的总数。现在考虑该结论的如下推广……（原文 PDF 在此处截断，本题题面未完整给出；完整题面与解答请见对应“习题解答”一节。）

    思路承接 4.5.1 节“所有 \(n\) 排列中循环总数 \(=n!\cdot H_n\)”（\(H_n\) 为调和数）这一结果的推广方向。带 (+) 标记表示难度较高的进阶题，建议先掌握第 18 题（平均循环数）与 EGF 方法后再尝试。

返回 全书目录