avatar

OI数学专题笔记 - 1

OI数学专题笔记 - 1

排列和逆序对

定义

  • 以任意一种顺序将相异的 nn 个数重排,每个顺序都称作一个排列。

  • 在排列 a1a2..ana_1 a_2 .. a_n 中,如果每有一个二元组 (i,j)(i, j) 满足 i<ji < jai>aja_i > a_j ,则称 ai,aja_i, a_j 组成了一个逆序对。

  • 排列 a1a2...ana_1 a_2 ... a_n 的逆序数表示为 τ(a1a2...an)\tau(a_1 a_2 ... a_n)

  • 定义:如果一个排列的逆序数为偶数,则称此排列为偶排列,否则称为奇排列。

  • 定义:在一个排列中,对换其中某两个数,其余的数不动,得到另一个排列,这种操作称为一个对换。

定理

  • 对换改变排列的奇偶性。

证明:
对于排列 aiai+1...aj1aja_i a_{i+1} ... a_{j-1} a_jaia_iai+1a_{i+1} 对换时,逆序对一定增加或者减少一个,所以将 aia_iaja_j 调换可以视作:将 aia_i 逐位对换到 aja_j 的位置,易得到排列变为 ai+1...aj1ajaia_{i+1} ... a_{j-1} a_j a_i 所需要的操作数为 jij - i ;再将 aja_j 逐位对换到 aia_i 原先的位置,由于 aja_j 移动的位置显然比 aia_i 移动的位置少一个,易得到排列变为 ajai+1...aj1aia_j a_{i+1} ... a_{j-1} a_i 所需要的操作数为 ji1j - i - 1。由于每次相邻的元素对换均会改变排列的奇偶性,而相邻元素总对换数为 2j2i12j -2i -1,这显然是个奇数,所以对换会改变排列的奇偶性。

  • 在全部 nn 阶排列中,奇偶排列各占一半。

证明;
对于任意一个排列,通过对换可以改变排列的奇偶性,也就是实现奇排列与偶排列的双射,所以奇偶排列数量一样,各占一半。

  • 定理:任意一个排列可以经过一系列对换操作变成自然排列,并且所做对换操作次数的奇偶性与这个排列的奇偶性相同。

行列式

定义

  • N阶行列式是由 N2N^2 个数 aij(i,j=1,2,...,n)a_{ij}(i, j = 1, 2, ... , n) 通过下式确定的一个数

a11a12...a1na21a22...a2n............an1an2..ann=Σj1j2...jnsgn(j1j2...jn)a1j1a2j2...anjn\left | \begin{array}{cccc} a_{1 1} & a_{1 2} & ... & a_{1 n} \\ a_{2 1} & a_{2 2} & ... & a_{2 n} \\ ... & ... & ... & ... \\ a_{n 1} & a_{n 2} & .. & a_{n n} \end{array} \right | = \Sigma_{j_1j_2...j_n}sgn(j_1j_2...j_n)a_{1j_1}a_{2j_2}...a_{nj_n}

  • 也称为行列式的完全展开式。

其中 Σj1j2...jn\Sigma_{j_1j_2...j_n}表示枚举 1 到 n 的每一种排列对后面的式子进行求和, sgnsgn 函数是符号函数。

a1j1a1j2...anjna_{1j_1}a_{1j_2}...a_{nj_n} 表示从每行取出一个数乘起来,由于排列 j1j2...jnj_1j_2...j_n 是没有重复的,所以这里也是从每一行每一列取一个数乘起来。

  • sgn(j1j2...jn)=(1)τ(j1j2...jn)={1  j1j2...jn1  j1j2...jnsgn(j_1j_2...j_n) = (-1)^{\tau(j_1j_2...j_n)} = \begin{cases} 1 \quad \ \ & j_1j_2...j_n是偶排列 \\ ​ -1 \quad \ \ & j_1j_2...j_n是奇排列 \end{cases}

引理

  1. 行列互换,值不变。

  2. 用一个数乘行列式的某行等于这个数乘此行列式。

  3. 如果行列式中某一行是两组数之和,则这个行列式等于两个行列式之和,这两个行列式分别以这两组数为该行,而其余各行与原行列式对应各行相同。

  4. 对换行列式中两行的位置,行列式反号。

  5. 如果行列式中有两行成比例,则行列式等于0。

  6. 把一行的某个倍数加到另一行,行列式的值不变。

矩阵

定义

  • mnmn 个数排成 mmnn 列矩形的数表

[a11a12a1na21a22a2nam1am2amn]\begin{bmatrix} a_{1 1} && a_{1 2} && \cdots && a_{1 n} \\ a_{2 1} && a_{2 2} && \cdots && a_{2 n} \\ \vdots && \vdots && \ddots && \vdots \\ a_{m 1} && a_{m 2} && \cdots && a_{m n} \end{bmatrix}

  • 称为一个 m×nm \times n 的矩阵,记做 A ,其中 aija_{i j} 称为第 ii 行第 jj 列的元素。

特殊矩阵种类

  • 零矩阵 0:所有位置都为零的矩阵。
  • 对角矩阵:只有左上到右下的对角线上的数非零的矩阵。
  • 单位矩阵 I:特殊的对角矩阵,对角线上的数均为1。
  • 纯量矩阵:A=diag(c,c,...,c)A = diag(c,c,...,c)
  • 上三角矩阵
  • 下三角矩阵
  • 对称矩阵
  • 反对称矩阵

运算

  • 矩阵的相等:大小一样,每个位置都一样。

  • 矩阵的加法;将两个矩阵对应位置相加,需保证两个矩阵大小一样。

  • 矩阵的数量乘法:用一个数乘一个矩阵等于用这个数乘矩阵每一个数。

  • 矩阵乘法:

条件:第一个矩阵的列数等于第二个矩阵的行数。

得到的矩阵的行数等于第一个矩阵的行数,列数等于第二个矩阵的列数。

计算得到的矩阵第 ii 行第 jj 列的方法为取出第一个矩阵的第 ii 行与第二个矩阵的第 jj 列对应位置相乘再求和。

矩阵乘法的性质

  • 0A = 0, A0 = 0
  • IA = A, AI = A
  • A(BC) = (AB)C
  • A(B + C) = AB + AC
  • (B + C)A = BA + CA
文章作者: Ender
文章链接: https://www.ender.xin/post/a0fbcc60.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论