排列组合 离散数学

排列组 (Permutation Group)

Let, X be a non-empty set. A permutation of X is a one-one function from X onto X. A group (G,*) is called a permutation group on a non-empty set X if the elements of G are a permutation of X and the operation * is the composition of two functions.

令X为非空集。 X的排列是从X到X的一一函数。 如果G的元素是X的置换并且运算*是两个函数的组合，则组(G，*)称为非空集X上的置换组。

For instance ro = 1 2 3 4 denotes the permutation on the four 2 1 4 3 symbols { 1, 2, 3, 4} which maps 1 on 2, 2 on 1, 3 on 4 and 4 on 3. This is the permutation corresponding to the symmetry of the square which is a reflection along the vertical bisector.

例如RO = 1 2 3 4表示的四个2 1 4 3个符号{1，2，3，4}其中2映射1，2合1，3 3 4和4的排列。 这是对应于正方形对称性的排列，该对称性是沿垂直平分线的反射。

Clearly, the order of the column in the symbol is immaterial so long as the corresponding elements above and below in that column remain unchanged. The number of elements of a finite set is the degree of the permutation.

显然，符号中该列的顺序并不重要，只要该列中上方和下方的相应元素保持不变即可。 有限集的元素数量是排列的程度。

Equality of two permutation

两个置换相等

Let, f and g be two permutation on a X. Then f = g if only if f(x) = g(x) for all x in X.

设f和g是X上的两个置换。 则f = g仅仅当f(x)= G(X)为X所有的x。

Example: Let, f and g be given by:

示例：令f和g给出：

f = 1 2 3 4         g = 3 2 1 4    2 3 4 1             4 3 2 1    Evidently f(1) = 2 = g(1), f(2) = 3 = g(2)    f(3) = 4 = g(3), f(4) = 1 = g(4)    Thus, f(x)  = g(x) for all x E {1, 2, 3, 4} which implies f = g.

Total Number of permutation

排列总数

Let, X, is a set consisting of n distinct elements. Then the elements of X can be permitted in n! different ways. If Sn be the set consisting of all permutation of degree n then the set Sn will have n! different permutation of degree n. This set Sn is called the symmetric set of permutation of degree n.

令X是由n个不同元素组成的集合。 那么X的元素可以在n中被允许！ 不同的方式。 如果Sn是由度n的所有排列组成的集合，则集合Sn将具有n！ n次的不同排列。 该集合Sn被称为度数n的排列的对称集合。

排列类型 (Types of permutation)

1. Identity permutation

1.身份置换

If each element of permutation is replaced by itself then it is known as the identity permutation and is denoted by the symbol I.

如果置换的每个元素都被自身替换，则称为身份置换，并用符号I表示。

I = a  b  c    a  b  c  is an identity permutation

2. Product of permutation

2.排列积

A permutation is one- one onto the map and hence it is invertible, i.e. every permutation f on a set P ={ a1, a2, ..., an} has a unique inverse permutation denoted by f^-1.

置换在映射上是一对一的，因此它是可逆的，即，集合P = {a1，a2，...，an}上的每个置换f都有一个由f ^ -1表示的唯一逆置换。

Thus if

因此，如果

f =     a1      a2 ......an            b1      b2 ......bn    then    f^-1 =  b1      b2 ......bn            a1      a2 ......an

3. Cyclic permutation

3.循环排列

A permutation which replaces n objects cyclically is called cyclic permutation of degree n.

循环替换n个对象的置换称为度n的循环置换。

Consider the permutation p = 1 2 3 4 this assignment of 2 3 4 1 values could be presented.

考虑置换p = 1 2 3 4 ，可以表示2 3 4 1值的分配。

The number of elements permuted by a cycle is said to be its length and disjoint cycles are those which have no common elements. A cycle of length 1 means that the image of an element is the element itself and represents identity permutation.

循环排列的元素数量被称为其长度，而不相交的循环则是没有共同元素的元素。 长度为1的循环表示元素的图像是元素本身，并表示标识置换。

4. Transposition

4.换位

A cyclic permutation such (a, b) which interchanges the symbol leaving all other unchanged is called transposition. In other words, transposition is a cycle of length two of the form (a, b) i.e. it is a mapping which maps each object onto itself expecting two, each of which is mapped on the other. For example (1, 2) is a transposition.

交换符号而使所有其他符号保持不变的循环置换(a，b)称为转置。 换句话说，换位是形式为(a，b)的长度为2的循环，即，它是一个映射，将每个对象映射到其本身，并期望两个对象相互映射。 例如(1，2)是一个换位。

5. Even and odd permutation

5.偶数和奇数排列

When a permutation is expressed as a product of even or odd number of transpositions then the permutation is called as even or odd permutation.

当排列表示为偶数或奇数个换位的乘积时，则将该排列称为偶数或奇数排列。

翻译自:

排列组合 离散数学