你问我答 • minty • 发表于 1 年前 • 最后回复来自 LasyCat • 1 年前

有N封请柬和对应的N个信封，求解请柬完全装错的装法有多少种？

共收到11条回复

wolf 1 年前湖北省 #1

这题属于看起来很简单，第一次做还是挺有一点难度的。

dasuda 1 年前湖北省 #2

(n-1)!

tl070602023 1 年前湖北省 #3

这个是不是皇后算法那个题

tl070602023 1 年前湖北省 #4

回溯算法？

testicles 1 年前湖北省 #5

F(n) F(n-1) ..... F(2) F(1)

lllc 1 年前湖北省 #6

错排问题可以用递推公式得到通项

keley 1 年前湖北省 #7

!N=N!
i=0
∑
N

i!
(−1)
i

其中，N! 表示 N 的阶乘，
∑

i

0
N
(
−
1
)
i
i
!
∑
i=0
N

i!
(−1)
i

是一个交替级数。

我们可以通过递归关系来计算德里克数，递归公式为：

N

(
N
−
1
)
(
!
(
N
−
1
)
+
!
(
N
−
2
)
)
!N=(N−1)(!(N−1)+!(N−2))

fcx 1 年前湖北省 #8

这个题乍看起来很复杂，实际上比看起来更复杂

tcl 1 年前湖北省 #9

@dasuda
初次计算，我也以为是（N-1）！
但是从N=4开始带入检验的时候，我发现有问题，因为K-1封请柬有可能刚好放在第K个信封里面了；那么第K封请柬就也有K-1种选择，而不是K-2种选择。

nobt 1 年前湖北省 #10

我能不能先贪心一下？

LasyCat 1 年前湖北省 #11

显然得：f（n）=（n-1）*（n-1）！/ 2 （n>2）

请绑定手机号后，再发言，点击此处