Namespaces
Variants
Actions

Difference between revisions of "Arrangement"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
''with repetitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134201.png" /> out of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134202.png" /> elements''
+
<!--
 +
a0134201.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/A013/A.0103420 Arrangement
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A finite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134203.png" /> of elements from some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134204.png" />. If all the term of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134205.png" /> are distinct, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134206.png" /> is called an arrangement without repetitions. The number of arrangements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134207.png" /> out of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134208.png" /> elements with repetitions is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a0134209.png" />, and that without repetitions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342010.png" />.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
An arrangement can be regarded as a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342011.png" /> given on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342012.png" /> and taking values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342013.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342015.png" />. The elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342016.png" /> are usually called cells (or urns), while those of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342017.png" /> are called particles (or balls); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342018.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342020.png" />, respectively, belong to the same class if and only if there is a permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342021.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342022.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342023.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342024.png" />. In this case, the number of such classes, or, as it is called, the number of arrangements filling <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342025.png" /> different cells by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342026.png" /> indistinguishable particles, is the number of combinations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342027.png" /> out of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342028.png" /> elements, with repetition allowed (cf. [[Combination|Combination]]).
+
''with repetitions of $  n $
 +
out of $  m $
 +
elements''
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342030.png" /> respectively, belong to the same class if there exists a permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342032.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342033.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342034.png" />. In this case the number of arrangements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342035.png" /> different particles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342036.png" /> indistinguishable cells, that is, the number of classes, is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342038.png" /> is the Stirling number of the second kind:
+
A finite sequence  $  \overline{a}\; = ( a _ {i _ {1}  } \dots a _ {i _ {n}  } ) $
 +
of elements from some set  $  A = \{ a _ {1} \dots a _ {m} \} $.  
 +
If all the term of  $  \overline{a}\; $
 +
are distinct, then  $  \overline{a}\; $
 +
is called an arrangement without repetitions. The number of arrangements of $  n $
 +
out of $  m $
 +
elements with repetitions is $  m  ^ {n} $,  
 +
and that without repetitions in  $  (m) _ {n} = m ( m - 1 ) \dots (m-n-1) $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342039.png" /></td> </tr></table>
+
An arrangement can be regarded as a function  $  \phi $
 +
given on  $  Z _ {n} = \{ 1 \dots n \} $
 +
and taking values in  $  A $:  
 +
$  \phi ( k ) = a _ {i _ {k}  } $,
 +
$  k = 1 \dots n $.
 +
The elements of  $  A $
 +
are usually called cells (or urns), while those of  $  Z _ {n} $
 +
are called particles (or balls); $  \phi $
 +
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  $  \phi $
 +
and  $  \psi $,
 +
respectively, belong to the same class if and only if there is a permutation  $  \sigma $
 +
of  $  Z _ {n} $
 +
such that  $  \phi ( \sigma (k) ) = \psi (k) $
 +
for all  $  k \in Z _ {n} $.  
 +
In this case, the number of such classes, or, as it is called, the number of arrangements filling  $  m $
 +
different cells by  $  n $
 +
indistinguishable particles, is the number of combinations of  $  n $
 +
out of  $  m $
 +
elements, with repetition allowed (cf. [[Combination|Combination]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342040.png" /></td> </tr></table>
+
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  $  \phi $
 +
and  $  \psi $
 +
respectively, belong to the same class if there exists a permutation  $  \tau $
 +
of  $  A $
 +
for which  $  \tau ( \phi (k) ) = \psi (k) $
 +
for all  $  k \in Z _ {n} $.
 +
In this case the number of arrangements of  $  n $
 +
different particles in  $  m $
 +
indistinguishable cells, that is, the number of classes, is  $  \sum _ {k=1}  ^ {m} S ( n , k ) $,
 +
where  $  S ( n , k ) $
 +
are the [[Stirling numbers]] of the second kind:
  
If one does not distinguish either particles or cells, then an arrangement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342041.png" /> identical particles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342042.png" /> identical cells is obtained; the number of such arrangements is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342043.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342044.png" /> is the number of additive partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342045.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342046.png" /> natural numbers. One can also consider other partitions of arrangements into classes, for example when the above-mentioned permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342048.png" /> are taken from subgroups of the symmetric groups of degrees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013420/a01342050.png" />, respectively (this and other generalizations can be found in [[#References|[1]]], [[#References|[2]]]). Synonyms of  "arrangement"  are the terms  "n-permutationn-permutation" , and  "ordered n-sampleordered n-sample of a population" .
+
$$
 +
S ( n , k )  = \
 +
S ( n -1 , k - 1 ) +
 +
k S ( n - 1 , k ) ,\ \
 +
S ( 0 , 0 )  =  1 ,
 +
$$
 +
 
 +
$$
 +
S ( n , k )  =  0 \  \textrm{ for }  k > n  \textrm{ and }  k = 0 , n > 0 .
 +
$$
 +
 
 +
If one does not distinguish either particles or cells, then an arrangement of $  n $
 +
identical particles in $  m $
 +
identical cells is obtained; the number of such arrangements is $  \sum _ {k=1}  ^ {n} p _ {n} (k) $,  
 +
where $  p _ {n} (k) $
 +
is the number of additive partitions of $  n $
 +
into $  k $
 +
natural numbers. One can also consider other partitions of arrangements into classes, for example when the above-mentioned permutations $  \sigma $
 +
and $  \tau $
 +
are taken from subgroups of the symmetric groups of degrees $  n $
 +
and $  m $,  
 +
respectively (this and other generalizations can be found in [[#References|[1]]], [[#References|[2]]]). Synonyms of  "arrangement"  are the terms  "n-permutationn-permutation" , and  "ordered n-sampleordered n-sample of a population" .
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.V. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.V. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1977)  (Translated from French)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1977)  (Translated from French)</TD></TR></table>

Latest revision as of 18:48, 5 April 2020


with repetitions of $ n $ out of $ m $ elements

A finite sequence $ \overline{a}\; = ( a _ {i _ {1} } \dots a _ {i _ {n} } ) $ of elements from some set $ A = \{ a _ {1} \dots a _ {m} \} $. If all the term of $ \overline{a}\; $ are distinct, then $ \overline{a}\; $ is called an arrangement without repetitions. The number of arrangements of $ n $ out of $ m $ elements with repetitions is $ m ^ {n} $, and that without repetitions in $ (m) _ {n} = m ( m - 1 ) \dots (m-n-1) $.

An arrangement can be regarded as a function $ \phi $ given on $ Z _ {n} = \{ 1 \dots n \} $ and taking values in $ A $: $ \phi ( k ) = a _ {i _ {k} } $, $ k = 1 \dots n $. The elements of $ A $ are usually called cells (or urns), while those of $ Z _ {n} $ are called particles (or balls); $ \phi $ 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 $ \phi $ and $ \psi $, respectively, belong to the same class if and only if there is a permutation $ \sigma $ of $ Z _ {n} $ such that $ \phi ( \sigma (k) ) = \psi (k) $ for all $ k \in Z _ {n} $. In this case, the number of such classes, or, as it is called, the number of arrangements filling $ m $ different cells by $ n $ indistinguishable particles, is the number of combinations of $ n $ out of $ m $ 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 $ \phi $ and $ \psi $ respectively, belong to the same class if there exists a permutation $ \tau $ of $ A $ for which $ \tau ( \phi (k) ) = \psi (k) $ for all $ k \in Z _ {n} $. In this case the number of arrangements of $ n $ different particles in $ m $ indistinguishable cells, that is, the number of classes, is $ \sum _ {k=1} ^ {m} S ( n , k ) $, where $ S ( n , k ) $ are the Stirling numbers of the second kind:

$$ S ( n , k ) = \ S ( n -1 , k - 1 ) + k S ( n - 1 , k ) ,\ \ S ( 0 , 0 ) = 1 , $$

$$ S ( n , k ) = 0 \ \textrm{ for } k > n \textrm{ and } k = 0 , n > 0 . $$

If one does not distinguish either particles or cells, then an arrangement of $ n $ identical particles in $ m $ identical cells is obtained; the number of such arrangements is $ \sum _ {k=1} ^ {n} p _ {n} (k) $, where $ p _ {n} (k) $ is the number of additive partitions of $ n $ into $ k $ natural numbers. One can also consider other partitions of arrangements into classes, for example when the above-mentioned permutations $ \sigma $ and $ \tau $ are taken from subgroups of the symmetric groups of degrees $ n $ and $ m $, 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)
How to Cite This Entry:
Arrangement. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Arrangement&oldid=17266
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article