朗福德配对(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$. 并思考能否用计算机计算这个问题.

从 1,2,3,...,11 这十一个数中开出 5 个号码作为中奖号码.

任选 7 个号码, 猜中开奖的全部 5 个号码. 求中奖的概率多大?

分析:

如果每注只能任选 5 个号码, 那么显然中奖概率为 $1/C_{11}^{5}=1/462$.

现在每注是选 7 个号码, 因此有 $C_{11}^{7}=C_{11}^{4}=330$ 种可能.

购买一注, 也就是 7 个号码, 它包含了 $C_7^2=21$ 种 5 个号码的可能, 中奖概率为 $\frac{21}{462}=\frac{1}{22}$.

反过来思考, 比如开奖号码是 1,2,3,4,5.  那么可以中奖的集合为

\[
A=\bigl\{(1,2,3,4,5,x,y)\mid x,y\in\{6,7,8,9,10,11\}\bigr\}.
\]

因此 $\# A=C_6^2=15$, 即 330 种可能中只有 15 个能中奖, 中奖概率为 $\frac{15}{330}=\frac{1}{22}$.

如果选 $k$ 个号码, 那么中奖概率为

\[
p(k)=\frac{C_{6}^{k-5}}{C_{11}^{k}}.
\]

比如

\[
p(7)=\frac{1}{22},\quad p(8)=\frac{4}{33},\quad p(9)=\frac{3}{11},\quad p(10)=\frac{6}{11},\quad p(11)=1.
\]

总结:

中奖概率非常小. 

类似的可以考虑 双色球的中奖概率.

正 $n$ 边形中由其顶点可构成多少个三角形?

如果要求所构成的三角形中, 没有哪条边属于此正 $n$ 边形的边, 问这样的三角形有多少个?

在由 $n$ 个字符组成的字母表中, 问长度小于等于 $n$ 的单词总数最多有多少?

也称 rucksack problem.