新浪博客

几个有趣的排列组合题目

2010-07-24 16:00阅读：

http://blog.sina.cn/dpool/blog/u/1880114690

今天看到几个有趣的排列组合题目，感觉和以往见过的不大相同。
1.纵横驰骋
国际象棋棋盘上的一个车要从左上角走到右下角。

走棋时必须遵循如下规定：
a.只能向下、向左或向右走；
b.任何一个格子都不能走入或者经过两次以上。
车一步可以走任意多个格子。那么它共有多少条不同的行走路径？
我看到题目后立刻开始用学过的排列组合计数模型去套，结果没能做出来，其实
这道题目很简单，但是简单问题复杂化恰恰是我们这些接受过高等教育的学生的通病。解答如下：
这个车从某一行跨过它下方的分割线达到下面一行共有8种可能性，这样从左上角到右下角共要跨越7次分割线，所以总的行走路径数为8^7=2097152。
哈哈，很简单吧，你是不是和我一样考虑复杂了呢？这也再次应证了奥卡姆剃刀原理：简单的往往是最优的。
2.电话号码
一家电话公司分配给用户的电话号码是所有的6位数(首位可以是0，数字可以重复)。但是为了避免某种差错，所有包含有相邻数字“12”的号码都必须排除在外。那么，有多少个6位数的电话号码由于这个原因将被取消实用？
这道题可以作为高考填空题的最后一题，还是不太容易做出正确结果得，得用到简单的容斥原理，解答如下：
为了去掉包含“12”的6位数，考虑如下5类号码：
A.1 2 * * * *
B.* 1 2 * * *
C.* * 1 2 * *
D.* * * 1 2 *
E.* * * * 1 2
每一类都包含10^4个号码。A和B没有共同的号码；B和C没有共同的号码；C和D，D和E亦然。另一方面，A和C有10^2个共同的号码；A和D，A和 E，B和D，B和E，C和E亦然。另外有一个号码121212是A、C、E所共有的。因此要排除的号码有5*10^4-6*10^2+1=49401个。
3.读出12121
你有多少种方法从下面这个数字排列阵中通过相互邻接(八向邻接)的数字读出12121？
1
1 2 1
1 2 1 2 1
1 2 1
1
任何一个1或2都可以在同一个12121中用上若干次。
这类题目的解题关键就是利用对称性，包括排列阵的对称性和待读序列的对称性，解答如下：
由于12121关于中间的“1”对称，解决问题的方法就是考虑排列阵中的每个“1”都可以作为12121中间的那个“1”。
中心位置的“1”与4个“2”相邻，而每个“2”又与4个“1”相邻，这样就有16个“21”，所以共有256个“12121”；
角上的每个“1”与1个“2”相邻，而每个“2”又与4个“1”相邻，这样就有4个“21”，共有16个“12121”，4个角上的“1”共有64个“12121”；
边上的每个“1”与2个“2”相邻，而每个“2”又与4个“1”相邻，这样就有8个“21”，共有64个“12121”，4个边上的“1”共有256个“12121”；
综上，总共有256+64+256=576种方法。
我再留几个类似题目给有兴趣的朋友玩玩。
a.读出ABC,共有12种方法。
A
A B A
A B C B A
A B A
A
b.读出POP，共有64种方法。
P
P O P
P O P O P
P O P
P
c.读出LEVEL，共有144种方法。
L
L E L
L E V E L
L E L
L
d.读出SPICE，共有60种方法。
E
E C E
E C I C E
E C I P I C E
E C I P S P I C E
E C I P I C E
E C I C E
E C E
E
e.读出OSLO(八向邻接)，共有108种方法。
O
O L O
O L S L O
O L S O S L O
O L S L O
O L O
O
f.读出REVIVER，共有784种方法。
R
R E R
R E V E R
R E V I V E R
R E V E R
R E R
R
g.读出LAVAL，共有400种方法。
L
L A L
L A V A L
L A V A V A L
L A V A L A V A L
L A V A V A L
L A V A L
L A L
L
h.读出ANNA(八向邻接且中间两个N必须用不同位置上的N)，共有432种方法。
A
A N A
A N N N A
A N N A N N A
A N N N A
A N A
A
i.读出123343321，共有21904种方法。
1
1 2 1
1 2 3 2 1
1 2 3 3 3 2 1
1 2 3 3 4 3 3 2 1
1 2 3 3 3 2 1
1 2 3 2 1
1 2 1
1
j.读出DEIFIED,共有1992种方法。
D
D E D
D E I E D
D E I F I E D
D E I F I F I E D
D E I F I E I F I E D
D E I F I E D E I F I E D
D E I F I E I F I E D
D E I F I F I E D
D E I F I E D
D E I E D
D E D
D

我的更多文章

下载客户端阅读体验更佳

APP专享