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

错位排序公式_完全错位排列数首先,对于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)
blank

相关推荐

  • 极大似然估计和贝叶斯估计的联系(似然估计和最大似然估计)

    1.什么是参数在机器学习中,我们经常使用一个模型来描述生成观察数据的过程。例如,我们可以使用一个随机森林模型来分类客户是否会取消订阅服务(称为流失建模),或者我们可以用线性模型根据公司的广告支出来预测公司的收入(这是一个线性回归的例子)。每个模型都包含自己的一组参数,这些参数最终定义了模型本身。我们可以把线性模型写成y=mx+c的形式。在广告预测收入的例子中,x可以表示广告支…

  • vue中如何关闭eslint「建议收藏」

    vue中如何关闭eslint「建议收藏」1.在目录中新建vue.config.js2.在新建文件中输入module.exports={lintOnSave:false}就可以关闭啦~

  • 选择排序-Java「建议收藏」

    选择排序-Java「建议收藏」堆排序理论:https://blog.csdn.net/qq_36186690/article/details/82505569代码:packagecom.paixu.paixuTest;importjava.util.Arrays;importjava.util.Scanner;/***选择排序*1)简单选择排序*2)堆排序*/publicclassxuanZhePaiXu{publicstaticvoidmain(String[]a

  • java mediatype属性_Java 如何获得文件的 Media Type「建议收藏」

    java mediatype属性_Java 如何获得文件的 Media Type「建议收藏」一般来说你可以使用ApacheTika来获得文件的类型。Tika是一个内容分析工具Maven设置maven的版本到你的POM文件中。org.apache.tikatika-core1.25测试代码例如,我们可以使用下面的测试代码。@TestpublicvoidwhenUsingTika_thenSuccess(){Filefile=newFile(“product.pn…

  • 安装tcping

    安装tcpingcping在windows和linux系统中都不是内建的命令,需要我们自己去下载下载命令wgethttps://sources.voidlinux.eu/tcping-1.3.5/tcping-1.3.5.tar.gzsudoyuminstallepel-releaseyuminstalltcpingtcpingwww.baidu.com443详细见图…

  • cygwin的163镜像(转)

    cygwin的163镜像(转)

发表回复

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

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