【组合数学】全错位排列的递推公式推导

news/2024/10/30 23:21:23/

简介

假设现在我有三个信封A,B,C,并且现在有三个信纸a,b,c。
按照道理的话是,a塞入A信封,b塞入B信封,c塞入C信封。
但是现在,想要问,对于a,b,c全部塞错的情况,有多少种呢?
比如把b塞入A,把c塞入B,把a塞入C就是一种。

解析

对于这个问题,自己推导的时候就卡在了一个很关键的地方,让我怎么也想不明白,后来看了答案后,虽然知道了最终公式是什么,但是网上的“容易得出”,或者干脆略过小熊这个🐷脑袋怎么也想不明白。

让我们先来看看这个问题,现在,我们记错排公式为 D ( N ) D(N) D(N):有N个信封和N个信纸的所有错误排列个数。

小熊是这样推导的:

现在假设我们有,求 D ( N ) D(N) D(N)
(A)(B)(C)(D)…(N)
这几个信封,并且有如下几个信纸:
a、b、c、d…、n

那我首先知道,对于未来所有的结论,第一列应该是:
b…
c…
d…

n…

这么多行,应该总共是 n - 1 行,所以先记录在这里。

那么对于每一行,我想答案应该是相同的,因为它具有对称性(比如,你只需要改改名字)。

下面来看第一行
b…
情况一 这说明,我们在把b信纸塞入(A)信封中,现在,若把a塞入(B)中,也就是a和b的对应信封调换了一下位置,那么剩下的(C)、(D)、(E)、…和信纸c、d、e、…就是一个新的问题,为 D ( N − 2 ) D(N-2) D(N2)

以上是第一种情况,那么对于a信纸不塞入(B)信封中的情况呢?

现在我们有信纸是:a、c、d、…n,因为b已经被塞入了,先别动。

情况二 那我们考虑,把信纸a换一个名字,现在悄悄改为b,这样现在我们有信封(B)、(C)、(D)、…和信纸b、c、d、…n来参与全错位的排列。可以肯定的是,最终结果排列中,每一种排列的b都不会塞入进(B)中,每一种排列的c也不可能塞入(C)中, 所以现在,我再把b的名字悄悄改为a,so~,现在,a不会塞入(B)中,并且我们也统计到了这种情况的所有错位排列。这是情况二。

综合考虑了情况一和情况二,现在我们可以大胆的写出公式了。

递推公式

D ( N ) = ( N − 1 ) ∗ [ D ( N − 2 ) + D ( N − 1 ) ] D(N)=(N-1)*[D(N-2)+D(N-1)] D(N)=(N1)[D(N2)+D(N1)]
其中肉眼可见: D ( 1 ) = 0 , D ( 2 ) = 1 D(1)=0,D(2)=1 D(1)=0,D(2)=1

附录

因为卡住了D(n-1)这个东西是怎么来的,浪费了快两个小时的时间呜呜。

如果喜欢的话,请点赞~


http://www.ppmy.cn/news/70201.html

相关文章

[JavaScript]JSON对象

eval函数 eval函数能将一个字符串当做一段JS代码解释并执行。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name&quo…

什么是Java中的阻塞队列?它有什么作用?

在Java中&#xff0c;阻塞队列是一种特殊的队列&#xff0c;它可以在队列为空或队列已满时阻塞添加或移除元素的操作。阻塞队列通常用于多线程编程中&#xff0c;可以帮助我们更加方便地进行线程通信和协作。在本文中&#xff0c;我将从面试的角度&#xff0c;详细讲解Java中的…

深入篇【C++】类与对象:运算符重载详解

深入篇【C】类与对象&#xff1a;运算符重载详解 ⏰一.运算符重载&#x1f553;1.<运算符重载&#x1f550;2.>运算符重载&#x1f552;3.运算符重载&#x1f551;4.运算符重载①.格式1.改进12.改进2 ②.默认成员函数1.功能2.不足 &#x1f553;5.<运算符重载&#x1…

什么是MQTT,和MQ有什么区别

什么是MQTT&#xff0c;和MQ有什么区别 概述常用的软件和MQ的主要区别应用场景 概述 MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;是一种轻量级的发布/订阅消息传输协议&#xff0c;主要用于物联网&#xff08;IoT&#xff09;领域&#xff0c;特别是在网…

方案设计与开发——血氧仪方案

血氧仪是一种专业的医疗检查工具&#xff0c;可以测定人体的血氧饱和度&#xff0c;是很多医疗机构、家庭的必备测量设备之一。下面我们来介绍一下血氧仪产品方案。 一、血氧仪运行原理 血氧仪采用光学吸收法进行检测&#xff0c;它通过将红外线和可见光一起照射到人体的指尖上…

Python图像处理:OpenCV入门教程

Python图像处理&#xff1a;OpenCV入门教程 一、Python图像处理概述1 图像处理的基本概念2 Python在图像处理中的优势 二、OpenCV简介1 OpenCV的概述2 OpenCV的特点3 OpenCV的应用领域 三、OpenCV安装与环境配置1 OpenCV的安装方法2 OpenCV的环境配置 四、图像处理的基础知识1 …

2023/5/14 数值计算方法考试复盘

第一题 问我1-()如果减少乘除次数,那么如何做出变形。 正确解法&#xff1a; 可以利用乘法分配律&#xff0c;将1拆分成1 - 1/2! 1/2! - 1/3! 1/3! - ... - 1/n! 1/n!&#xff0c;然后将拆分出来的两项合并&#xff0c;得到&#xff1a; 1 - (1/2! - 1/2!) - (1/3! - 1/3…

如何使用 CSS 中的边距(margin)属性来定义元素在网页中的边距

首先&#xff0c;我要说的是&#xff0c;CSS边距&#xff08;margin&#xff09;属性是一个非常有用的属性&#xff0c;它可以用来定义元素在网页中的边距。不过&#xff0c;如果你是一个新手&#xff0c;我建议你从最基础的知识开始学习&#xff0c;因为它可以帮助你更好地理解…