Arrangement
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
are the Stirling numbers 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" .
References
[1] | A.V. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian) |
[2] | J. Riordan, "An introduction to combinational analysis" , Wiley (1958) |
Comments
References
[a1] | L. Comtet, "Advanced combinatorics" , Reidel (1977) (Translated from French) |
Arrangement. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Arrangement&oldid=45224