错位排序公式_完全错位排列数

错位排序公式_完全错位排列数首先,对于D(n),有1~n这样n个元素错排,所以对于第一个元素①,它现在可能的位置有(n-1)个,倘若它在第k个元素的位置上,对于第k个元素而言,它所在的位置就有两种可能—第一种,它处在非第一个元素①位置上,所以对于接下来的排列就相当于是n-1个元素的错排,即D(n-1);第二种,它处在第一个元素①的位置上,所以在排列D(n)中有两个元素找到了位置,那么接下来的队列就相当于是n-2个元素的错排。…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

首先,对于D(n),有1~n这样n个元素错排,所以对于第一个元素①,它现在可能的位置有(n-1)个,倘若它在第k个元素的位置上,对于第k个元素而言,它所在的位置就有两种可能—第一种,它处在非第一个元素①位置上,所以对于接下来的排列就相当于是n-1个元素的错排,即D(n-1);第二种,它处在第一个元素①的位置上,所以在排列D(n)中有两个元素找到了位置,那么接下来的队列就相当于是n-2个元素的错排。因此,对于D(n)都有D(n)=(n-1)*(D(n-1)+D(n-2))【特殊的,D(1)=0,D(2)=1】。

容斥定理

正整数1,2, 3, ……, n的全排列有 n! 种,其中第k位是k的排列有 (n-1)! 种;当k分别取1, 2, 3, ……, n时,共有n*(n-1)!种排列是至少放对了一个的,由于所求的是错排的种数,所以应当减去这些排列;但是此时把同时有两个数不错排的排列多排除了一次,应补上;在补上时,把同时有三个数不错排的排列多补上了一次,应排除;……;继续这一过程,得到错排的排列种数为D(n) = n! – n!/1! + n!/2! – n!/3! + … + (-1)^n*n!/n!= ∑(k=2~n) (-1)^k * n! / k!   或者  错位排序公式_完全错位排列数

为方便起见,设D(k) = k! N(k), k = 1, 2, …, n,

则N(1) = 0, N(2) = 1/2.

n ≥ 3时,n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)

即 nN(n) = (n-1) N(n-1) + N(n-2)

于是有N(n) – N(n-1) = – [N(n-1) – N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) – N(1)] = (-1)^n / n!.

因此

N(n-1) – N(n-2) = (-1)^(n-1) / (n-1)!,

N(2) – N(1) = (-1)^2 / 2!.

相加,可得

N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!

因此

D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

此即错排公式

递推代码

long long rc[maxn];
inline void get_cp()
{
    rc[0]=1ll;
    for(int i=2;i<=n;i++)
        rc[i]=(i-1)*(rc[i-2]+rc[i-1])%mod;
}

Jetbrains全家桶1年46,售后保障稳定

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/201347.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vb FindwindowEx的用法实例「建议收藏」

    vb FindwindowEx的用法实例「建议收藏」’添加Command1ConstWS_CHILD=&amp;H40000000ConstWM_LBUTTONDOWN=&amp;H201ConstWM_LBUTTONUP=&amp;H202ConstSW_HIDE=0ConstSW_NORMAL=1PrivateTypeRECT   LeftAsLong   TopAsLong   …

  • 获取新浪可转债t+0列表,附上python代码

    ​​​​​​​@classmethoddefget_page_convertibleBonds(cls,pageIndex,retry_count=10):url=”http://vip.stock.finance.sina.com.cn/quotes_service/api/json_v2.php/Market_Center.getHQNodeDataSimple?page=%d&num=1000&sort=symbol&asc=1&node=h..

  • goland激活码永久(注册激活)

    (goland激活码永久)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html09LVN3XLKC-eyJsaWNlbnNlSWQi…

  • android activity跳转动画_叠化转场是什么意思

    android activity跳转动画_叠化转场是什么意思Android Reveal圆形Activity转场动画

  • 【STM32】STM32CubeMX教程二–基本使用(新建工程点亮LED灯)

    【STM32】STM32CubeMX教程二–基本使用(新建工程点亮LED灯)前言在配置好CubeMX之后,就是新建工程的开始了,那么首先我们需要一些准备,本片博客我们会很详细的介绍STM32CubeMx的基本使用和如何创建一个新的工程并且点亮LED灯面向初学者如果您想着快速实现工程的创建,可以直接跳过功能介绍,观看工程创建一栏并且,在新建工程时,我们分为了具体流程1~7如果您不想看每部分的讲解,直接按照流程操作即可,5分钟即可成功点亮LED灯安装…

  • 单片机中P1=0x01什么意思「建议收藏」

    单片机中P1=0x01什么意思「建议收藏」0x01是16进制,转化为二进制:00000001(字节(Byte)是计算机信息技术用于计量存储容量的一种计量单位,作为一个单位来处理的一个二进制数字串,是构成信息的一个小单位。最常用的字节是八位的字节,即它包含八位的二进制数)P1=0x01,表示P1.7~P.1=0,P1.0=1…

    2022年10月23日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号