Questions in category: 组合数学 (Combinatorics)
计算数学 >> 离散数学 >> 组合数学

1. 黑白棋取法问题

Posted by haifeng on 2017-04-02 10:27:09 last update 2017-04-04 08:24:35 | Answers (2) | 收藏


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

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

 

 


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

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

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

 

2. 11 选 5 的中奖概率

Posted by haifeng on 2014-10-27 12:28:09 last update 2014-12-19 14:52:39 | Answers (0) | 收藏


从 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.
\]


总结:

中奖概率非常小. 


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

3. 正 $n$ 边形中由其顶点构成的三角形的问题.

Posted by haifeng on 2014-09-28 20:02:15 last update 2014-09-28 20:02:15 | Answers (1) | 收藏


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

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

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

Posted by haifeng on 2012-11-06 22:23:00 last update 2012-11-06 22:23:00 | Answers (1) | 收藏


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

5. 背包问题(Knapsack problem)

Posted by haifeng on 2011-08-10 15:41:46 last update 2011-08-10 15:43:53 | Answers (0) | 收藏


也称 rucksack problem.


http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/KnapsackProblem.htm

6. Hadamard 矩阵的存在性猜想

Posted by haifeng on 2011-05-04 23:47:17 last update 0000-00-00 00:00:00 | Answers (0) | 收藏


The Hadamard conjecture

7. 研究组合数学的学者

Posted by haifeng on 2011-05-04 23:38:10 last update 0000-00-00 00:00:00 | Answers (0) | 收藏