柱体涂色与伯努利---欧拉的装错信封的问题

最近又与涂色问题干上了,我们看下一道题:

用四种不同颜色给三棱柱ABC-DEF六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种?

解法一:

对于涂色问题,我们按照颜色来分类,首先观察有哪些区域的颜色可以相同,至少需要多少颜色。

颜色可以相同的区域可以是AE,AF,BD,BF,CE,CD,显然至少需要三种颜色。

接下来分类:

第一类:需要三种颜色,由于有6个点,且着色点相同最多有两个,所以三个正整数和为6,且最大为2的情况只有2+2+2=6。

AE—BF—CD,AF—BD—CE,有2种。

有2×4×3×2=48。

第二类:需要四种颜色,由于有6个点,且着色点相同最多有两个,所以四个正整数和为6,且最大为2的情况只有2+2+1+1=6。

AE—BD—C—F,AE—BF—C—D,AE—CD—B—F,AF—BD—C—E,AF—CE—B—D,AF—CD—B—E,BD—CE—A—F,BF—CE—A—D,BF—CD—A—E,有9种。

有9×4×3×2×1=216。

共有48+216=264种。

解法二:

我们选择分步完成:

第一步:先涂上底面ABC,有4×3×2=24种。

第二步:在涂下底面DEF,有两类:

不选择第四种颜色,实际上变成了三种颜色排列,但是与以上颜色不同。

例如:    上面是1、2、3

下面只能是2、3、1

3、1、2,共两种。

选择第四种颜色,实际上变成了一种新颜色与以上三种颜色中的两个颜色,共有3种选法。接下来排列,但是与以上颜色不同。

例如:譬如选的是1、2。上面是1、2、3

下面只能是4、1、2

2、4、1

2、1、4,共三种。

有2+3×3=11种。

共有24×11=264种。

接下来我们来看解法二的第二步的第一类:

转化成下面问题:

将标有1、2、3号的小球放到编号为1、2、3的盒子中,要求每个盒子中有一个小球,且小球号码与盒子编号不同,有多少种放置方法?

利用穷举法很容易解出:

2——3——1;3——1——2,共2种。

对于四人各写一张贺年卡互相赠送的问题,我们也可以利用穷举法列出:

如果人数再加一人,即五人各写一张贺年卡互相赠送的问题,我们利用穷举法列出:

4人的错排问题只有9个,而5人的错排数有44个,可想而知,随着数的增大,错排数将愈来愈大,显然再用穷举法不再是最佳方案,为了解决这一问题,我们可以利用递推思想完成。

如果人数再加一人,即六人各写一张贺年卡互相赠送的问题,我们利用总体淘汰法分析:

当然,也可以利用递推思想来分析:

进而得到错位排列的两个递推公式:

我们还可以利用容斥原理解决这类问题:

对于最开始题目中的解法二的第二步的第一类,就相当于三个元素的错位排列,

我们有以下几种方式求出:

接下来我们来看解法二的第二步的第二类:

如果我们把4看做3的话,看以下穷举的情况,

转化成下面问题:

将标有1、2、3号的小球放到编号为1、2、3的盒子中,要求每个盒子中有一个小球,且1、2小球号码与盒子的编号不同,3号小球不受限制,则有多少种放置方法?

利用穷举法很容易解出:

3——1——2;2——3——1;2——1——3,共3种。

接下来,尝试完成下面著名的“夫妻舞会问题”与“夫妻入座问题”

【嗨!难以想象,当初想出这两道题目的人的思想有多龌龊!】

呵呵,笑谈而已!

一次苏东坡和佛印和尚在林中打坐,日移竹影,一片寂然,很久了,佛印对苏东坡说:“观君坐姿,酷似佛祖。”苏东坡心中欢喜,看到佛印的褐色袈裟透迄在地,对佛印说:“上人坐姿,活像一堆牛粪。”佛印和尚微笑而已。

(0)

相关推荐

  • 汉字Unicode编码表,曾经爱玩的你还记得吗?

    在前些年QQ上就流行着这么一个游戏:在QQ聊天栏里按住ALT不放,再按小键盘数字29482(只能用小键盘的数字键,用笔记本的不行哦),然后放开ALT,将会出现你自己的名字.结果是出现一个"猪 ...

  • 欧拉、伯努利、达朗贝尔关于弦振动问题的论战,催生了傅立叶级数

    在自然世界中,存在着许多的波动现象,它是一种常见的物质运动形式,如声波.水波等,后来物理学家对此类现象经过归纳总结,把某一物理量的扰动或振动在空间逐点传递时形成的运动形式都称之为波动. 各种形式的波的 ...

  • 多伯努利滤波的快速红外弱小目标检测与跟踪

    李翠芸,李 宁,姬红兵 (西安电子科技大学电子工程学院,陕西西安 710071) 摘要:针对复杂背景下多个弱目标检测与跟踪中存在的跟踪不稳定.非实时及量测模型高度非线性问题,提出一种基于多伯努利滤波的 ...

  • 常识积累 | 生活中的伯努利原理

    伯努利,瑞士物理学家.数学家.医学家.作为伯努利数学家族中的杰出代表,16岁时就在巴塞尔大学攻读哲学与逻辑,后获得哲学硕士学位,17岁开始学医,于1721年获医学硕士学位,成为外科名医并担任过解剖学教 ...

  • 古有伯努利卖论文给洛必达,今有SCI论文小铺,是人才吗?

    古有伯努利卖论文给洛必达,今有SCI论文小铺,是人才吗?

  • “伯努利升力原理”的批判

    编者按: 马丁·宋贝先生的这篇文章,揭示了一个耸人听闻的事实,那就是我们耳熟能详的关于飞机升力原理的解释,竟然是一个彻头彻尾的谬误,而著名的伯努利先生也是此事的受害者.发表于1993年的这篇文章,由于 ...

  • 如何计算前n个整数的p次幂的和?证明伯努利幂和

    瑞士的伯努利家族共有八位世界著名的数学家,雅各布·伯努利(Jacob Bernoulli)便是其中之一.1713年,雅各布·伯努利提出了前n个整数的p次幂之和的表达式.他的解是n的(p+1)次多项式, ...

  • 伯努利原理[伯努利原理]

    方程式 原表达形式 伯努利原理 适于理想流体(不存在摩擦阻力).式中各项分别表示单位流体的动能.位能.静压能之差. 假设条件 使用伯努利定律必须符合以下假设,方可使用:如没完全符合以下假设,所求的解也 ...

  • 通俗讲解伯努利原理及其应用

    当年的流体力学是那么的难学,如果有人这么给我们解释,我相信,我肯定能通过考试的.现在想起来,都是满满的回忆呀.本文从实例篇.理论篇.应用篇三个方面展开,肯定让您不虚此行. 天才/学霸/大神--伯努利 ...

  • 草原犬鼠都会利用的伯努利原理

    丹尼尔·伯努利在1726年提出了"伯努利原理".这是在流体力学的连续介质理论方程建立之前,水力学所采用的基本原理,其实质是流体的机械能守恒.即:动能 重力势能 压力势能=常数.其最 ...