设 $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]  陈景润  著  《组合数学》，哈尔滨工业大学出版社.

设 $g(x)=(x+1)(x+2)(x+3)\cdots(x+n)$, $f(x)=g^2(x)$, 求 $f(x)$ 中 $x^{n+1}$ 的系数.

证明恒等式

\[
\dfrac{C_n^0}{2^n}+\dfrac{C_{n+1}^0}{2^{n+1}}+\dfrac{C_{n+2}^0}{2^{n+2}}+\cdots+\dfrac{C_{2n}^0}{2^{2n}}=1.
\]

(1)   $\sum_{k=1}^{n}kC_n^k=n 2^{n-1}$.

类似地, 可证明

(2)   $\sum_{k=2}^{n}C_n^k C_k^2=C_n^2  2^{n-2}$.

(3)   $\sum_{k=3}^{n}C_n^k C_k^3=C_n^3  2^{n-3}$.

由此可推出下面的恒等式

\[
\sum_{k=1}^{n}\binom{n}{k}k^3=2^{n-3}n^2(n+3).
\]

参见 (1 封私信) 这个组合数求和问题怎么解决？ - 知乎 (zhihu.com)

朗福德配对(Langford pair)问题

由 $2n$ 个数组成的集合 $\{1,1,2,2,3,3,\ldots,n,n\}$, 欲将其排成一列, 使两个数字 $k$ 之间恰有 $k$ 个数.

• 当 $n=3$时, 只有唯一的排列方式:  $231213$  (及其左右逆转).
• 当 $n=4$ 时, 也只有唯一的排列方式, 写出此排列.
• 当 $n=5$ 或 $6$ 时, 无解.

参考文献

[1]  Donald E. Knuth, 计算机程序设计艺术, 第4卷 第0册.

拉姆齐数(Ramsey number)

引例.  任意六个人组成一个小组, 小组中或者有三个人互不相识, 或者有三个人互相认识.

使用图的术语,  将六个人视为六个点. 两个人认识则用红边(或实线)相连; 不认识则用蓝边(或虚线)相连. 则总可以找到一个红边三角形或一个蓝边三角形.

图论中将顶点两两连接的图称为完全图, $p$ 个顶点的完全图记为 $K_p$. 于是上面的例子可以叙述为:

对于完全图 $K_6$ 的所有边进行着色, 必存在一个红边 $K_3$ 或一个蓝边 $K_3$.

此时我们记为 $K_6\rightarrow(K_3, K_3)$.

一般的, $K_p\rightarrow(K_m, K_n)$ 是指对于完全图 $K_p$ 的所有边着色(红色和蓝色), 存在红色完全子图 $K_m$ 或蓝色完全子图 $K_n$.  (这里 $2\leqslant m,n\leqslant p$.)

显然, 若 $K_p\rightarrow(K_m, K_n)$, 则对所有比 $p$ 大的正整数 $q$, 都有 $K_q\rightarrow(K_m, K_n)$.

定义.  给定正整数 $m,n$, 使得 $K_p\rightarrow(K_m, K_n)$ 成立的最小正整数 $p$ 被称为关于 $m,n$ 的拉姆齐数(Ramsey number) , 记作 $r(m,n)$.

注: 英国逻辑学家 Frank Ramsey 首先研究了这个问题, 并最终证明了 $r(m,n)$ 有上界. 因此这个数以他的名字命名.

例:  $r(3,3)=6$.

基本性质

Prop 1.  $r(m,n)=r(n,m)$

Pf.  通过交换两种颜色即证明.  事实上, 设 $p=r(m,n)$, 即 $K_p$ 所有边涂色后, 存在红色 $K_m$ 或蓝色 $K_n$. 若将 $K_p$ 中两种颜色对调, 则存在红色 $K_n$ 或蓝色 $K_m$. 由于 $p$ 使得 $K_p\rightarrow(K_m,K_n)$ 成立的最小正整数, 因此 $p$ 也是使得 $K_p\rightarrow(K_n,K_m)$ 成立的最小正整数. 因此 $r(n,m)=p$.

Prop 2.  $r(m,2)=m$,  $r(2,n)=n$.

Pf.  只需证明 $r(2,n)=n$. 首先 $r(2,n)\geqslant n$.  若将 $K_n$ 所有边涂为蓝色, 则包含 $K_n$; 若存在某条边是红色, 则包含 $K_2$. 证毕.

称 $r(m,2)$ 和 $r(2,n)$ 为平凡的 Ramsey 数.

参考文献

[1] 殷剑宏  编著 《组合数学》.

证明下面的组合数公式:

(1) 

\[C_n^r=\frac{n}{r}C_{n-1}^{r-1}\quad\text{或}\quad\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}\]

(2)

\[
C_n^r=\frac{n}{n-r}C_{n-1}^{r}\quad\text{或}\quad\binom{n}{r}=\frac{n}{n-r}\binom{n-1}{r}
\]

设数列 $\{a_n\}$ 满足递推关系 $a_{n+2}=6a_{n+1}-a_n$, $n\geqslant 0$. 初始值 $a_0=2$, $a_1=10$. 证明: $a_n$ 可以表示为两个自然数的平方和.

例如: $a_0=2=1^2+1^2$, $a_1=10=1^2+3^2$.

Calculator

功能: 算廿四

描述: 即使用 +,-,*,/,(,) 将四个数(一般指正整数, 并且传统上限制不超过10)组成一个算式, 使其结果为24.

函数: eq24(a,b,c,d)

返回: 所有能计算出24的算式

请问总共有多少种不同的算式?

注意, 这里要找的是本质上不同的算式,

比如 a-b+c 与 a-(b-c) 虽然形式上不同, 但本质上是同一个算式.

桌子上现有 3 枚黑棋子和 3 枚白棋子,  小洁要分若干次把它们取走. 她每次可以取一种颜色的若干枚棋子, 或者取两种颜色的相同个数的棋子.

那么她有多少种不同的方法将这些棋子取完. （相同颜色的棋子不作区分）

[Hint] 可以先考虑 2 枚黑棋子和 2 枚白棋子的情况, 此时有 22 种取法.

对于 $m$ 枚黑棋子和 $m$ 枚白棋子, 记取法数是 $f(m)$.

 尝试证明 $f(4)=1712$. 并思考能否用计算机计算这个问题.