首页 > 代码库 > 错排【数学】【排列】【容斥原理】
错排【数学】【排列】【容斥原理】
今天整理数论的模板发现了错排的公式，推导有点忘记了，查了资料搞明白了。
已知错排的公式为：
D(n) = n ! ( 1 - 1 / 1 ! + 1 / 2 ! - 1 / 3 ! + ... + ( - 1 ) ^ n / n ! )
= ( n - 1 ) ( D ( n - 2 ) - D ( n - 1 ) )
下面是根据容斥得到答案的过程：
设1,2,...,n的全排列t1,t2,...,tn的集合为I,而使ti=i的全排列的集合记为Ai(1<=i<=n)。
Ai=(n - 1)!
则Dn=| I | - | A1 ∪ A2 ∪ ... ∪ An |.
所以Dn = n! - | A1 ∪ A2 ∪ .. . ∪ An |.
注意到 | Ai | = ( n - 1 ) ! , | Ai ∩ Aj | = ( n - 2 ) ! , ... , | A1 ∩ A2 ∩ ... ∩ An | = 0 ! = 1.
由容斥原理：
则： | A1 ∪ A2 ∪ ... ∪ An | = C ( n , 1 ) ( n - 1 ) ! - C ( n , 2 ) ( n - 2 ) ! + C ( n , 3 ) ( n - 3 ) ! - . . . - ( - 1 ) ^ n C ( n , n ) * 0 !
Dn = n ! - | A1 ∪ A2 ∪ ... ∪ An | = n ! - C ( n , 1 ) ( n - 1 ) ! + C ( n , 2 ) ( n - 2 ) ! - C ( n , 3 ) ( n - 3 ) ! + . . . + ( - 1 ) ^ n C ( n , n ) * 0 !
= n ! ( 1 - 1 / 1 ! + 1 / 2 ! - 1 / 3 ! + . . . + ( - 1 ) ^ n * 1 / n ! )
= ( n - 1 ) ( D ( n - 2 ) - D ( n - 1 ) )
证明完毕。
下面给出前面几组错排的数值：D(1) = 0
D(2) = 1
D(3) = 2
D(4) = 9
D(5)= 44
D(6) = 265
D(7) = 1854
D(8)= 14833
D(9) = 133496
D(10) = 1334961
错排【数学】【排列】【容斥原理】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。