Namespaces
Variants
Actions

Difference between revisions of "Combination"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (better)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
''of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232403.png" /> elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232404.png" />''
+
{{TEX|done}}
  
A subset of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232405.png" /> of some given finite set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232406.png" />. The number of combinations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232407.png" /> elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232408.png" /> is written <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c0232409.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324010.png" /> and is equal to
+
{{MSC|05A}}
  
<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/c/c023/c023240/c02324011.png" /></td> </tr></table>
+
''of $n$ elements from $m$''
  
The generating function for the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324014.png" />, has the form
+
A subset of cardinality $n$ of some given finite set of cardinality $m$. The number of combinations of $n$ elements from $m$ is written $C_m^n$ or $\binom mn$ and is equal to
  
<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/c/c023/c023240/c02324015.png" /></td> </tr></table>
+
$$\frac{m!}{n!(m-n)!}\,.$$
  
Combinations can also be considered as non-ordered samples of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324016.png" /> from a general aggregate of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324017.png" /> elements. In combinatorial analysis, a combination is an equivalence class of arrangements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324018.png" /> elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324019.png" /> (cf. [[Arrangement|Arrangement]]), where two arrangements of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324020.png" /> from a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324021.png" />-element set are called equivalent if they consist of the same elements taken the same number of times. In the case of arrangements without repetitions, every equivalence class is determined by the set of elements of an arbitrary arrangement from this class, and can thus be considered as a combination. In the case of arrangements with repetitions, one arrives at a generalization of the concept of a combination, and then an equivalence class is called a combination with repetitions. The number of combinations with repetitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324022.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324023.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023240/c02324024.png" />, and the generating function for these numbers has the form
+
The generating function for the sequence $C_m^n$, $n=0,\dots,m$, $C_m^0=1$, has the form
  
<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/c/c023/c023240/c02324025.png" /></td> </tr></table>
+
$$\sum_{n=0}^m\binom mnx^n=(1+x)^m.$$
 +
 
 +
Combinations can also be considered as non-ordered samples of size $n$ from a general aggregate of $m$ elements. In combinatorial analysis, a combination is an equivalence class of arrangements of $n$ elements from $m$ (cf. [[Arrangement|Arrangement]]), where two arrangements of size $n$ from a given $m$-element set are called equivalent if they consist of the same elements taken the same number of times. In the case of arrangements without repetitions, every equivalence class is determined by the set of elements of an arbitrary arrangement from this class, and can thus be considered as a combination.
 +
 
 +
In the case of arrangements with repetitions, one arrives at a generalization of the concept of a combination, and then an equivalence class is called a combination with repetitions. The number of combinations with repetitions of $n$ from $m$ is equal to $C_{m+n-1}^n$, and the generating function for these numbers has the form
 +
 
 +
$$\sum_{k=0}^\infty C_{m+k-1}^kx^k=\sum_{k=0}^\infty\binom{m+k-1}{k}x^k=\frac{1}{(1-x)^m}.$$
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. 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 combinatorial analysis" , Wiley  (1958)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. 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 combinatorial analysis" , Wiley  (1958)</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
 +
The numbers of combinations, $\binom mn$, are just the [[binomial coefficients]].
  
 +
The formula for the number of combinations with repetition may be derived as follows.  Given a set $X$ of size $n$, list the elements in arbitrary order $x_1,\ldots,x_n$.  A combination with repetition of $k$ elements from $X$ may be encoded as a sequence of symbols consisting of $k$ dots $\bullet$ and $n-1$ bars $|$, where the number of occurrences of $\bullet$ between the $i-1$-th $|$ and the $i$-th $|$ denotes the number of occurrences of  $x_i$ in the combination.  Thus, for example, the sequence beginning ${\bullet}{\bullet}||{\bullet}|\cdots$ encodes a combination containing $2$ occurrences of $x_1$, $0$ occurrences of $x_2$ and $1$ occurrence of $x_3$.  The number of such encoding sequences is then $\binom{n+k-1}{k}$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley  (1986)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley  (1986) {{ZBL|0907.05002}}</TD></TR>
 +
</table>

Latest revision as of 17:22, 18 September 2016


2020 Mathematics Subject Classification: Primary: 05A [MSN][ZBL]

of $n$ elements from $m$

A subset of cardinality $n$ of some given finite set of cardinality $m$. The number of combinations of $n$ elements from $m$ is written $C_m^n$ or $\binom mn$ and is equal to

$$\frac{m!}{n!(m-n)!}\,.$$

The generating function for the sequence $C_m^n$, $n=0,\dots,m$, $C_m^0=1$, has the form

$$\sum_{n=0}^m\binom mnx^n=(1+x)^m.$$

Combinations can also be considered as non-ordered samples of size $n$ from a general aggregate of $m$ elements. In combinatorial analysis, a combination is an equivalence class of arrangements of $n$ elements from $m$ (cf. Arrangement), where two arrangements of size $n$ from a given $m$-element set are called equivalent if they consist of the same elements taken the same number of times. In the case of arrangements without repetitions, every equivalence class is determined by the set of elements of an arbitrary arrangement from this class, and can thus be considered as a combination.

In the case of arrangements with repetitions, one arrives at a generalization of the concept of a combination, and then an equivalence class is called a combination with repetitions. The number of combinations with repetitions of $n$ from $m$ is equal to $C_{m+n-1}^n$, and the generating function for these numbers has the form

$$\sum_{k=0}^\infty C_{m+k-1}^kx^k=\sum_{k=0}^\infty\binom{m+k-1}{k}x^k=\frac{1}{(1-x)^m}.$$

References

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


Comments

The numbers of combinations, $\binom mn$, are just the binomial coefficients.

The formula for the number of combinations with repetition may be derived as follows. Given a set $X$ of size $n$, list the elements in arbitrary order $x_1,\ldots,x_n$. A combination with repetition of $k$ elements from $X$ may be encoded as a sequence of symbols consisting of $k$ dots $\bullet$ and $n-1$ bars $|$, where the number of occurrences of $\bullet$ between the $i-1$-th $|$ and the $i$-th $|$ denotes the number of occurrences of $x_i$ in the combination. Thus, for example, the sequence beginning ${\bullet}{\bullet}||{\bullet}|\cdots$ encodes a combination containing $2$ occurrences of $x_1$, $0$ occurrences of $x_2$ and $1$ occurrence of $x_3$. The number of such encoding sequences is then $\binom{n+k-1}{k}$.

References

[a1] M. Hall, "Combinatorial theory" , Wiley (1986) Zbl 0907.05002
How to Cite This Entry:
Combination. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Combination&oldid=11802
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article