置换和排列 | 您所在的位置:网站首页 › 排列组合基本内容是什么 › 置换和排列 |
置换和排列置换 一个有限集合 到自身的双射(即一一对应)称为 的一个置换。集合 上的置换可以表示为 意为将 映射为 ,其中 是 的一个排列。显然 上所有置换的数量为 。 乘法对于两个置换 和 , 和 的乘积记为 ,其值为 简单来说就是先经过 的映射,再经过 的映射。 排列设 是前 个正整数构成的集合, 是 的一个置换。记: 于是 仍然为 这 个数,只是顺序有所不同。 由 组成的一个有序组,称为 的一个排列。例如把前文 叫做 的一个排列。 前 个正整数 的不同排列共有 个。 逆序和逆序数在一个排列中,如果某一个较大的数排在某一个较小的数前面,就说这两个数构成一个反序或逆序。 在一个排列里出现的反序的总个数,叫做这个排列的反序数或逆序数。 一个排列的反序数可能是偶数也可能是奇数。有偶数个反序的排列叫做一个偶排列,有奇数个反序的排列叫做一个奇排列。 对换如果把 的排列中,任意两个数 和 交换,其余数保持不动,就得到一个新排列。对于排列施加这样一个变换叫做一个对换,用 表示。 定理:设 和 是 个数码的任意两个排列,那么总可以通过一系列对换,由 得出 。 定理:每一个对换都改变排列的奇偶性。 定理:当 至少为 时, 个数码的奇排列与偶排列个数相等,各为 个。 逆序数的计算方法逆序数的编程计算方法,可以使用归并排序,时间复杂度为 。 本页面最近更新:2023/8/25 08:40:58,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:2008verser, aofall, CoelacanthusHex, Early0v0, Great-designer, Marcythm, Persdre, shuzhouliu, Tiphereth-A本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
CopyRight 2018-2019 实验室设备网 版权所有 |