置换

✍ dations ◷ 2025-09-17 11:39:27 #置换
排列(英语:Permutation)是将相异对象或符号根据确定的顺序重排。每个顺序都称作一个排列。例如,从一到六的数字有720种排列,对应于由这些数字组成的所有不重复亦不阙漏的序列,例如"4, 5, 6, 1, 2, 3" 与1, 3, 5, 2, 4, 6。置换(排列)的广义概念在不同语境下有不同的形式定义:此节使用排列的传统定义。从 n {displaystyle n} 个相异元素中取出 k {displaystyle k} 个元素, k {displaystyle k} 个元素的排列数量为:其中P意为Permutation(排列),!表示阶乘运算。以赛马为例,有8匹马参加比赛,玩家需要在彩票上填入前三胜出的马匹的号码,从8匹马中取出3匹马来排前3名,排列数量为:因为一共存在336种可能性,因此玩家在一次填入中中奖的概率应该是:不过,中国大陆的教科书则是把从n取k的情况记作 P n k {displaystyle P_{n}^{k}} 或 A n k {displaystyle A_{n}^{k}} (A代表Arrangement,即排列)。上面的例子是建立在取出元素不重复出现状况。从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素, k {displaystyle k} 个元素可以重复出现,这排列数量为:以四星彩为例,10个数字取4个数字,因可能重复所以排列数量为:这时的一次性添入中奖的概率就应该是:在集合论与抽象代数等领域中,“置换”一词被保留为集合(通常是有限集)到自身的双射的一个称呼。例如对于从一到十的数字构成的集合,其置换将是从集合 { 1 , … , 10 } {displaystyle {1,ldots ,10}} 到自身的双射。因此,置换是拥有相同定义域与上域的函数,且其为双射的。一个集合上的置换在函数合成运算下构成一个群,称为对称群或置换群。以下仅考虑有限集上的置换(视为双射),由于 n {displaystyle n} 个元素的有限集可以一一对应到集合 { 1 , … , n } {displaystyle {1,ldots ,n}} ,有限集的置换可以化约到形如 {1, ..., n} 的集合之置换。此时有两种表示法。第一,利用矩阵符号将自然排序写在第一列,而将置换后的排序写在第二列。例如:表示集合 {1,2,3,4,5} 上的置换 s : s ( 1 ) = 2 , s ( 2 ) = 5 , s ( 3 ) = 4 , s ( 4 ) = 3 , s ( 5 ) = 1 {displaystyle s:s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1} 。第二,借由置换的相继作用描述,这被称为“轮换分解”。分解方式如下:固定置换 s {displaystyle s} 。对任一元素 x {displaystyle x} ,由于集合有限而 s {displaystyle s} 是双射,必存在正整数 N {displaystyle N} 使得 s N ( x ) = x {displaystyle s^{N}(x)=x} ,故可将置换 s {displaystyle s} 对 x {displaystyle x} 的相继作用表成 ( x s ( x ) s 2 ( x ) ⋯ s m − 1 ( x ) ) {displaystyle (x;s(x);s^{2}(x)cdots s^{m-1}(x))} ,其中 m {displaystyle m} 是满足 s m ( x ) = x {displaystyle s^{m}(x)=x} 的最小正整数。称上述表法为 x {displaystyle x} 在 s {displaystyle s} 下的轮换, m {displaystyle m} 称为轮换的长度。我们在此将轮换视作环状排列,例如是同一个轮换。由此可知 x {displaystyle x} 在 s {displaystyle s} 下的轮换只决定于 x {displaystyle x} 在 s {displaystyle s} 作用下的轨道,于是,任两个元素 x , y {displaystyle x,y} 或给出同一个轮换,或给出不交的轮换。我们将轮换 ( x 1 ⋯ x m ) {displaystyle (x_{1};cdots x_{m})} 理解为一类特殊的置换:仅须定义置换 s {displaystyle s} 为 s : x 1 ↦ x 2 , … , x m − 1 ↦ x m , x m ↦ x 1 {displaystyle s:x_{1}mapsto x_{2},ldots ,x_{m-1}mapsto x_{m},x_{m}mapsto x_{1}} ,而在其它元素上定义为恒等映射。不交的轮换在函数合成的意义下可相交换。因此我们可以将集合 {1, ..., n} 对一置换分解成不交轮换的合成,此分解若不计顺序则是唯一的。例如前一个例子的 s {displaystyle s} 就对应到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。轮换一是种特殊的排列。如果给定 f : X → X {displaystyle f:Xrightarrow X} 是 X {displaystyle X} 上的一个排列, A {displaystyle A} 为 X {displaystyle X} 上的一个子集。若有∃ A ∈ X , A = { x 1 , x 2 , ⋯ , x l } {displaystyle exists Ain X,A={x_{1},x_{2},cdots ,x_{l}}}{ f ( x 1 ) = x 2 , f ( x 2 ) = x 3 , ⋯ , f ( x l ) = x 1 f ( x ) = x , x ∉ A {displaystyle {begin{cases}f(x_{1})=x_{2},f(x_{2})=x_{3},cdots ,f(x_{l})=x_{1}\f(x)=x,xnot in Aend{cases}}}则称 f {displaystyle f}  为一个轮换。 l {displaystyle l}  为轮换的长度。在上节的轮换表法中,长度等于二的轮换称为换位,这种轮换 ( x y ) {displaystyle (x;y)} 不外是将元素 x , y {displaystyle x,y} 交换,并保持其它元素不变。对称群可以由换位生成。由于轮换长度为 l {displaystyle l} 的轮换 C {displaystyle C} 可分解为最少 k = l − 1 {displaystyle k=l-1} 个换位,若 k {displaystyle k} 为偶数,则 C {displaystyle C} 为偶轮换,否则C为奇轮换。即轮换的长度为奇数,该轮换为偶轮换;轮换的长度为偶数,该轮换为奇轮换。由此可定义任一排列的奇偶性,并可证明:一个排列是偶排列的充要条件是它可以由偶数个换位生成。偶轮换在置换群中构成一个正规子群,称为交错群。某些旧课本将排列视为变量值的赋值。在计算机科学中,这就是将值赋予变量的赋值运算子,并要求每个值只能赋予一个变量。赋值/代入的差别表明函数式编程与指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将排列看作函数,其间运算看作函数合成,函数式编程也类似。就赋值语言的观点,一个代入是将给定的值“同时”重排,这是个有名的问题。取一个无向图G,将图G的n个顶点标记v1,...,vn,对应一个排列( s(1) s(2) ... s(n) ),当且仅当s(i) < s(j) 而 i > j,则图的vi和vj相连,这样的图称为排列图。排列图的补图必是排列图。多数计算机都有个计算排列数的 nPr 键。然而此键在一些最先进的桌上型机种中却被隐藏了。例如:在 TI-83 中,按 MATH、三次右键、再按二。在卡西欧的图形计算机中,按 OPTN,一次右键(F6)、PROB(F3)、nPr(F2)。多数试算表软件都有函式 PERMUT(Number,Number chosen),用以计算排列。Number 是描述对象数量的一个整数,Number chosen 是描述每个排列中所取对象数的整数。

相关

  • 稻大鼠稻大鼠(学名:Oryzomys palustris)是北美洲一种半水生的啮齿类。它们主要分布在美国东部及南部,由新泽西州及肯萨斯州南部至科罗拉多州及墨西哥塔毛利帕斯州最东北端。;其分布地以
  • 景天庚酮糖景天庚酮糖(英语:Sedoheptulose),即D-阿卓-2-庚酮糖(英语:D-altro-2-heptulo-se),是由七个碳原子构成的酮糖。存在于几乎所有景天科植物中。其衍生物是单糖降解代谢的中间物。果聚糖
  • 汝州温泉汝州温泉风景区位于河南省汝州市西部的温泉镇。这里有三个温泉群,有“灵泉”、“神泉”之称。历史上是皇家温泉,包括唐代的女皇武则天在内的汉唐两代十三帝四妃曾来此沐浴。武
  • 辉锑矿辉锑矿为组成锑矿石的重要有用矿物,晶体呈柱状、针状。颜色和条痕均为铅灰色。金属光泽。相对密度4.6,硬度2-2.5.解理 面上有纹理。形成于低温热液矿床中,常与辰砂、雄黄、雌黄
  • UBC银色与金色科罗拉多大学博尔德分校(英语:University of Colorado Boulder;常用缩写:CU Boulder)是科罗拉多大学系统(英语:University of Colorado)的旗舰校。它成立于1876年,比科罗拉
  • 布朗大学1764年(美洲新英格兰英属罗德岛和普罗维登斯殖民地学院) 1805年(布朗大学)布朗大学(英语:Brown University,拉丁语:Universitas Brunensis),简称布朗(英语:Brown),位于美国罗德岛州普罗维
  • 台湾糖业铁路坐标:22°45′21″N 120°18′51″E / 22.7556997°N 120.3142969°E / 22.7556997; 120.3142969台湾糖业铁路,简称糖铁,地方或称五分车、五分仔车,是为配合台湾糖业需要而兴建
  • 玻意耳定律波意耳-马略特定律(英语:Boyle's law,也称作Boyle–Mariotte law或Mariotte's law),在定量定温下,理想气体的体积与压强成反比。是由爱尔兰化学家罗伯特·波义耳,在1662年根据实验
  • span class=nowrapY(NOsub3/sub)sub3/sub/span&硝酸钇是一种无机化合物,化学式为Y(NO3)3。它的受热分解经YONO3,最终生成Y2O3。硝酸钇可由氧化钇和硝酸反应得到:Y(OH)3
  • 金弘集金弘集(1842年-1896年),字敬能,号道园、以政学斋,原名金宏集;本籍庆尚道庆州,谥号忠献(충헌),赠大提学,朝鲜王朝后期的政治人物,亲日派,俄馆播迁时被巡检处死。金弘集出身庆州金氏,是肃宗仁