线性代数全排列及其逆序

格式：ppt
大小：83.50 KB
文档页数：7

下载文档原格式

线性代数第一章第二节

四、作业 P35 1(3) 2(4) 4 8(3) 12(1)(3)
思考题[*]
x
已知
1
1
2
1 f x 3 1
3
x 1 1 2 x 1 1 2x 1
求 x 的系数.
思考题解答
解含 x 3 的项有两项,即
x 1 f x 3 1
对应于
t
1
1
2
x 1 1 2 x 1 1 2x 1
2. a14 a21a33 a44不是四阶行列式中的项，a12 a43a31a24是四阶行列式中的项. a12 a43a31a24 a12 a24 a31a43
1t 2413 a12a24 a31a43a 13 a12a24 a31a43 a12a24 a31a43
t(53412) = 0+1+1+3+3=8 定理 2 n个自然数共有n!个n元排列，其中奇偶排列各占一半。
二、n 阶行列式的定义
三阶行列式定义为
a 11 a 21 a 31
a 12 a 22 a 32
a 13 a 23 a 33
123 231 312 132 213 321 t(123)=0 t(231)=2 t(312)=2 t(132)=1 t(213)=1 t(321)=3
例 3 三阶行列式
例4 四阶行列式
1 2 3
12 3
3 4
例5 n 阶行列式
1 2
12 34
1 2

(1)
n( n 1 ) 2
12 n
n
a 11 a 21 an1
a 12 a 22 an 2
... a 1 n ... a 2 n t ( j1 j2 ......jn ) a1 j1 a2 j2 ......anj n (1) ... a nn

线性代数第一节排列及其逆序数

第一章行列式第一节排列及其逆序数�引言�排列与逆序数一、引言我们在中学曾经学习过求解二元一次线性方程组⎩⎨⎧=+=+2221212111c x b x a c x b x a （1）当两个方程的未知数系数不成比例，即 2121b b a a ≠时，我们有.b a b ac a c a x ,b a b ac b c b x 122112212122121121−−=−−=（2）为方便记忆，我们引入二阶行列式bc ad db ca −=（3）则（2）可以表示为.b a b ac a c a x ,b a b a b c b c x 221122112221122111==（4）即当（1）的系数行列式0b a b a 2211≠时，（1）的解可以用二阶行列式表示为（4）。

用高斯消元法，对三元一次线性方程组,333323213123232221211313212111⎪⎩⎪⎨⎧=++=++=++b x a x a x a b x a x a x a b x a x a x a （5）我们也可以得到类似的结果。

即如果引入三阶行列式,c c c c c c c c c c c c c c c c c c c c c c c c c c c 322311332112312213322113312312332211333231232221131211−−−++=（6）则当（5）的系数行列式0a a a a a a a a a D 333231232221131211≠=（7）时，方程组（5）的解可以用三阶行列式表示为.a a a a a a a a a b a a b a a b a a x ,a a a a a a a a a a b a a b a a b a x ,a a a a a a a a a a a b a a b a a b x 333231232221131211332312222111211333323123222113121133331232211311123332312322211312113332323222131211===（8）对于n 元一次方程组，是否也有类似于上述（4）、（8）的结果呢？这就是本章要回答的问题。

1-2线性代数

n( n 1 ) , = 2 时为偶排列；当 n = 4k ,4k + 1 时为偶排列；
t = ( n 1) + ( n 2 ) + L + 2 + 1
时为奇排列. 当 n = 4k + 2,4k + 3 时为奇排列
(4) (2k )1(2k 1)2(2k 2)3(2k 3)L (k + 1)k
于是排列32514的逆序数为 t = 0 + 1 + 0 + 3 + 1 = 5. 的逆序数为于是排列
计算下列排列的逆序数，并讨论它们的奇偶性. 例2 计算下列排列的逆序数，并讨论它们的奇偶性
(1)
4132
(2) 3712456
（2））
解（1）4 1 3 2 ）
3 7 1 2 4 5 6
0 0 2 2 1 1 1
第二节全排列及其逆序数
一、排列
定义由自然数 2, , n 组成的不重复的每一由自然数1, 种有确定次序的排列, 称为一个n 种有确定次序的排列称为一个阶排列 (简称排列简称排列). 简称排列都是4 例如 1234 和4312都是阶排列都是阶排列, 24315是一个阶排列是一个5 阶排列. 是一个
t = 0 +0 + 2 + 2 + 1 + 1 + 1
0 1 1 2
t = 0+1+1+ 2 = 4
此排列为偶排列此排列为偶排列. 偶排列
=7
此排列为奇排列此排列为奇排列. 奇排列
(3)
解
n(n 1)(n 2 )L 321
n 6444 74444 4 1 8 n(n 1)2 2 )L 321 1 4(n443 44 4 (n 2)

线性代数(同济六版)知识点总结

1. 二阶行列式--------对角线法则 : |a 11 a 12a 21a 22|= a 11a 22 −a 12a 212. 三阶行列式 ①对角线法则②按行（列）展开法则3. 全排列：n 个不同的元素排成一列。

所有排列的种数用P n 表示， P n = n ！逆序数：对于排列p 1 p 2… p n ，如果排在元素p i 前面，且比p i 大的元素个数有t i 个，则p i 这个元素的逆序数为t i 。

整个排列的逆序数就是所有元素的逆序数之和。

奇排列：逆序数为奇数的排列。

偶排列：逆序数为偶数的排列。

n 个元素的所有排列中，奇偶各占一半，即n!2对换：一个排列中的任意两个元素对换，排列改变奇偶性. 4.其中：j 1j 2j 3 是1,2,3的一个排列，t(j 1j 2j 3)是排列 j 1j 2j 3 的逆序数5.下三角行列式: 副三角跟副对角相识对角行列式：副对角行列式：6. 行列式的性质： ①行列式与它的转置行列式相等. （转置：行变列，列变行）。

D = D T ②互换行列式的两行（列），行列式变号。

推论：两行（列）相同的行列式值为零。

互换两行：r i ↔ r j ③行列式的某一行（列）中的所有元素都乘以同一个数k ，等于用数 k 乘此行列式。

第i 行乘k ：r i x k 推论：行列式中某一行（列）的公因子可以提到行列式符号外面 ④行列式中如果有两行（列）元素成比例，则此行列式等于0⑤若行列式的某一列（行）的元素都是两个元素和，则此行列式等于两个行列式之和。

如：⑥把行列式的某行（列）的各元素同一倍数后加到另一行（列）的对应元素上去，行列式的值不变。

如第j 列的k 倍加到第i 列上：c i +kc j333231232221131211a a a a a a a a a 3221312312332211a a a a a a a a a 13++=312213332112322311a a a a a a a a a ---32132123312322211312113j 2j 1j )j j t (j 33a a a a a a a a a a a a 1)(∑-=n n 2211n n n 2n 1222111...a a a a ...a a 0a a a = n...λλλλλλ21n 21= n21λλλn2121)n(n λλλ1)( --=n n n j n jn 2n 12n 2j 2j 22211n 1j 1j 1211a )c (b a a a )c (b a a a )c (b a a+++n n n j n 2n 12n2j 22211n 1j 1211n n n j n 2n 12n 2j 22211n 1j 1211a c a a a c a a a c a a a b a a a b a a a b a a +=n n n j n j n in 12n 2j 2j 2i 211n 1j 1j 1i 11a a ka a a a a ka a a a a ka a a+++n nn j n i n 12n2j 2i 211n 1j 1i 11a a a a a a a a a a a a =7. 重要性质：利用行列式的性质 r i +kr j 或 c i +kc j ，可以把行列式化为上（下）三角行列式，从而计算n 阶行列式的值。

线性代数知识点总结

奇排列：逆序数为奇数的排列。偶排列：逆序数为偶数的排列。n 个元素的所有排列中，奇偶各占一半，即n!
2
对换：一个排列中的任意两个元素对换，排列改变奇偶性.
4. a a a
11
12
13
(1) a a a
21
22
23
a a a t(j1j2 3j )
1j1 2j2 3j3
a a a 31
23
33
其中：j1j2j3 是 1,2,3 的一个排列， t(j1j2j3)是排列 j1j2j3 的逆序数
5. 下三角行列式:
a11
a21 a22
0 a 1a1 22...a nn
副三角跟副对角相识
an1 an2 ... ann
对角行列式：
副对角行列式：
λ1
λ2
λ1λ2...λn
λ2
λ1
n(n 1)
(1)
2
λλ λ
12
n
λn
λn
6. 行列式的性质：
①行列式与它的转置行列式相等. （转置：行变列，列变行）。D = DT
aaa 11 23 32
aaa 12 21 33
a a a 13 22 31
3. 全排列：n 个不同的元素排成一列。
所有排列的种数用Pn 表示， Pn = n！逆序数：对于排列p1 p2… pn，如果排在元素pi前面，且比pi大的元素个数有ti个，则pi这个元素的逆序数为ti。
整个排列的逆序数就是所有元素的逆序数之和。
通过性质化为 0，则 D = aij Aij
9. 利用 Cramer 法则求解 n 个 n 元线性方程组：
①若非齐次线性方程组的系数行列式不等于零，则方程组有唯一解。等于 0，则无解

线性代数 1.1 全排列及其逆序数

三、排列的奇偶性
逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 定义把排列中两个元素位置进行对调，称为对排列作一次对换。定理：对换改变排列的奇偶性. 证明：先证明是相邻对换的情况，再证非相邻对换的情况。推论将奇（偶）排列变成标准排列需用奇（偶）数次对换。
第一章
行列式
§1.1 全排列及其对换
一、全排列的定义 n 个不同的元素排成一列，叫做这 n
个元素的全排列，简称排列。例 123456 是 6 个数的全排列， 53421 是 5 个数的全排列。
二排列的逆序数
对于n 个不同的元素，规定各元素之间由小到大为标准次序. 定义当某两个元素的先后次序与标准次序不同时，就说有一个逆序，一个排列中所有逆序的总数叫做这个排列的逆序数。求逆序数的方法： t ( p1 p2 pn ) t1 t2 tn 其中 ti 是排列中与元素 pi 相关的逆序数，即位于 pi前且比 pi 大的的元素个数。
例 (1) 求排列3412中逆序数 .
2 nn 1n 2 321
(1) t (3412) 0 0 2 2 4; 解：
(2) t (n n 1 n 2 321) 0 1 2 (n 1) 1 n(n 1) 2

线性代数-全排列及其逆序数

§2 全排列及其逆序数
引例用1、2、3三个数字，可以组成多少个没有重复数字的三位数？
解
123
百位 1 十位 1 2 个位 1 2 3
2
3
3种放法
13
2种放法 1种放法
共有 3 2 1 6 种放法.
问题把 n 个不同的元素排成一列，共有多少种不同的排法？
定义把 n 个不同的元素排成一列，叫做这 n 个元素的全排列. n 个不同元素的所有排列的种数，通常用 Pn 表示.
t(32514) 0 1 0 3 1 5
练习：求排列 453162 的逆序数.
解： t 9
并规定由小到大为标准次序.
先看有多少个比 p1 大的数排在 p1 前面，记为 t1 ；再看有多少个比 p2大的数排在 p2前面，记为 t2 ;
……
最后看有多少个比 pn大的数排在 pn前面，记为 tn;
则此排列的逆序数为 t t1 t2 tn
例1：解：
求排列 32514 的逆序数.
对于n 个不同的元素，可规定各元素之间的标准次序. n 个不同的自然数，规定从小到大为标准次序.
定义当某两个元素的先后次序与标准次序不同时，就称这两个元素组成一个逆序.
例如在排列32514中，逆序
32514 逆序逆序思考题：还能找到其它逆序吗？答：2和1，3和1也构成逆序.
定义排列中所有逆序的总数称为此排列的逆序数.
显然 Pn n (n 1) (n 2) 3 2 1 n!
即n 个不同的元素一共有n! 种不同的排法.
Hale Waihona Puke 3个不同的元素一共有3! =6种不同的排法
123，132，213，231，312，321

线性代数1.2全排列与逆序数

的奇偶性， .
而标准排列是
0 )，因此知推论成立
推论2：n元排列中（n>1,n！个排列）奇排列偶排列各占一半。
计算排列的逆序数的方
法 :
设 p 1 p 2 p n 为 n 个自然数的一个排列，
考虑元素 p i ( i 1、、 n )， 2 p i 前面的元素有 t i 个，
如果比 p i大的且排在
就是说 pi 这个元素的逆序数为t i .
全体元素的逆序数即是这个排列的逆序数之和 . t t1 t 2 t n
n 个不同元素的所有排列
的种数，通常用
Pn 表示 .
Pn n ( n 1) 3 2 1 n!
例1 求排列32514的逆序数. 解在排列32514中， 3排在首位，逆序数为 0； 2前面比2大的数有一个（3），故逆序数为1； 5是最大数，逆序数为 0； 1前面比1大的数有三个（3、2、5）,故逆序数为3； 4前面比4大的数有一个（5），故逆序数为1；于是这个排列的逆序数为 ( 32514 ) 0 1 0 3 1 5 .
解
n 1 n ( n 1 )( n 2 ) 321 n 2

t ( n 1) ( n 2 ) 2 1
n( n 1) 2
,
当 n 4k ,
4 k 1时为偶排列，
4 k 3时为奇排列 .
ti ,
i1
n
例2 计算下列排列的逆序数，并讨论它们的奇偶性.
(1 ) 217986354 ;
解
2 1 7 9 8 6 3 5 4
0 1 0 0 1 3 4 4 5
t ( 217986354 )

§2 全排列及其逆序数

逆序
例如排列32514 中，排列
3 2 5 1 4
逆序逆序
2. 一个排列中所有逆序的总数称为此排列的逆序数. 一个排列中所有逆序的总数称为此排列的逆序数逆序数. 例如: 其逆序数为5. 例如排列 32514 , 其逆序数为其逆序数为4. 排列 31524 , 其逆序数为 3. 排列的奇偶性逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列; 奇排列逆序数为偶数的排列称为偶排列逆序数为偶数的排列称为偶排列. 偶排列
4.计算排列逆序数的方法计算排列逆序数的方法设排列为 p1 p2 L pn , t i 为 pi 构成的逆序数则其逆序数为 t = t ( p1 p2 L pn ) = t1 + t 2 + Lt n−1 计算下列排列的逆序数,并讨论它们的奇偶性并讨论它们的奇偶性. 例计算下列排列的逆序数,并讨论它们的奇偶性.
二、排列的逆序数
规定各元素之间有一个标准次序, 规定各元素之间有一个标准次序 n 个不同的自然数, 规定由小到大为标准次序标准次序. 然数 …pt…ps…pn中, 若数 pt >ps, 则称这两个数组成一个逆序逆序. 则称这两个数组成一个逆序 (即：大的数在小的数左边, 则这两数构成一个逆序）即大的数在小的数左边则这两数构成一个逆序）
(1) 217986354 ( 2) n( n − 1)( n − 2)L 321
四、小结
1. n个不同的元素的所有排列总数为个不同的元素的所有排列总数为n!. 个不同的元素的所有排列总数为 2. 排列具有奇偶性排列具有奇偶性. 3. 计算排列逆序数. 计算排列逆序数
§2 全排列及其逆序数
一、全排列二、排列逆序数三、小结

全排列及其逆序数

下页
标准排列在n个自然数的全排列中排列123 ⋅ ⋅ ⋅ n称为标准排列. 逆序与逆序数在一个排列中, 如果某两个元素的先后次序与标准排列的次序不同, 就说有1个逆序. 一个排列中所有逆序的总数叫做这个排列的逆序数.
提示: 以下我们只讨论n个自然数的全排列.
下页
标准排列在n个自然数的全排列中排列123 ⋅ ⋅ ⋅ n称为标准排列. 逆序与逆序数在一个排列中, 如果某两个元素的先后次序与标准排列的次序不同, 就说有1个逆序. 一个排列中所有逆序的总数叫做这个排列的逆序数. 逆序数的计算在排列p1p2⋅ ⋅ ⋅pn中, 如果pi的前面有ti个大于pi的数, 就说元素pi的逆序数是ti. 排列的逆序数为t=t1+t2+ ⋅ ⋅ ⋅ +tn. 举例: 在排列32514中, t1=0, t2=1, t3=0, t4=3, t5=1. 排列32514的逆序数为t=0+1+0+3+1=5. 标准排列12345的逆序数是多少字, 可以组成多少个没有重复数字的三位数？解采用先选定百位数, 再选定十位数, 最后选定个位数的步骤. 百位数有3种选法, 十位数有2种选法, 个位数有1种选法. 因为3×2×1=6, 所以可以组成6个没有重复数字的三位数. 这6个三位数是 123, 132, 213, 231, 312, 321.
下页
标准排列在n个自然数的全排列中排列123 ⋅ ⋅ ⋅ n称为标准排列. 逆序与逆序数在一个排列中, 如果某两个元素的先后次序与标准排列的次序不同, 就说有1个逆序. 一个排列中所有逆序的总数叫做这个排列的逆序数. 奇排列与偶排列逆序数为奇数的排列叫做奇排列, 逆序数为偶数的排列叫做偶排列. 举例: 排列32514的逆序数是5, 它是奇排列. 标准排列12345的逆序数是0, 它是偶排列.

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

逆序
定义: 一个排列中所有逆序的总数称为此排列的逆序数.
例如: 排列32514 中, 0 0
1
3 2 5 1 4
1 逆序数为3
故此排列的逆序数为: 3+1+0+1+0 = 0+1+0+3+1 = 5. 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 计算排列逆序数的方法方法1: 分别计算出排在1,2, ·, n 前面比它大的数 · · 码的个数并求和, 即先分别算出 1,2, ·, n 这 n 个元素 · · 的逆序数, 则所有元素的逆序数的总和即为所求排列的逆序数.
§1.2 全排列及其逆序数一、全排列
引例: 用1, 2, 3三个数字, 可以组成多少个没有重复数字的三位数？这是一个大家熟知的问题, 答案是: 3! = 6. 将此问题推广: 把n个不同的元素按先后次序排成一列, 共有多少种不同的排法. 定义: 把 n 个不同的元素排成一列, 叫做这 n 个元素的全排列(或排列). n 个不同的元素的所有排列的种数, 通常用 Pn 表示, 称为排列数. Pn = n (n–1) (n–2) · 2 1 = n! · ·
三、小结
1. n个不同的元素的所有排பைடு நூலகம்种数为n!个; 2. 排列具有奇偶性; 3. 计算排列逆序数常用的方法有两种.
例2: 计算下列排列的逆序数, 并讨论其奇偶性. (1) 217986354. 解: 2 1 7 9 8 6 3 5 4 0 1 001 34 4 5 于是排列217986354的逆序数为: t = 0+1+0+0+1+3+4+4+5 = 18. 此排列为偶排列. (2) n(n–1)(n–2) · 21 · · · · 解: n (n–1) (n–2) · 2 1 2 (n–2) (n–1) 0 1 于是排列n(n–1)(n–2) · 21的逆序数为: · · nn 1 , t = 0+1+2+ · +(n–2)+(n–1) · · 2
方法2: 依次计算出排列中每个元素前面比它大的数码个数并求和, 即算出排列中每个元素的逆序数, 则所有元素的逆序数之总和即为所求排列的逆序数. 例1: 求排列32514的逆序数.
解: 在排列32514中, 3排在首位, 则3的逆序为0; 2的前面比2大的数只有一个3, 故2的逆序为1; 5的前面没有比5大的数, 故其逆序为0; 1的前面比1大的数有3 个, 故其逆序为3; 4的前面比4大的数有1个, 故逆序为1. 即 3 2 5 1 4 0 1 0 3 1 于是排列32514的逆序数为 t = 0+1+0+3+1 = 5.
二、排列的逆序数
我们规定各元素之间有一个标准次序. 以 n 个不同的自然数为例, 规定由小到大为标准次序. 定义: 在一个排列 i1 i2 · is · it · in 中, 若数 is>it, · · · · · · 则称这两个数组成一个逆序.
例如: 排列32514 中, 逆序
3 2 5 1 4 逆序
此排列当 n=4k, 4k+1 时为偶排列; 当 n=4k+2, 4k+3 时为奇排列. (3) (2k)1(2k–1)2(2k–2)3(2k–3) · (k–1)(k +1)k. · · · · 解: (2k) 1 (2k–1) 2 (2k–2) 3 (2k–3) · (k–1) (k+1) k (k–1) (k–1) k 3 0 1 1 2 2 3 于是排列(2k)1(2k–1)2(2k–2) · (k–1)(k +1)k的逆序数为: · · t = 0+1+1+2+2+ · +(k–1)+(k–1)+k · · k k 1 2 k k2. 2 此排列当 k 为偶数时为偶排列, 当 k为奇数时为奇排列.