preface

Hello! Friend!!!

Thank you very much for reading haihong’s article, if there are any mistakes in the article, please point out ~

Self-introduction ଘ(੭, ᵕ)੭

Nickname: Haihong

Tag: programmer monkey | C++ contestant | student

Introduction: because of C language to get acquainted with programming, then transferred to the computer major, had the honor to get some national awards, provincial awards… Has been confirmed. Currently learning C++/Linux/Python

Learning experience: solid foundation + more notes + more code + more thinking + learn English well!

Machine learning little White stage

The article is only used as my own study notes for the establishment of knowledge system and review

Know what is, know why!

Second and third order determinants

Second order determinant

Write for


∣ a 11 a 12 a 21 a 22 ∣ = a 11 ∗ a 22 – a 12 ∗ a 21 \begin{vmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{vmatrix}=a_{11}*a_{22}-a_{12}*a_{21}

define

The difference obtained from the product of two elements on the main diagonal minus the product of two elements on the vice diagonal is: A11 ∗a22− A12 ∗a21a_{11}* A_ {22}-a_{12}* A_ {21}a11∗a22− A12 ∗a21

Note: The determinant is essentially a number, for example: ∣1234∣ begin{vmatrix} 1&2 \\ 3&4end {vmatrix} | ∣∣∣∣1324 | ∣∣∣

For example,


∣ 3 – 2 2 1 ∣ = ? \begin{vmatrix} 3&-2 \\ 2&1 \end{vmatrix} =?

A:


∣ 3 – 2 2 1 ∣ = 3 ∗ 1 – ( – 2 ) ∗ 2 = 3 – ( – 4 ) = 7 \begin{vmatrix} 3 & -2\\ 2 & 1 \end{vmatrix}=3*1-(-2)*2=3-(-4)=7

Third order determinant

Write for


∣ a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 ∣ = a 11 ∗ a 22 ∗ a 33 + a 12 ∗ a 23 ∗ a 31 + a 13 ∗ a 21 ∗ a 32 – a 11 ∗ a 23 ∗ a 32 – a 12 ∗ a 21 ∗ a 33 – a 13 ∗ a 22 ∗ a 31 \begin{vmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{vmatrix}=a_{11}*a_{22}*a_{33}+a_{12}*a_{23}*a_{31}+a_{13}*a_{21}*a_{32}-a_{11}*a_{23}*a_{32}-a_{12}*a_{21}*a_{33}-a _{13}*a_{22}*a_{31}

For example,


∣ 1 2 – 4 – 2 2 1 – 3 4 – 2 ∣ = ? \ begin {vmatrix} \ \ 1 & 2 & – 4-2 & 2 & 1 \ \ 2-3 & 4 & – \ \ \ end {vmatrix} =?

A:


∣ 1 2 – 4 – 2 2 1 – 3 4 – 2 ∣ = 1 ∗ 2 ∗ ( – 2 ) + 2 ∗ 1 ∗ ( – 3 ) + ( – 4 ) ∗ ( – 2 ) ∗ 4 – 1 ∗ 1 ∗ 4 – 2 ∗ ( – 2 ) ∗ ( – 2 ) – ( – 4 ) ∗ 2 ∗ ( – 3 ) = – 14 \begin{vmatrix} 1 & 2 & -4\\ -2 & 2 & 1\\ -3 & 4 & -2 \end{vmatrix}=1*2*(-2)+2*1*(-3)+(-4)*(-2)*4-1*1*4-2*(-2)*(-2)-(-4)*2*(-3)=-14

Total permutation and the number of inversions

The whole arrangement

define

Taking any m (m≤ N) elements from n different elements and arranging them in a certain order is called taking a permutation of M elements from N different elements.

All permutations when m is equal to n are called complete permutations.

The formula

The total permutation f(n)=n! (define 0! = 1)

For example,

How many three-digit numbers can be composed of 1, 2, and 3 without repeated digits?

Answer: 3×2×1=6.

If we put the hundreds place, we have three possibilities, then we put the tens place, we have two possibilities, and then we put the ones place, we only have one possibility.

So for 3 * 2 * 1 = 6

As can be seen from the above example:

When I have n different numbers arranged

The first position has (n) choices, the second position has (n-1) choices… N *(n-1)(n-2)… 21 possibilities, which is n factorial. Kinds of arrangement.

We use PnP_{n}Pn to represent the number of all permutations of n different elements, then


P n = n ∗ ( n – 1 ) ∗ ( n – 2 ) ∗ . . . ∗ 3 ∗ 2 ∗ 1 = n ! P_n=n*(n-1)*(n-2)*… *3*2*1=n!

Reverse order number

concept

  • Standard order: n different numbers, we can specify from smallest to largest as the standard order
  • Reverse order: reverse the standard order (for example, if two elements are ordered from largest to smallest, it is considered reverse order)
  • Permutation inversions: The total number of inversions in a permutation

A method for calculating the number of inversions of permutations

N elements (1,2,3… N -1,n), specifying the standard order from smallest to largest

Set p1p2… pnp_1p_2… p_np1p2… Pn is a permutation of n elements. For elements pip_ipi(I =1,2… ,n), if there are tit_iti before pip_ipi, then pip_ipi is said to have tit_iti inversions.

The sum of the inversions of all the elements is t, then


t = t 2 + t 2 + . . . + t n = ∑ t = 1 n t i t=t_2+t_2+… +t_n=\sum_{t=1}^nt_i

It’s the number of inversions of this permutation.

For example,

Find the number of inversions of permutation 32514

Answer: 3 is the first digit. There is no number before it. The reverse number is 0

2 is in the second place, and one of the first numbers, 3, is greater than 2, so the reverse is 1

5 can’t be preceded by anything greater than 5, so the reverse order is 0

The number before 1 is greater than 1:3, 2, 5, so the reverse number is 3

There’s only 5 before 4, so the number of inversions is 1

To sum up, the number of inversions of this arrangement t=0+1+0+3+1=5

Added concept

  • Flush arrangement: a arrangement with an odd number of inversions
  • Even permutation: a permutation with an even number of inversions

conclusion

The essay is just a study note, recording a process from 0 to 1

Hope to help you, if there is a mistake welcome small partners to correct ~

If the mathematical formula in the text is not correct, click here to view it

I am haihong ଘ(੭, ᵕ)੭

If you think it’s ok, please give it a thumbs up

Thanks for your support ❤️