我要招人

去企业版

首页 > 试题广场 >

6支笔，其笔身和笔帽颜色相同：但6支笔颜色各不相同，求全部笔

[单选题]

6支笔，其笔身和笔帽颜色相同：但6支笔颜色各不相同，求全部笔身都戴错笔帽的可能性有多少种？

```
265
```
```
266
```
```
267
```
```
268
```

查看答案及解析

推荐

SunburstRun

答案是A

排列组合的错排公式,D(n) = n! - n!/1! + n!/2! - n!/3! + … + (-1）^n*n!/n! = ∑(k=2~n) (-1)^k * n! / k!

D(0) = 1（所有的元素都放回原位、没有摆错的情况）

D(1) = 0（只剩下一个元素，无论如何也不可能摆错）

D(2) = 1（两者互换位置）

D(3) = 2（ABC变成BCA或CAB）

D(4) = 9

D(5) = 44

D(6) = 265

D(7) = 1854

D(8) = 14833

D(9) = 133496

D(10) = 1334961

推导公式详见 http://baike.baidu.com/link?url=eBRbIdNGC4sFeqsjhzVhJJCt5GIjJOa14qMpyRJ__lNMDmBIj6m6apUOPcyTsjYTezVZhq6POjjTkKyuMcLt5a

编辑于 2015-11-03 12:26:08 回复(4)

NieYanzhe

错排问题：详情见维基

公式：

简化公式：

发表于 2017-03-29 15:48:12 回复(0)

牛客125457号

递归即可。

f(n)=(n-1)*(f(n-1)+f(n-2))

发表于 2016-01-21 21:26:39 回复(1)

牛客895585036号

从反面考虑，求有戴对笔帽的情形有多少种。

C(6,1)*5!-C(6,2)*4!+C(6,3)*3!-C(6,4)*2!+C(6,5)*1-C(6,6)=455

都没戴对：6!-455=265

发表于 2020-05-24 10:36:14 回复(0)

bad_orange

将n个元素的全错位排列分成2步完成：

第一步,对于n中的任意一个元素（如1）有n-1种（其它的2，3，4…n）选择。

第二步，假设元素1选择了位置k，那么接下来排k，又将k的排法分成两类：第一类，k选择位置1，则余下的就是n-2个元素的错位全排列f(n-2). 第二类:若k选择了除1外的其他位置，那么问题实质上转化为n-1个元素（2，3，4…n）的错位全排列f(n-1).由分步和分类计数原理得f(n)=(n-1)[f(n-1)+f(n-2)](n>2)

递推公式 f(n)=(n-1)[f(n-1)+f(n-2)](n>2),f(1)=0,f(2)=1.

发表于 2017-09-12 19:37:40 回复(0)

BAT收了我吧

f(2)=1

f(3)=3!-C(3,1)f(2)-1

f(4)=4!-C(4,1)f(3)-C(4,2)f(2)-1

f(5)=5!-C(5,1)f(4)-C(5,2)f(3)-C(5,3)f(2)-1

f(6)=6!-C(6,1)f(5)-C(6,2)f(4)-C(6,3)f(3)-C(6,4)f(2)-1

发表于 2016-06-10 10:35:04 回复(0)

Terence_Ge

我来讲一下原理：

笔的ID为：1， 2 ， 3， 4， 5

笔帽的ID为：11， 22， 33， 44， 55

1->11, 2->22, 3->33, 4->44, 5->55

符号 -> 表示对应的意思。

上面的是求函数f(5)，f(5)表示五个笔的全部错排可能性。

下面过程：

1.对于笔1而言，有22,33,44,55四种选择

2. 假设笔1选择了22,

3.那么剩下的结果是： 2,3,4,5 -> 11,33,44,55 , 这样的对应方式有几种可能，可以分为下面4,5两种情况。

4.如果2->11，那么剩下3,4,5->33,44,55，可能性为f(3)；

5.如果2->33 / 44/ 55，也就是2 对应 33,44,55中的任意一个，2不对应到11，那么此时将2换为1的结果是等价的。

6.因此2->33/44/55时，该问题等价为1,3,4,5 -> 11,33,44,55.

7. 综上 f(5) = (5-1) * (1 * f(3) + f(4) );

由此，我们就可以得到通用公式f(n) = (n-1) * (f(n-1) + f(n-2))

发表于 2016-03-29 15:59:01 回复(11)

Willy

如果赶时间，可以这样：

首先结果肯定是5的倍数（6-1）；

然后选A

发表于 2016-09-06 11:58:12 回复(7)

stupig

偷个鸡。

6支笔，既然都排错笔帽，那么随便拿一支笔身，有5个笔帽可选，那么结果就是

5*(里面不care)

看答案，只有A（265 ）了

发表于 2016-09-05 17:22:27 回复(0)

已注销

递推式T(n+1)=n*(T(n)+T(n-1))

假想一群人玩换帽子游戏，每个人都不能戴自己的那顶帽子。n个人共有T(n)种帽子戴法，这时再来一个人，拿走了原来人群中a的一顶帽子，并留下了自己的帽子，这时有n*种选择方式，假如a不戴新来的人留下的帽子，这时仍有T(n）种戴法，如果a戴上了这顶帽子，那么剩下的人共有T（n-1）种戴法，综上得递推式T(n+1)=n*(T(n)+T(n-1))

发表于 2021-05-27 11:14:27 回复(0)

牛客1659416

用Ai分别表示第i支笔身没戴错笔帽，N(Ai)表示第i支笔身没有戴错笔帽的可能性总数

所求为6！-N(A1 U A2 U A3 U A4 U A5 U A6)。

N(A1 U A2 U A3 U A4 U A5 U A6)=6N(A1) - C(6,2)N(A1 A2) + C(6,3)N(A1 A2 A3) - C(6,4)N(A1 A2 A3 A4) + C(6,5)N(A1 A2 A3 A4 A5) - C(6,6)N(A1 A2 A3 A4 A5 A6)=6*5! - 15*4! + 20*3!-15*2! + 6 * 1 - 1 *1

所求为15*4! - 20 *3! +15*2! - 6*1!+1*1=265

发表于 2018-04-26 16:36:36 回复(1)

~火车头~

发现各位牛油都太强了。

发表于 2018-01-29 17:00:14 回复(0)

黎密特

公式为n!∑(-1)^i/i! i,0,n 此处n取6 公式来自enumerative combinatorics chapter2 example2.2.1 //计数组合第二章例2.2.1

发表于 2016-11-05 10:58:40 回复(0)

提交观点

问题信息

组合数学

来自：完美世界2016研发工...

上传者：SunburstRun

难度：

13条回答 624收藏 16472浏览

6支笔，其笔身和笔帽颜色相同：但6支笔颜色各不相同，求全部笔

问题信息

热门推荐

相关试题