多项式入门

基础方法

乘法公式

分配率：

\begin{aligned} (a+b)(c+d)&=ac+ad+bc+bd\\ (a+b)(a-b)&=a^2-b^2 \end{aligned}

和差方：

\begin{aligned} (a+b)^2&=a^2+2ab+b^2\\ (a-b)^2&=a^2-2ab+b^2\\ (a+b)^3&=a^3+3a^2b+3ab^2+b^3\\ (a-b)^3&=a^3-3a^2b+3ab^2-b^3\\ (a+b+c)^2&=a^2+b^2+c^2+2ab+2bc+2ac\\ \end{aligned}

二项式定理：

\begin{aligned} (x+y)^n&=\sum_{k=0}^n{n\choose k}x^ky^{n-k}\\ (x+1)^n&=\sum_{k=0}^n{n\choose k}x^k \end{aligned}

方和差：

\begin{aligned} a^3+b^3&=(a+b)(a^2-ab+b^2)\\ a^3-b^3&=(a-b)(a^2+ab+b^2)\\ a^2+b^2&=(a+b)^2-2ab\\ a^2+b^2&=(a-b)^2+2ab\\ a^3+b^3+c^3&=(a+b+c)(a^2+b^2+c^2-ab-bc-ac)\\ \end{aligned}

一般形式：

\begin{aligned} a^n-b^n&=(a-b)(a^{n-1}+a^{n-2}b+\dots+b^{n-1})\\ a^n+b^n&=(a+b)(a^{n-1}-a^{n-2}b+\dots+b^{n-1})&n=2k+1,k\in\mathbb Z \end{aligned}

次方和公式：

\sum_{i=1}^ni={n(n+1)\over2}

\sum_{i=1}^ni^2={n(n+1)(2n+1)\over6}

\sum_{i=1}^ni^3=\left[{n(n+1)\over2}\right]^2={n^2(n+1)^2\over4}

\sum_{i=1}^ni^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}

对于五次方及以上，公式较为复杂，一般不考察。

婆罗摩笈多-斐波那契恒等式：

\begin{aligned} (a^2+b^2)(c^2+d^2)&=(ac-bd)^2+(ad+bc)^2\\ &=(ac+bd)^2+(ad-bc)^2 \end{aligned}

这个恒等式指出，如果有两个数都能表示为两个平方数的和，则这两个数的积也可以表示为两个平方数的和。

计算技巧

共轭根式：

(\sqrt2\pm1)^2=3\pm2\sqrt2\\ (\sqrt3\pm1)^2=4\pm2\sqrt3

平方：

\begin{array}{lllll} &11^2=121&12^2=144&13^2=169&14^2=196\\ 15^2=225&16^2=256&17^2=289&18^2=324&19^2=361\\ &21^2=441&22^2=484&23^2=529&24^2=576\\ 25^2=625&26^2=676&27^2=729&28^2=784&29^2=841\\ &31^2=961&32^2=1024&33^2=1089&34^2=1156\\ 35^2=1225&36^2=1296&37^2=1369&38^2=1444&39^2=1521\\ &41^2=1681&42^2=1764&43^2=1849&44^2=1936\\ {\color{red}45^2=2025}&46^2=2116&47^2=2209&48^2=2304&49^2=2401\\ \end{array}

立方：

\begin{array}{lllll} &&\,\,\,2^3=8&\,\,\,3^3=27&\,\,\,4^3=64\\ \,\,\,5^3=125&\,\,\,6^3=216&\,\,\,7^3=343&\,\,\,8^3=512&\,\,\,9^3=729\\ 10^3=1000&11^3=1331&12^3=1728&13^3=2197&14^3=2744\\ 15^3=3375&16^3=4096&17^3=4913&18^3=5832&19^3=6859\\ 20^3=8000&21^3=9261&22^3=10648&23^3=12167&24^3=13824\\ 25^3=15625&26^3=17576&27^3=19683&28^3=21952&29^3=24389\\ 30^3=27000&31^3=29791&32^3=32768&33^3=35937&34^3=39304\\ 35^3=42875&36^3=46656&37^3=50653&38^3=54872&39^3=59319\\ 40^3=64000 \end{array}

幂：

\begin{array}{lllll} &2^{1}\,\,=2&2^{2}\,\,=4&2^{3}\,\,=8&2^{4}\,\,=16\\ 2^{5}\,\,=32&2^{6}\,\,=64&2^{7}\,\,=128&2^{8}\,\,=256&2^{9}\,\,=512\\ 2^{10}=1024&2^{11}=2048&2^{12}=4096&2^{13}=8192&2^{14}=16384\\ 2^{15}=32768&2^{16}=65536 \end{array}

\begin{array}{llllll} 3^{2}=9&3^{3}=27&3^{4}=81&3^{5}=243&3^{6}=729&3^{7}=2187\\ 5^{2}=25&5^{3}=125&5^{4}=625&5^{5}=3125&5^{6}=15625&5^{7}=78125 \end{array}

阶乘：

\begin{array}{llllll} 0!=1&1!=1&2!=2\\ 3!=6&4!=24&5!=120\\ 6!=720&7!=5040&8!=40320 \end{array}

因式分解

经典分离技巧：

(a+b+c)^2=a^2+b^2+c^2+2(ab+bc+ca)

(a+b)(a^2-ab+b^2)=a^3+b^3

(a-b)(a^2+ab+b^2)=a^3-b^3

x^3+\dfrac{1}{x^3}=\paren{x+\dfrac{1}{x}}\paren{x^2+\dfrac{1}{x^2}-1}

一般的，

a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\dots+b^{n-1})

a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+\dots\pm b^{n-1}),n\equiv1\pmod2

双十字相乘：

x^2+4y^2+4xy+6x+12y+9=(x+2y+3)^2

1. 分解 x^2,y^2,xy。

2. 将 x 或 y 分为两部分。

3. 检验。

因式定理：形如

f(x)=a_0+a_1x+\dots+a_nx^n

的称为多项式，若 f(a)=0，则 f(x) 一定可以分解成：

f(x)=(x-a)g(x)

其中 g(x) 是比 f(x) 低一次的多项式。

长除法​：根据因式定理，可以通过长除法来分解多项式。

如果已知多项式的一个或多个零点，因式定理可以帮助提取对应零点的因式，将多项式化简为更低次数的形式，从而简化求根过程。具体步骤如下：

• 先设法找到多项式 f 的一个零点 a。
• 用因式定理确认 (x-a) 是多项式 f(x) 的因式。
• 用长除法计算多项式 g(x)=\frac{f(x)}{x-a}。
• 在方程 f(x)=0 中，所有满足 x\neq a 的根，都是方程 g(x)=0 的根。
• 由于 g(x) 的多项式次数比 f(x) 低，因此求 g 的零点可能更简单。

等式与方程

韦达定理

对于二次方程

ax^2+bx+c=0

有根的判别式

\Delta=b^2-4ac

两根公式

x_{1,2}=\dfrac{-b\pm\sqrt{\Delta}}{2a}

有韦达定理

x_1+x_2=-\dfrac{b}{a}

x_1x_2=\dfrac{c}{a}

|x_1-x_2|=\dfrac{\sqrt\Delta}{|a|}

因此

x_1^2+x_2^2=(x_1+x_2)^2-2x_1x_2=\dfrac{b^2-2ac}{a^2}

|x_1^2-x_2^2|=|(x_1+x_2)(x_1-x_2)|=\dfrac{|b|\sqrt{b^2-4ac}}{a^2}

练习 五个人的顺序已确定，现插入两人，共有几种方案？

• 若两人相邻：捆绑后插空，C_6^1=6 种。
• 若两人不相邻：如上所述，240 种。

由于两种情况无交集，直接相加，总答案为 246 种。

隔板法

隔板法用于求将相同元素分组的方案数，也可以用于求线性不定方程的正整数解或非负整数解的组数。

情况一：正整数解

求方程：

\dfrac{1}{x_1}+\dfrac{1}{x_2}=\dfrac{x_1+x_2}{x_1x_2}=-\dfrac{b}{c}

\vert{\dfrac{1}{x_1}-\dfrac{1}{x_2}}=\dfrac{|x_1-x_2|}{|x_1x_2|}=\dfrac{\sqrt{b^2-4ac}}{|c|}

有二次函数根的分布：

• 方程有两个正根：

  \Delta > 0, x_1 + x_2 > 0, x_1x_2 > 0

• 方程有两个负根：

  \Delta > 0, x_1 + x_2 < 0, x_1x_2 > 0

• 方程有两个异号根：

  x_1x_2 < 0

• 方程有两个根均大于 m：

  \Delta > 0, x_1 + x_2 > 2m, (x_1 - m)(x_2 - m) > 0

• 方程有两个根均小于 m：

  \Delta > 0, x_1 + x_2 < 2m, (x_1 - m)(x_2 - m) > 0

• 方程有两个根在 m 两侧：

  (x_1 - m)(x_2 - m) < 0

• 方程有两个根在 (l, r) 之间：

  \Delta > 0, l < -\frac{b}{2a} < r, f(l)f(r) > 0

• 方程有两个根在 [l, r] 之间：

  \Delta > 0, l < -\frac{b}{2a} < r, a \cdot f(l) \ge 0, a \cdot f(r) \ge 0

• 方程有两个根，一个在 (l, r) 之间：

  \Delta > 0, f(l)f(r) < 0

• 方程有两个根，一个在 [l, r] 之间：

  \Delta > 0, f(l)f(r) < 0

  或

  \Delta > 0, f(l) = 0, \frac{l+r}{2} < -\frac{b}{2a}

  或

  \Delta > 0, f(r) = 0, -\frac{b}{2a} < \frac{l+r}{2}

非对称韦达定理：求出 x_1x_2 与 x_1+x_2 的比值，带入其中一个求解。

泰勒展开

14 世纪，马德哈瓦最早使用了泰勒级数以及相关的方法。尽管他的数学著作没有流传下来，但后来印度数学家的著作表明他发现了一些特殊的泰勒级数，这些级数包括正弦、余弦、正切、和反正切三角函数等等。之后，喀拉拉学派在他的基础上进行了一系列的延伸与合理逼近，这些工作一直持续到 16 世纪。到了 17 世纪，詹姆斯·格雷果里同样继续着这方面的研究并且发表了若干麦克劳林级数。但是直到 1715 年，布鲁克·泰勒提出了一个通用的方法来构建适用于所有函数的此类列级数。这就是后来被人们所熟知的泰勒级数。麦克劳林级数是泰勒级数的特例，是爱丁堡大学的科林·麦克劳林教授在 18 世纪发表的，并以其名字命名。

设 n 是一个正整数，如果定义在一个包含 a 的区间上的函数在 a 点 n+1 次可导，那么对于这个区间上的任意 x 都有：

f(x)=f(a)+\dfrac{f'(a)}{1!}(x-a)+\dfrac{f''(a)}{2!}(x-a)^2+\dots+\dfrac{f^{(n)}(a)}{n!}(x-a)^n+R_n(x)

其中的多项式称为函数在 a 处的泰勒展开式，剩余的 R_n(x) 是泰勒展开式，是 (x-a)^n 的高阶无穷小 \mathrm{o}[(x-a)^n]。

e^x=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\dfrac{x^4}{4!}+\dots+\dfrac{x^n}{n!}

\ln(x+1)=x-\dfrac{x^2}{2}+\dfrac{x^3}{3}-\dfrac{x^4}{4}+\dfrac{x^5}{5}+\dots+(-1)^{n+1}\dfrac{x^n}{n}

\sin x=x-\dfrac{x^3}{3!}+\dfrac{x^5}{5!}-\dfrac{x^7}{7!}+\dots+(-1)^n\dfrac{x^{2n+1}}{(2n+1)!}

\cos x=1-\dfrac{x^2}{2!}+\dfrac{x^4}{4!}-\dfrac{x^6}{6!}+\dots+(-1)^n\dfrac{x^{2n}}{(2n)!}

根据这些可以得到一些经典的不等式：

\boxed{e^x\ge\dfrac{1}{2}x^2+x+1},x\ge0

\boxed{e^x\ge x^2+1>x^2},x\ge0

\boxed{\ln x\le\dfrac{x}{e}},x>0

\boxed{\ln x\le x^2-x},x>0

多项式插值

插值是一种通过已知的、离散的数据点推算一定范围内的新数据点的方法，分为线性插值和多项式插值。多项式插值的一般形式如下：对已知的 n+1 的点 (x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)，求 n 阶多项式 f(x) 满足：

f(x_i)=y_i,\forall i=0,1,\dots,n

形式化来说，就是给定 n+1 个横坐标互不相同的点，求一个不超过 n 次的多项式 f(x)，使其过这 n+1 个点。

最简单的插值法就是拉格朗日插值法：尝试构造多项式 f_i(x) 使得 f_i(x)=[i=x_i]，易得：

f_i(x)=\prod_{j\neq i}{x-x_j\over x_i-x_j}

可得拉格朗日插值的形式为：

f(x)=\sum_{i=1}^ny_i\cdot f_i(x)

化简为：

f(x)=\sum_{i=0}^ny_i\prod_{j\neq i}{x-x_j\over x_i-x_j}

置换和排列

置换和排列是各类问题中都很常见的概念。本文中如果不加说明，总是讨论有限的集合。

一个集合 X 到自身的双射（即一一对应）\sigma 称为 X 的一个置换（permutation）。如果集合 X 上还具有全序关系，则它的一个置换也常称作一个**（全）排列**。这个全序关系称为集合上的自然顺序。

「置换」与「排列」：在中文语境下，「置换」通常指改变元素顺序，而「排列」通常指将元素排成一列。当元素之间存在自然的顺序时，这两个概念是一回事：「排列」可以看作「置换」的结果；而相较于元素的自然顺序，「排列」中元素的顺序就指定了「置换」。因为本文使用「排列」一词时，总假定集合上存在自然顺序，故而本文中不会特意区分这两个概念。当然，没有自然顺序的元素也可以进行「排列」。这种「排列」常常出现在组合计数问题中。这超出了本文讨论的范畴。

设集合 X 的大小是 n，那么，X 上的全体置换的数目就是 n!。特别地，0!=1，即空集合上有且只有一个置换，也就是空置换。

置换讨论的是元素间的对应关系，而并不关心元素具体是什么。因而，当讨论大小为 n 的集合时，通常假定讨论的集合就是 \{1,2,\cdots,n\}；当集合上需要自然顺序的时候，通常假定使用自然数上的自然顺序。

表示方法

置换有多种表示方法。这里，以如下置换为例，讨论不同的置换表示方法。

\sigma(1) = 2,\ \sigma(2) = 6,\ \sigma(3) = 5,\ \sigma(4) = 4,\ \sigma(5) = 3,\ \sigma(6) = 1.

双行记号：集合 X=\{x_1,x_2,\cdots,x_n\} 上的置换可以表示为

\sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n} \end{pmatrix}.

它表示置换 \sigma 将元素 x_i 映射到 x_{p_i}。这里，当然需要 X=\{x_{p_1},x_{p_2},\cdots,x_{p_n}\}。置换的双行记号表示中，首行的元素出现顺序并不重要，重要的是两行之间的对应关系。

比如说，前文的例子可以按照双行记号写作

\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 6 & 5 & 4 & 3 & 1 \end{pmatrix},

当然，也可以写作

\sigma= \begin{pmatrix} 6 & 5 & 4 & 3 & 2 & 1 \\ 1 & 3 & 4 & 5 & 6 & 2 \end{pmatrix}.

单行记号：很多时候，集合 X 上有自然顺序。如果在双行记号中默认首行按照自然的顺序书写，并省略首行，那么，置换可以表示为

\sigma=\sigma(1)\sigma(2)\cdots\sigma(n).

这更像自然语言中排列的概念。所以，有时候排列会用来称呼这个有序组。

前文的例子利用单行记号可以写作

\sigma=265431.

这种单行的记号，常用来比较不同排列的大小。

轮换表示：置换还有一种更为紧凑的表达方式，称为置换的轮换表示。它将置换表示为一系列不相交的轮换的乘积。下面描述将给定置换写成轮换表示的步骤。

给定一个置换 \sigma，可以通过如下步骤写成轮换表示：

1. 如果 X 中还有未曾写下的元素，就写下一个左括号，并写下任意一个这样的元素；
2. 当前一个写下的元素是 x 时，
   • 如果 \sigma(x) 已经在前面写下过，就写上右括号，并返回步骤 1；
   • 如果 \sigma(x) 还没有写下过，就写下 \sigma(x)，并继续步骤 2；
3. 直到 X 的所有元素都已经写下，结束。

每一对括号中，都是一个轮换。括号中的元素个数，称为对应轮换的长度。实践中，常常省略掉长度为一的轮换。

前文的例子利用轮换表示可以写作

\sigma=(126)(35)(4)=(126)(35).

恒等变换中所有的轮换长度都是一，常常记作 (1) 而不是全部省略。

复合和逆置换

置换的复合就是映射的复合。置换的复合也常常称作置换的乘法。给定两个置换

\sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n}\end{pmatrix},\ \pi=\begin{pmatrix}x_{p_1}&x_{p_2}&\cdots&x_{p_n}\\ x_{q_1}&x_{q_2}&\cdots&x_{q_n}\end{pmatrix},

那么，它们的乘积 \pi\circ\sigma 的值为

\pi\circ\sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{q_1}&x_{q_2}&\cdots&x_{q_n}\end{pmatrix}.

简单来说就是先经过 \sigma 的映射，再经过 \pi 的映射。注意在上面的双行记号中，内层映射 \sigma 的第二行的顺序和外层映射 \pi 的第一行的顺序一致。因为置换 \sigma 和 \pi 本质是两个映射，所以 (\pi\circ\sigma)(x)=\pi(\sigma(x))。置换的复合的运算顺序是自右向左的。置换的乘法并不满足交换律，所以使用错误的顺序计算可能会导致错误的结果。连续多个置换的乘积称作排列的幂。

因为置换是双射，所以置换总有相应的逆置换。给定置换

\sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n}\end{pmatrix},

它的逆置换就是

\sigma^{-1}=\begin{pmatrix}x_{p_1}&x_{p_2}&\cdots&x_{p_n}\\x_1&x_2&\cdots&x_n\end{pmatrix}.

在轮换表示中，只要对每个轮换取逆，就能得到原来的置换的逆；而对每个轮换取逆，只要把元素的书写顺序倒过来就可以了。比如说，上文中的例子 \sigma 的逆置换的轮换表示是

\sigma^{-1} = (621)(53) = (162)(35).

给定 1\sim n 的一个排列和它的每个元素的排名的序列，就互为逆排列。

轮换（cycle）本身是特殊的置换。轮换的特性是，从轮换中的任何一点 x 出发，都能通过反复应用置换 \sigma 的方式得到轮换中的另一点 y。长度为 k 的轮换也称作 k‑轮换（k-cycle）。反复应用 k‑轮换 k 次，将得到恒等变换，即每个元素都回到了最开始的位置。置换的轮换表示可以看作将置换写成这些特殊置换（即轮换）的乘积，因而置换的轮换表示也可以看作是置换的轮换分解（cycle decomposition）。对于每个置换，它分解成轮换乘积的方式在不计顺序后都是唯一的。轮换可以看作是构成置换的基本单元。置换的轮换分解有着清晰的几何意义。如果将集合 S 上的置换中的每个有序对 (x,\sigma(x)) 都看成以 S 为顶点的有向图的边，那么这些轮换就是这个图上面的环路。如果置换 \sigma 能够分解为 m 个轮换，就意味着对应的有向图中共计有 m 个环路（包括自环）。这些环路自然互不相交。

1‑轮换就是置换的不动点（fixed point）。对于集合 X 上的置换 \sigma，通常用 X^\sigma 表示 \sigma 的不动点集合，即 X^\sigma=\{x\in X:\sigma(x)=x\}。

2‑轮换也称作对换（transposition）。也就是说，对换就是只交换了一对元素位置的置换。它的轮换表示是 (x_ix_j)，表示它交换了 x_i 和 x_j 的位置。任何置换都可以写作一系列对换的乘积。这相当于说，任何顺序的排列都可以通过一系列交换两个元素的操作恢复成指定的正序排列。这正是基于交换的排序算法在做的事情。更进一步，冒泡排序算法的正确性其实说明，任何置换都可以写作一系列相邻对换的乘积。这里的相邻对换（adjacent transposition）指的是只交换相邻元素的对换。

置换的性质

在应用中，常常需要关注单个置换的性质。

奇偶性：将轮换分解成对换的方式并不是唯一的。比如，

(123)=(13)(12)=(12)(23)=(12)(13)(12)(13).

但是，置换分解成一系列对换时，需要的对换的数目的奇偶性是固定的。一个置换的对换分解的数目的奇偶性也称作置换的奇偶性（parity）。

能够分解成偶数个对换的乘积的置换叫做偶置换，能够分解成奇数个对换的乘积的置换叫做奇置换。当 n\ge2 时，大小为 n 的奇置换和偶置换的数目相同。

符号：根据置换的奇偶性，还可以定义置换的符号（sign），记作 \operatorname{sgn}\sigma。偶置换的符号定义为 +1，奇置换的符号定义为 -1。

置换的乘积的符号，等于它们的符号的乘积，即

\operatorname{sgn}(\pi\circ\sigma)=\operatorname{sgn} \pi\cdot\operatorname{sgn}\sigma.

也就是说，两个奇偶性相同的置换的复合是偶置换，两个奇偶性不同的置换的复合是奇置换。这一结论，从对换分解的角度看是显然的。

特别地，单次对换必然改变置换的奇偶性。这也正解释了为什么虽然分解成对换的方式不唯一，但是所需的对换的数目的奇偶性是确定的。

置换的符号出现在行列式的 Leibniz 展开中。

置换的阶：置换的阶（order）是指满足如下条件的最小正整数 a：重复该置换 a 次后，所有元素都回到了原位。即

\operatorname{ord}\sigma=\min\{a\in\mathbf N_+:\sigma^a=(1)\}.

有限集合上，所有置换的阶都是有限的。这意味着，从起始顺序出发，只要重复按照固定模式打乱给定序列，在有限时间内，总可以将排列恢复原样。

置换的型：将 n 个元素的置换做轮换分解，置换的型（cycle type）就是分解中轮换长度的可重集合。这些轮换的长度构成了一个置换长度 n 的整数分划。如果得到的分解中长度为 k 的轮换共计 \alpha_k 个，那么置换的型常记作

1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n},

且这些系数满足 \sum_{k=1}^nk\alpha_k=n。

给定置换的型，不同的置换的数目为

\frac{n!}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}.

这是因为，给定任何 1\sim n 的排列，都可以按照置换的型分割成相应的轮换分解。但是，长度相同的轮换之间的顺序并不影响置换，所以总数需要除以 \prod_k\alpha_k!。另外，同一轮换内部实际是圆排列，起点的选取也不影响置换，所以需要除以 \prod_kk^{\alpha_k}。这就得到上式。

如果仅仅给定置换分解成的轮换个数 c(\sigma)，则不同的置换的数目为第一类斯特林数 \begin{bmatrix}n\\ k\end{bmatrix}。不同的型的个数为置换长度 n 的分拆数 p_n。

从置换的型，可以方便地确定置换的阶和奇偶性等性质。

因为 k‑轮换的阶是 k，不同的轮换又互不相交，所以置换 \sigma 的阶就是

\operatorname{lcm}\{k:\alpha_k>0\}.

同样地，因为 k‑轮换的奇偶性与 k 的奇偶性相反，所以置换 \sigma 的奇偶性就是

\sum_k(k-1)\alpha_k=\sum_{k}k\alpha_k-\sum_{k}\alpha_k=n-c(\sigma)

的奇偶性。这里，c(\sigma) 是轮换的个数（包括 1‑轮换，即不动点）。

置换的型在 Pólya 计数中有重要作用。

排列相关

如果集合 X 本身具有自然顺序，此时置换 \sigma 常称作排列，并用单行记号

\sigma(1)\sigma(2)\cdots\sigma(n)

表示。注意不要同轮换混淆。

逆序数：在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个逆序（inversion）或反序。这里的比较是在自然顺序下进行的。

在一个排列里出现的逆序的总个数，叫做这个置换的逆序数。排列的逆序数是它恢复成正序序列所需要做相邻对换的最少次数。因而，排列的逆序数的奇偶性和相应的置换的奇偶性一致。这可以作为置换的奇偶性的等价定义。

排名：将 n 个元素的排列按照字典序从小到大列举出来，则某一排列在这个序列中的位次就是该排列的排名。它建立了排列和正整数之间的一一对应，常常用于排列相关问题的状态压缩。

在中文竞赛圈，这个排名常称作排列的「康托展开」，但这种名称并不规范。更为严谨的说法是，一个排列的排名的康托展开（Cantor expansion），对应着该排列的 Lehmer 码（Lehmer code）。

正如名字所暗示的那样，康托展开是指一种将自然数展开为数列的方法。它可以看作是一种特殊的进制，也叫做阶乘进制。这种进制中，不同的数位对应的底数（radix）并不相同。比如，十进制数 463_{10} 可以在阶乘进制中表示为

463_{10}=341010_{!}.

它表示如下含义

463=3\times 5!+4\times 4!+1\times 3!+0\times 2!+1\times 1!+0\times 0!.

康托对于这类混合底数的进制进行了研究，故而自然数在这种进制下的数码表示也常称作自然数的康托展开。

不熟悉排名的计算方法的读者，可以通过这个简单的例子理解下面的算法的基本思路。

要计算排列 \sigma=452631 的排名，就是要计算有多少排列的字典序小于 \sigma，再加一。

• 第 1 位的选取要小于 \sigma，只能取自 \{1,2,3\}，后面 5 位可以任意选取，共 3\times 5! 个可选的排列；
• 如果第 1 位也选择 4，那么第 2 位的选取要小于 \sigma，只能取自 \{1,2,3\}（这里，4 已经选过了），后面的 4 位可以任意选取，共 3\times 4! 个可选的排列；
• 类似地，前 2 位的选取和 \sigma 相同时，第 3 位的选取要小于 \sigma，只能取自 \{1\}，后面的 3 位可以任意选取，共 1\times 3! 个可选的排列；
• 前 3 位的选取和 \sigma 相同时，第 4 位的选取要小于 \sigma，只能取自 \{1,3\}，后面的 2 位可以任意选取，共 2\times 2! 个可选的排列；
• 前 4 位的选取和 \sigma 相同时，第 5 位的选取要小于 \sigma，只能取自 \{1\}，后面的 1 位可以任意选取，共 1\times 1! 个可选的排列；
• 前 5 位的选取和 \sigma 相同时，第 6 位的选择无法得到比 \sigma 更小的排列，所以共 0\times 0! 个可选的排列。

因此，排列 \sigma 的排名为

1+3\times 5!+3\times 4!+1\times 3!+2\times 2!+1\times 1!+0\times 0!=444.

对于不同的排列，关键的点在于确定阶乘前面的系数。实际上，这些系数正是排在该位置之后却小于该位置元素的元素数目。

从例子中可以知道，求解给定排列的排名的算法，可以分为两步：

1. 将给定的长度为 n 的排列转化为它的 Lehmer 码，即长度为 n 的序列 L_\sigma，其中，第 i 位是

   L_\sigma(i)=\#\{j>i:\sigma(j)<\sigma(i)\},

   也就是在排列中，排在第 i 位后面，但是却比 \sigma(i) 小的元素个数。它等于尚未使用的元素中给定元素的排名（减一）。

2. 将 Lehmar 码看作是自然数的康托展开，求出原来的自然数，并加一。也就是说，最终的排名等于

   \operatorname{rank}\sigma=1+L_\sigma(1)(n-1)!+L_\sigma(2)(n-2)!+\cdots+L_\sigma(n)0!.

要求解这一问题的逆问题，即给定排名求解相应的排列，只要将上述过程反过来操作即可。在这一过程中求得的 Lehmer 码中的数字之和，就是排列的逆序数。

生成函数

序列 a （有穷无穷均可）的普通生成函数定义为形式幂级数：\displaystyle F(x)=\sum_na_nx^n。例如：

1. a=\lang1,2,3\rang 的普通生成函数是 1+2x+3x^2
2. a=\lang1,1,1,\dots\rang 的普通生成函数是 \displaystyle\sum_{n\geq 0}x^n
3. a=\lang1,2,4,8,16,\dots\rang 的生成函数是 \displaystyle\sum_{n\geq 0}2^nx^n
4. a=\lang1,3,5,7,9\rang 的生成函数是 \displaystyle\sum_{n\geq 0}(2n+1)x^n

换句话说，如果序列 a 有通项公式，那么它的普通生成函数的系数就是通项公式。

基本运算

两个序列 a,b 的生成函数 F(x),G(x)，则 F(x)\pm G(x) 是序列 \lang a_n\pm b_n\rang 的生成函数。

F(x)\pm G(x)=\sum_{n}(a_n\pm b_n)x^n

乘法运算即卷积，推出 F(x)G(x) 是序列 \left\lang\displaystyle\sum_{i=0}^na_ib_{n-i}\right\rang 的生成函数。

F(x)G(x)=\sum_nx^n\sum_{i=0}^na_ib_{n-i}

形式幂级数形式 \to 封闭形式

例如 a=\lang1,1,1,\dots\rang 的普通生成函数是 \displaystyle F(x)=\sum_{n\geq 0}x^n，可以发现 F(x)x+1=F(x)，于是解方程得到 \displaystyle F(x)=\frac{1}{1-x}，这就是 \displaystyle\sum_{n\geq 0}x^n 的封闭形式。

又例如等比数列 \lang1,p,p^2,\dots\rang 的生成函数 F(x)=\displaystyle\sum_{n\geq 0}p^nx^n，有 F(x)px+1=F(x) 得 F(x)=\displaystyle\frac{1}{1-px}.

a=\lang 1,0,1,0,1,\dots\rang 的 F(x)=\displaystyle\sum_{n\geq 0}x^{2n}=\frac{1}{1-x^2}

a=\lang 1,2,3,4,\dots\rang 的 F(x)=\displaystyle\sum_{n\geq 0}(n+1)x^n=\sum_{n\geq 0}(x^n)'=\left(\frac{1}{1-x}\right)'=\frac{1}{(1-x)^2}

a_n=\begin{pmatrix}m\\n\end{pmatrix} 的 F(x)=\displaystyle\sum_{n\geq 0}\begin{pmatrix}m\\n\end{pmatrix}x^n=(1+x)^m

Fib 数列定义为 a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}，于是有

F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0\implies F(x)=\frac{x}{1-x-x^2}

应用

1. 在许多不同种类的食物中选出 n 个，计算方案数。每种食物的限制如下：

构造生成函数：

全部乘起来得到答案的生成函数：

F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)}=\frac{x}{(1-x)^4}=\sum_{n\geq 1}\begin{pmatrix}n+2\\n-1\end{pmatrix}x^n

于是答案 =\begin{pmatrix}n+2\\n-1\end{pmatrix}=\begin{pmatrix}n+2\\3\end{pmatrix}

1. a_{n+1}+a_n=2^n,a_0=0，求通项。

f(x)=\displaystyle\sum_{n=0}^{+\infty}a_nx^n，原式变为 x^{-1}(a_{n+1}x^{n+1})+a_nx^n=(2x)^n，再求和有

\displaystyle\sum_{n=0}^{+\infty}x^{-1}(a_{n+1}x^{n+1})+\sum_{n=0}^{+\infty}(a_nx^n)=\sum_{n=0}^{+\infty}(2x)^n=\frac{1}{1-2x}\implies (\frac{1}{x}+1)f(x)=\frac{1}{1-2x}

f(x)=\frac{x}{(1-2x)(1+x)}=\frac{1}{3}(\frac{1}{1-2x}-\frac{1}{1+x})=\frac{1}{3}\sum_{n=0}^{+\infty}[2^n-(-1)^n]x^n

于是 \displaystyle a_n=\frac{1}{3}[2^n-(-1)^n].

1. 卡特兰数：一个 n\times n 的方阵从 (0,0) 走到 (n,n)，不经过对角线的方案数，记作 C_n。

有如下关系：C_n=\displaystyle\sum_{k=0}^nC_{n-k}C_k，构造 f(x)=\displaystyle\sum_{n=0}^{+\infty}C_nx^n，有

f^2(x)=C_0^2+(C_0C_1+C_1C_0)x+\dots\implies xf^2(x)+C_0=f(x)\implies f(x)=\frac{1-\sqrt{1-4x} }{2x}

\implies f(x)=\frac{1-\left\{1+\displaystyle\sum_{k=1}^{+\infty}\left[-2\begin{pmatrix}2k-2\\ k-1\end{pmatrix}\right]x^k\right\}}{2x}=\sum_{k=0}^{+\infty}\frac{\begin{pmatrix}2k\\k\end{pmatrix}x^k}{k+1}\implies\red{\boxed{C_n=\frac{\begin{pmatrix}2n\\n\end{pmatrix}}{n+1}}}

上升幂与普通幂的相互转化

我们记上升阶乘幂 x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)。

则可以利用下面的恒等式将上升幂转化为普通幂：

x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k

如果将普通幂转化为上升幂，则有下面的恒等式：

x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}}

下降幂与普通幂的相互转化

我们记下降阶乘幂 x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)。

则可以利用下面的恒等式将普通幂转化为下降幂：

x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}

如果将下降幂转化为普通幂，则有下面的恒等式：

x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k

多项式下降阶乘幂表示与多项式点值表示的关系

在这里，多项式的下降阶乘幂表示就是用

f(x)=\sum\limits_{i=0}^nb_i{x^{\underline{i}}}

的形式表示一个多项式，而点值表示就是用 n+1 个点

(i,a_i),i=0..n

来表示一个多项式。

显然，下降阶乘幂 b 和点值 a 间满足这样的关系：

a_k=\sum\limits_{i=0}^{n}b_ik^{\underline{i}}

即

\begin{aligned} a_k&=\sum\limits_{i=0}^{n}\dfrac{b_ik!}{(k-i)!}\\\dfrac{a_k}{k!}&=\sum\limits_{i=0}^kb_i\dfrac{1}{(k-i)!} \end{aligned}

这是一个卷积形式的式子，我们可以在 O(n\log n) 的时间复杂度内完成点值和下降阶乘幂的互相转化。