From Encyclopedia of Mathematics
Revision as of 17:20, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

with repetitions of out of elements

A finite sequence of elements from some set . If all the term of are distinct, then is called an arrangement without repetitions. The number of arrangements of out of elements with repetitions is , and that without repetitions in .

An arrangement can be regarded as a function given on and taking values in : , . The elements of are usually called cells (or urns), while those of are called particles (or balls); defines the filling of the various cells by the various particles. If one speaks of indistinguishable particles or cells, it is understood that classes of arrangements are being considered. Thus, if all the particles are indistinguishable, then two arrangements defined by functions and , respectively, belong to the same class if and only if there is a permutation of such that for all . In this case, the number of such classes, or, as it is called, the number of arrangements filling different cells by indistinguishable particles, is the number of combinations of out of elements, with repetition allowed (cf. Combination).

If one says that all the cells are indistinguishable, then one means that the arrangements are put into the classes in such a way that two arrangements, defined by functions and respectively, belong to the same class if there exists a permutation of for which for all . In this case the number of arrangements of different particles in indistinguishable cells, that is, the number of classes, is , where is the Stirling number of the second kind:

If one does not distinguish either particles or cells, then an arrangement of identical particles in identical cells is obtained; the number of such arrangements is , where is the number of additive partitions of into natural numbers. One can also consider other partitions of arrangements into classes, for example when the above-mentioned permutations and are taken from subgroups of the symmetric groups of degrees and , respectively (this and other generalizations can be found in [1], [2]). Synonyms of "arrangement" are the terms "n-permutationn-permutation" , and "ordered n-sampleordered n-sample of a population" .


[1] A.V. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2] J. Riordan, "An introduction to combinational analysis" , Wiley (1958)



[a1] L. Comtet, "Advanced combinatorics" , Reidel (1977) (Translated from French)
How to Cite This Entry:
Arrangement. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article