问题及解答

设 $n$ 为正整数, 定义 $[n]_p$ 为

\[
[n]_p=n(n-1)(n-2)\cdots(n-p+1),
\]

这里 $p=0,1,2,\ldots,n$. 当 $p=0$ 时, 规定 $[n]_0=1$ (与规定 $0!=1$ 相似). 根据定义 $[n]_p$ 是 $n!$ 中前 $p$ 个因子相乘的结果. 因此有一些简单的性质:

(1)  $[n]_0=1$;
(2)  $[n]_n=n!$;
(3)  $[n]_p=\frac{n!}{(n-p)!}$;
(4)  $[n]_p=P_n^p$, 即 $n$ 元集的 $p$ 排列数. 由于 $C_n^p=\frac{P_n^p}{p!}$, 故 $[n]_p=p!C_n^p$;
(5)  $[n]_{p+1}=(n-p)[n]_p$.

我们可以列出前几项 $[n]_p$. 

\[
\begin{aligned}
[n]_1&=n,\\
[n]_2&=n(n-1)=n^2-n,\\
[n]_3&=n(n-1)(n-2)=n^3-3n^2+2n,\\
[n]_4&=n(n-1)(n-2)(n-3)=n^4-6n^3+11n^2-6n,\\
[n]_5&=n(n-1)(n-2)(n-3)(n-4)=n^5-10n^4+35n^3-50n^2+24n,
\end{aligned}
\]

可见 $[n]_p$ 展开后即是 $n$ 的 $p$ 次多项式. 或者可以被表示为 $\{n^i\mid i=1,2,\ldots,p\}$ 的线性组合.

一般的, 设

\[
\begin{split}
[n]_p&=s_1(p,p)n^p-s_1(p,p-1)n^{p-1}+s_1(p,p-2)n^{p-2}-\cdots+(-1)^{p-1}s_1(p,1)n^1+(-1)^p s_1(p,0)n^0\\
&=\sum_{i=0}^{p}(-1)^{i}s_1(p,p-i)n^{p-i}.
\end{split}
\]

这里的系数 $s_1(p,i)$ $(0\leqslant i\leqslant p)$ 称为第一类斯特林(Stirling)数.

易见,

• $s_1(p,0)=0$, $\forall p\geqslant 1$, 特别的, $s_1(0,0)=1$(因为 $[n]_0=1$);
• $s_1(p,p)=1$, $\forall p\geqslant 0$.

定理.  若 $1\leqslant i\leqslant p-1$, 则

\[
s_1(p,i)=(i-1)s_1(p-1,i)+s_1(p-1,i-1).
\]

例. 若令 $f_p(x)=x(x+1)(x+2)\cdots(x-p+1)$, $p=1,2,3,\ldots$. 约定 $f_0(x)=1$. 则

\[
\begin{aligned}
f_1(x)&=x,\\
f_2(x)&=x(x+1)=x^2+x,\\
f_3(x)&=x(x+1)(x+2)=x^3+3x^2+2x,\\
f_4(x)&=x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x,\\
f_5(x)&=x(x+1)(x+2)(x+3)(x+4)=x^5+10x^4+35x^3+50x^2+24x,
\end{aligned}
\]

容易看出 $f_p(x)$ 展开成 $x$ 多项式后, $x^i$ 的系数即为 $s_1(p,i)$. 即有

\[
f_p(x)=\sum_{i=0}^{p}s_1(p,p-i)x^{p-i}.
\]

参考文献

[1]  殷剑宏  编著 《组合数学》, 机械工业出版社.
[2]  陈景润  著  《组合数学》，哈尔滨工业大学出版社.