亚太教育创新
Innovations in Asia-Pacific Education
- 主办单位:未來中國國際出版集團有限公司
- ISSN:3079-3661（P）
- ISSN:3079-9503（O）
- 期刊分类:教育科学
- 出版周期:月刊
- 投稿量:2
- 浏览量:707
相关文章
暂无数据
重排与部分错排的数学特性及应用
Mathematical Characteristics and Applications of Permutations and Partial Derangements
引言
排列组合中的错排问题是一个经典计数模型，广泛应用于密码学、排班调度、匹配设计等领域。传统的全错排要求所有元素均不在原位，而部分错排则允许恰好指定数量的元素保位，更具现实意义。然而，实际问题往往涉及更复杂的约束条件，例如元素按组划分、多个信息维度的联合匹配等，此时经典的部分错排模型难以直接适用。本文针对这些复杂场景，以容斥原理为核心工具，对部分错排模型进行系统推广。首先将元素分组，讨论组级维度下恰好若干组存在保位元素的计数方法；进而考虑姓名卡与照片的双信息匹配问题，建立双重部分错排模型。通过严格的定理证明，揭示不同维度下禁位排列的统一本质，为处理多约束排列问题提供理论依据与计算方法。
一、定义及相关概念
设π是由n个相异元a1,a2,...,an作成的全排列，如果aj(1≤j≤n)
在π中排在第j位，则称aj在π中保位。以D(n,m)表示由a1,a2,...,an作成的恰好有m个元素保位的全排列的个数，D(n,m)称为m-部分错排数。则有：
特别地，当m=n-1或m=n时，则所有元素保位，记D(n,n)=1；当m=0时，则所有元素都不保位，即n元重排：
注：Dn称为n元重排数，令D0=1。
二、推广证明
在实际排列问题中常需对元素进行分组划分，以组为单位设定保位要求，如恰好t个组存在保位元素，接下来以此为场景，进行部分错排模型的组级维度推广。
定义
共有n组人，每组均有k个人，以aij表示第i组的第j人。现将所有人分配到n行k列个位置中，若成员aij坐到第i行第j列，则称该成员具有保位性质。
定理1
将n组人(每组k个人)分配到n行k列个位置上，则恰好有m个组，每组均有r个人保位的分配方法为：
其中，N=nk-tr为剩余总元素数，K=t(k-r)为具有禁位约束性质的受限元素数。
证明：该问题可以利用容斥原理解决，令S为全体nk个人在n×k个位置上所有排列构成的集合，则S=(nk)!。
设s∈S，对于i=1,2,...,n，若在排列S中，第i组恰好有r个人保位（即该组有r个人保位，剩下的k-r人禁位），则称排列s具有性质ai，可知满足分配方法的排列总数为S中恰好具有a1,a2,...,an中m个性质的元素个数，记为N(m)，则：。
其中
接下来计算，记S中同时具有t个性质的排列数，此类排列的构造可分两步计算：
第一步，在这t组的每一组中，选出r个成员具有保位性质，选法有种；
第二步，处理剩余的成员，此时，剩余成员总数为N=nk-tr，需要注意的是，选定的t组中，每组剩余k-r个成员需要“不保位”（禁位），即共K=t(k-r)个，而剩余未选定的n-t组中所有元素不受限制，将这N个成员安排在剩余的N个位置上，由容斥原理可知相应的排列数为：
综上可得：
因此，，所以得到了定理1。
组级维度的部分错排仍属于单一信息维度的禁位排列，无论元素是否分组，匹配关系均为元素对应单一位置信息，而实际场景中还存在元素与目标的双信息联合匹配问题，元素的保位或禁位需同时满足两个信息维度的要求，且元素选择相互影响。于是以此为场景，实现部分错排模型从单一信息维度到双信息联合维度的二次推广，定理2仍以容斥原理为核心，兼顾信息的独立性与选择的关联性。
定理2
有n个人各填写一个姓名卡并交一张照片，并把这些姓名卡和照片任意装入m(m≥n)个有姓名的档案袋（每袋只装一份姓名卡和一张照片）。则恰好有t(0≤t≤n)个人的姓名卡和照片都装对了其对应档案袋的不同装法数为：
证明：令S为全体n个人的姓名和照片分配到m个档案袋（每袋各一份卡和照片）的所有可能装法构成的集合。
由于姓名卡和照片的分配相互独立，分配n份姓名卡到m个袋子的方法有种，分配照片的方法也有种，故。
设s∈S，对于i=1,2,...,n，若在装法s中，第i人的姓名卡和照片均装入了他自己的档案袋中，则称装法s具有性质ai。
我们要求的是集合S中，恰好具有a1,a2,...,an中t个性质的元素个数，记为N(t)，显然：
其中
现在计算同时具有j个性质的装法数。此时这j个人的姓名卡和照片都装进了自己的档案袋中，我们只需计算剩下的n-j个人的姓名卡和照片的装法。
首先，将的n-j个人的姓名卡放进m-j个档案袋中，有种放法；
其次，剩下的n-j张照片也有种放法，所以，从而可知，因此：
由于，所以：
令i=j-t，则：
三、结论
综上，本文通过单一元素单维度、到单一元素双维度的递进式推广，构建了部分错排的系列模型，基础、双重均以禁位排列为本质，以容斥原理为核心求解方法，遵循选定保位对象和剩余对象禁位排列的统一推导逻辑，且后序推广模型可在特定条件下退化为基础部分错排模型，形成层层递进的推广体系。
参考文献：
- [1] 曹汝成.组合数学[M].广州:华南理工大学出版,2012.
- [2] 布鲁迪(RichardA.Brualdi).组合数学[M].冯舜玺,罗平,裴伟东,译.北京:机械工业出版社,2002.
- [3] 郑翔.全错位排列问题数学模型的求解及推广[J].高等函授学报(自然科学版),2005(03):34-36.