NIST

combination

(algorithm)

Definition: Choose m of n elements, where m ≤ n.

See also permutation, subset.

Note: A combination is a subset with exactly m elements.

There are n!/(n-m)!m! combinations of n (distinguishable) elements taken m at a time. Why? To begin, there are n! permutations. Permutations that only differ in the order of the n-m elements not taken are the same combination, so divide by (n-m)!. The order of the m elements taken doesn't matter either, so divide by m!, too.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 March 2015.
HTML page formatted Mon Mar 2 16:13:48 2015.

Cite this as:
Paul E. Black, "combination", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 March 2015. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/combination.html