1. 缺项定位

在正式进入本节的内容前, 我要提到一类常用的简写. 设 $a$, $b$, $c$, $d$, $\dots$ 是若干个文字. 那么, $a=b=c$ 是 “$a=b$ 且 $b=c$” 的略. 同理, $a=b=c=d$ 是 “$a=b$ 且 $b=c$ 且 $c=d$” 的略. 类似地, 若 $x$, $y$, $z$ 是实数, 则 $x<y<z$ 是 “$x<y$ 且 $y<z$” 的略. 自然地, $x<y⩽z$ 是 “$x<y$ 且 $y⩽z$” 的略. 此类简写在本章随处可见.

我们先看一个简单的问题.

例 1.1. 考虑文字列 I: $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$. 我们去除第 $2$, $6$, $8$ 个文字 (也就是, 去除 $2$, $6$, $8$), 且不改变文字的前后次序, 得文字列 II: $1$, $3$, $4$, $5$, $7$, $9$, $10$. 试用公式表示文字列 II 的文字 $x$ 在文字列 II 的位置 $f(x)$ (比如, 文字 $7$ 的位置是 $5$).

此事自然不难. 分段地, 我们可写$$\begin{array}{r}f(x)=\{\begin{array}{ll}1,& x=1;\\ 2,& x=3;\\ 3,& x=4;\\ 4,& x=5;\\ 5,& x=7;\\ 6,& x=9;\\ 7,& x=10.\end{array}\end{array}$$不过, 分段或许是多的. 能否减少分段的数目? 这是可以的. 比如, 我们可写$$\begin{array}{r}f(x)=\{\begin{array}{ll}x,& x<2;\\ x-1,& 2<x<6;\\ x-2,& 6<x<8;\\ x-3,& 8<x.\end{array}\end{array}$$我认为这个写法是更好的, 因为它更体现本质: $x$ 前缺几项, 其位置就减几.

若我们想进一步地使公式简单, 那我们可作一个新记号. 设 $i$, $j$ 为二个整数. 定义$$\begin{array}{r}\rho (i,j)=\{\begin{array}{ll}0,& i<j;\\ 1,& i⩾j.\end{array}\end{array}$$注意, 对不相等的二个整数 $i$, $j$, $\rho (i,j)=0$ 相当于 $i<j$, 而 $\rho (i,j)=1$ 相当于 $i>j$. 利用这个 $\rho$-记号, 我们可方便地写出, 文字列 II 的文字 $x$ 在文字列 II 的位置$$\begin{array}{r}f(x)=x-(\rho (x,2)+\rho (x,6)+\rho (x,8)).\end{array}$$我们记 $m(x)=\rho (x,2)+\rho (x,6)+\rho (x,8)$. 不难看出, $x<2$ 时, $m(x)=0$; 此时, $x$ 前不缺项. $2<x<6$ 时, $m(x)=1$; 此时, $x$ 前缺 $1$ 项. $6<x<8$ 时, $m(x)=2$; 此时, $x$ 前缺 $2$ 项. $8<x$ 时, $m(x)=3$; 此时, $x$ 前缺 $3$ 项. 所以, 用 $\rho$-记号表示的 $f(x)$ 跟用分段表示的 $f(x)$ 是一样的.

还有一件事值得提. 因为数的加法适合结合律与交换律, 故我们可写$$\begin{array}{rl}f(x)=& x-(\rho (x,2)+\rho (x,6)+\rho (x,8))\\ =& x-(\rho (x,6)+\rho (x,8)+\rho (x,2))\\ =& x-(\rho (x,8)+\rho (x,2)+\rho (x,6))\\ =& x-(\rho (x,6)+\rho (x,2)+\rho (x,8))\\ =& x-(\rho (x,2)+\rho (x,8)+\rho (x,6))\\ =& x-(\rho (x,8)+\rho (x,6)+\rho (x,2)).\end{array}$$

为方便, 我再介绍一次 $\rho$-记号.

定义 1.2 ($\rho$-记号). 设 $i$, $j$ 为二个整数. 定义$$\begin{array}{r}\rho (i,j)=\{\begin{array}{ll}0,& i<j;\\ 1,& i⩾j.\end{array}\end{array}$$

不难看出, $i\ne j$ 时, $\rho (i,j)+\rho (j,i)=1$; 我们在后面会用到它. (当然, $i=j$ 时, $\rho (i,j)+\rho (j,i)=2$.)

一般地, 我们有

定理 1.3 (缺项定位). 设 $n$ 为高于 $1$ 的正整数. 设文字列 I: $1$, $2$, $\dots$, $n$. 设 $k$ 是低于 $n$ 的正整数. 设 $i_1$, $i_2$, $\dots$, $i_k$ 是不超过 $n$ 的, 且互不相同的正整数. 去除文字列 I 的第 $i_1$, $i_2$, $\dots$, $i_k$ 个文字 (也就是, 去除 $i_1$, $i_2$, $\dots$, $i_k$), 且不改变文字的前后次序, 得文字列 II. 那么, 文字列 II 的文字 $x$ 在文字列 II 的位置$$\begin{array}{r}f(x)=x-(\rho (x,i_1)+\cdots +\rho (x,i_k)).\end{array}$$

证. 我们先从小到大地排 $i_1$, $i_2$, $\dots$, $i_k$ 为 $i_1^{\prime }$, $i_2^{\prime }$, $\dots$, $i_k^{\prime }$.

为方便, 我们写 $i_0^{\prime }=0$, $i_{k+1}^{\prime }=n+1$. 注意, $i_0^{\prime }<1⩽i_1^{\prime }$, 且 $i_{k+1}^{\prime }>n⩾i_k^{\prime }$.

文字列 II 的文字恰为所有不等于 $i_1^{\prime }$, $i_2^{\prime }$, $\dots$, $i_k^{\prime }$ 的, 且不超过 $n$ 的正整数. 任取文字列 II 的一个文字 $x$. 那么, 存在不超过 $k$ 的非负整数 $v$, 使 $i_v^{\prime }<x<i_{v+1}^{\prime }$. 于是, $x$ 前缺了 $v$ 项. 不难验证$$\begin{array}{r}\rho (x,i_1^{\prime })+\cdots +\rho (x,i_k^{\prime })=v.\end{array}$$故 $x$ 在文字列 II 的位置$$\begin{array}{rl}f(x)=& x-v\\ =& x-(\rho (x,i_1^{\prime })+\cdots +\rho (x,i_k^{\prime }))\\ =& x-(\rho (x,i_1)+\cdots +\rho (x,i_k)).\end{array}$$我们用了加法的结合律与交换律.

证毕.