北京师范大学组合数学试卷

组合数学 期末 张秀平.

试题

1. 在边长为 \(1\) 的正方形中至少放入几个点, 才能保证至少有两点的距离不大于 \(\frac{1}{3}\)?
2. 化简组合恒等式 \[\sum\limits_{k=0}^n \binom{\alpha+k}{p+k}\binom{p+k}{k}.\]
3. 记初始排列为 \(1,2,\cdots,n\), 将其重排后为 \(a_1,\cdots,a_n\), s.t. \(a_{i+1}\neq a_i+1\) \((i=1,2,\cdots,n-1)\), 令其方案数为 \(Q_n\):
   1. 利用组合方法推导 \(Q_n\) 的递推关系;
   2. 利用容斥原理推导 \(Q_n\) 的递推关系.
4. 用延迟认可算法求下面优先矩阵的稳定完备婚姻匹配(男选女, 女选男各做一次), 并给出简单评价:

	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)
\(A\)	\((1,4)\)	\((2,3)\)	\((3,6)\)	\((4,2)\)	\((5,5)\)	\((6,1)\)
\(B\)	\((3,1)\)	\((5,2)\)	\((6,5)\)	\((2,6)\)	\((1,3)\)	\((4,4)\)
\(C\)	\((5,5)\)	\((3,6)\)	\((6,1)\)	\((4,4)\)	\((2,2)\)	\((1,3)\)
\(D\)	\((6,6)\)	\((5,5)\)	\((4,4)\)	\((3,3)\)	\((2,1)\)	\((1,2)\)
\(E\)	\((1,3)\)	\((3,1)\)	\((5,2)\)	\((2,5)\)	\((4,4)\)	\((6,6)\)
\(F\)	\((4,2)\)	\((5,4)\)	\((6,3)\)	\((1,1)\)	\((2,6)\)	\((3,5)\)

5. 设数列满足 \(\{f_n\}\) 满足 \(f_0=1\), \(f_1=1\), \(f_n=f_{n-1}+f_{n-2}~(n\geqslant 2)\), 令 \(g_n=f_{2n}\), \(h_n=f_n^2\).
   1. 分别求 \(f\), \(g\), \(h\) 的通项公式;
   2. 求 \(g_n\) 与 \(h_n\) 的生成函数.
6. 构造一个指标为 \(1\) 的 \(9\) 元素 \(STS\), 判断它是否可解, 并给出理由.