A k-combination (or k-subset) is a subset with k elements.
where n is the number of objects from which you can choose and k is the number to be chosen, and n! denotes the factorial.
The definition can be understood by considering a list of elements; the list can be ordered ways, and for each possible ordering can be partitioned into the first elements followed by the remaining elements. The first partition is then a selection of elements from the original list and all those partitions from every ordering cover all such selections. The complete permutation of the original list produces duplicate selections, however; some permutations result in a permuted but identical set for the first partition, and so we divide by to remove these, and other permutations result in permuted second partitions, and so we divide by to remove these.
The use of the definition in calculation is not always straightforward. For example, the number of five-card hands possible from a standard fifty-two card deck is:
Since it is impractical to calculate n! if the value of n is very large, a more efficient algorithm is
This method of calculation can be seen immediately from the recursive definition of the choose function:
with a base case of . It can be argued that is a more natural base case but the former follows easily from the latter anyway.
This second definition can be understood as stating that when adding an element to the selection, there are elements to choose from, and so this increases the number of possible selections by that much, but doing this to all selections produces duplicates (e.g. ) and so we divide by the size of the selection since that is the number of possibilities for the last element added.
Since as explained above a combination is a special case of a partition of a set; specifically, a partition into two sets of size k and n − k, you get the same number of combinations if you substitute k with n − k. Therefore, when k is more than half of n, it may be easier to compute the binomial coefficient using n − k in place of k.
For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also multiset).