|
In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set , namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters. The study of permutations of finite sets is a topic in the field of combinatorics. Permutations occur, in more or less prominent ways, in almost every area of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. The number of permutations of distinct objects is factorial usually written as , which means the product of all positive integers less than or equal to . In algebra and particularly in group theory, a permutation of a set is defined as a bijection from to itself. That is, it is a function from to for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of in which each element is replaced by the corresponding . The collection of such permutations form a group called the . The key to this group's structure is the fact that the composition of two permutations (performing two given rearrangements in succession) results in another rearrangement. Permutations may ''act'' on structured objects by rearranging their components, or by certain replacements (substitutions) of symbols. In elementary combinatorics, the -permutations, or partial permutations, are the ordered arrangements of distinct elements selected from a set. When is equal to the size of the set, these are the permutations of the set. ==History== The rule to determine the number of permutations of ''n'' objects was known in Indian culture at least as early as around 1150: the Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to
Fabian Stedman in 1677 described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, ''two'' must be admitted to be varied in two ways" which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively this is an recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:
Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and horses from a stable of 20. A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations in which understanding a problem requires studying certain permutations related to it. ==Definition and one-line notation== There are two equivalent common ways of regarding permutations, sometimes called the "active" and "passive" forms, or in older terminology "substitutions" and "permutations".〔Cameron (1994) p. 29, footnote 3〕 Which form is preferable depends on the type of questions being asked in a given discipline. The "active" way to regard permutations of a set ''S'' (finite or infinite) is to define them as the bijections from ''S'' to itself. Thus, the permutations are thought of as functions which can be composed with each other, forming groups of permutations. From this viewpoint, the elements of ''S'' have no internal structure and are just labels for the objects being moved: one may refer to permutations of any set of ''n'' elements as "permutations on ''n'' letters". In Cauchy's ''two-line notation'', one lists the elements of ''S'' in the first row, and for each one its image below it in the second row. For instance, a particular permutation of the set ''S'' = can be written as: : this means that ''σ'' satisfies ''σ''(1)=2, ''σ''(2)=5, ''σ''(3)=4, ''σ''(4)=3, and ''σ''(5)=1. The elements of ''S'' may appear in any order in the first row. This permutation could also be written as: : The "passive" way to regard a permutation of the set ''S'' is an ''ordered arrangement'' (or listing, or linearly ordered arrangement, or sequence without repetition) of the elements of ''S''. This is related to the active form as follows. If there is a "natural" order for the elements of ''S'',〔The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.〕 say , then one uses this for the first row of the two-line notation: : Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as , that is, an ordered arrangement of S. Care must be taken to distinguish one-line notation from the cycle notation described later. In mathematics literature, a common usage is to omit parentheses for one-line notation, while using them for cycle notation. The one-line notation is also called the ''word representation'' of a permutation.〔 The example above would then be 2 5 4 3 1 since the natural order 1 2 3 4 5 would be assumed for the first row. (It is typical to use commas to separate these entries only if some have two or more digits.) This form is more compact, and is common in elementary combinatorics and computer science. It is especially useful in applications where the elements of ''S'' or the permutations are to be compared as larger or smaller. There are ''n''! permutations of a finite set ''S'' having ''n'' elements. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set , namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters. The study of permutations of finite sets is a topic in the field of combinatorics.Permutations occur, in more or less prominent ways, in almost every area of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science.The number of permutations of distinct objects is factorial usually written as , which means the product of all positive integers less than or equal to .In algebra and particularly in group theory, a permutation of a set is defined as a bijection from to itself. That is, it is a function from to for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of in which each element is replaced by the corresponding . The collection of such permutations form a group called the . The key to this group's structure is the fact that the composition of two permutations (performing two given rearrangements in succession) results in another rearrangement. Permutations may ''act'' on structured objects by rearranging their components, or by certain replacements (substitutions) of symbols.In elementary combinatorics, the -permutations, or partial permutations, are the ordered arrangements of distinct elements selected from a set. When is equal to the size of the set, these are the permutations of the set.==History==The rule to determine the number of permutations of ''n'' objects was known in Indian culture at least as early as around 1150: the Lilavati by the Indian mathematician Bhaskara II contains a passage that translates toThe product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.N. L. Biggs, ''The roots of combinatorics'', Historia Math. 6 (1979) 109−136Fabian Stedman in 1677 described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, ''two'' must be admitted to be varied in two ways" which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively this is an recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and horses from a stable of 20.A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations in which understanding a problem requires studying certain permutations related to it.==Definition and one-line notation== There are two equivalent common ways of regarding permutations, sometimes called the "active" and "passive" forms, or in older terminology "substitutions" and "permutations".Cameron (1994) p. 29, footnote 3 Which form is preferable depends on the type of questions being asked in a given discipline. The "active" way to regard permutations of a set ''S'' (finite or infinite) is to define them as the bijections from ''S'' to itself. Thus, the permutations are thought of as functions which can be composed with each other, forming groups of permutations. From this viewpoint, the elements of ''S'' have no internal structure and are just labels for the objects being moved: one may refer to permutations of any set of ''n'' elements as "permutations on ''n'' letters".In Cauchy's ''two-line notation'', one lists the elements of ''S'' in the first row, and for each one its image below it in the second row. For instance, a particular permutation of the set ''S'' = can be written as:: \sigma=\begin1 & 2 & 3 & 4 & 5 \\2 & 5 & 4 & 3 & 1\end;this means that ''σ'' satisfies ''σ''(1)=2, ''σ''(2)=5, ''σ''(3)=4, ''σ''(4)=3, and ''σ''(5)=1. The elements of ''S'' may appear in any order in the first row. This permutation could also be written as:: \sigma=\begin3 & 2 & 5 & 1 & 4 \\4 & 5 & 1 & 2 & 3\end.The "passive" way to regard a permutation of the set ''S'' is an ''ordered arrangement'' (or listing, or linearly ordered arrangement, or sequence without repetition) of the elements of ''S''. This is related to the active form as follows. If there is a "natural" order for the elements of ''S'',The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly. say x_1,x_2,\ldots,x_n, then one uses this for the first row of the two-line notation:: \sigma = \beginx_1 & x_2 & x_3 & \cdots & x_n \\\sigma(x_1) &\sigma(x_2) & \sigma(x_3) & \cdots& \sigma(x_n)\end.Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as \sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n), that is, an ordered arrangement of S. Care must be taken to distinguish one-line notation from the cycle notation described later. In mathematics literature, a common usage is to omit parentheses for one-line notation, while using them for cycle notation. The one-line notation is also called the ''word representation'' of a permutation. The example above would then be 2 5 4 3 1 since the natural order 1 2 3 4 5 would be assumed for the first row. (It is typical to use commas to separate these entries only if some have two or more digits.) This form is more compact, and is common in elementary combinatorics and computer science. It is especially useful in applications where the elements of ''S'' or the permutations are to be compared as larger or smaller.There are ''n''! permutations of a finite set ''S'' having ''n'' elements.」の詳細全文を読む スポンサード リンク
|