首页 >
置换
✍ dations ◷ 2025-07-01 09:05:38 #置换
排列(英语: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 是描述每个排列中所取对象数的整数。
相关
- 圣座圣座(拉丁语:Sancta Sedes;意大利语:Santa Sede;拉丁语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode
- 偏执型人格障碍妄想型人格障碍(paranoid personality disorder)又叫偏执型人格障碍,其症状常表现为:对别人的回绝,不信任,厌恶过度敏感,而且很容易怀疑别人对自己有这些反面情绪。别人无意中的一
- 裂殖子顶复门物种的生命周期包括以下各个阶段:作为一组细胞内寄生虫,顶复门的生命周期阶段让它们透过演化去适应它们所暴露于的各种复杂的环境下生存。簇虫亚纲的身细胞内都有营养体
- 惠特尼山惠特尼峰(英语:Mount Whitney)是位于美国加利福尼亚州内华达山脉中的一座山峰。惠特尼峰海拔高度为4,421米,是美国本土最高的山峰。惠特尼峰位于美洲杉国家公园内。名称来自于当
- 虚像虚像(英语:virtual image)指物体发出的光线经折射或反射后,如果为发散光线,其反向延长线相交而成的像,例如,平面镜、眼镜所成的像是虚像。光线到达面镜(如平面镜)时会发生反射,经过透
- b北周/b font style=color:#888small557-581/small<北周(557年—581年)是中国历史上南北朝的北朝之一。又称后周(宋朝以后鲜用),由宇文氏建立,定都长安,北周自建国后,统治实权一直在霸府宇文护身上,皇帝无力与之抗阻,为了摆脱宇文护的束
- 马克斯·普朗克古斯塔夫·路德维希·赫兹 瓦尔特·迈斯纳 华特·萧特基 马克斯·冯·劳厄 马克斯·亚伯拉罕 莫雷兹·石里克马克斯·卡尔·恩斯特·路德维希·普朗克(德语:Max Karl Ernst Lu
- 海绵城市海绵城市是一个比喻的说法,是一种在城市中建设防洪防涝并兼有生态环保功能的新型城市模型。比如建设透水路面以代替非透水的路面。国际通用术语为“低影响开发雨水系统构建”
- 嘌呤代谢作用许多生物利用代谢途径来合成或分解嘌呤。嘌呤在生物合成中会合成为核苷酸,特别是核糖核苷酸,即核糖-5-磷酸。 主要的调节步骤为PRPP合成酶产生磷酸核糖焦磷酸(PRPP)的反应,这个
- Imagine Dragons梦想之龙乐队(英语:Imagine Dragons)是一个成立于美国内华达州拉斯维加斯的独立摇滚乐队。乐队主唱丹·雷诺斯是拉斯维加斯人,2008年时正在杨百翰大学就学,在那里遇到了鼓手Tolma