Namespaces
Variants
Actions

Combination

From Encyclopedia of Mathematics
Revision as of 10:18, 6 September 2014 by Ivan (talk | contribs) (TeX)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

References

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