Combination (mathematics)

A combination counts the ways to choose k items from n without regard to order. Explains notation, the binomial coefficient, formulas, examples, variations, properties, and common applications.

A combination is a selection of items taken from a larger set where the order of the chosen items does not matter. This concept is a central object of combinatorics, the branch of mathematics concerned with counting, arrangement, and existence questions for finite structures. When only which elements are chosen matters — not the sequence in which they are listed — we speak of combinations rather than permutations. The contrast is important: the same chosen set can correspond to many different ordered lists.

$nCk$

Notation and basic formula

The number of ways to choose k items from an n-element set (with 0 ≤ k ≤ n) is usually written as n choose k, denoted C(n,k), nCk, or using the binomial coefficient notation (n k). It can be computed by the closed form n! / (k!(n − k)!), where n! (factorial) equals 1·2·3·…·n. This expression counts how many distinct k-element subsets exist, because it divides the number of ordered selections (permutations of k distinct elements) by the number of orderings of each chosen subset. For an explanation of the factorial function used in the formula see factorial.

${\tbinom {n}{k}}$

Examples and the order-versus-selection distinction

As a simple example, selecting 3 people from a committee of 6 produces C(6,3) = 20 different combinations. If order mattered, each combination of three could be arranged in 3! = 6 ways, producing 120 ordered lists (permutations). Thus permutations are generally more numerous because they distinguish arrangements that combinations identify as the same set. For more on arrangements where order is significant see permutations.

${\tfrac {n!}{k!(n-k)!}}$

Variants and useful properties

Boundary cases: C(n,0) = C(n,n) = 1; C(n,k) = 0 when k > n for the usual “without repetition” interpretation.
Symmetry: C(n,k) = C(n,n−k). This follows directly from the factorial formula and reflects that choosing k items to include is equivalent to choosing n−k items to exclude.
Pascal's identity: C(n,k) = C(n−1,k−1) + C(n−1,k), which underpins Pascal's triangle and many inductive arguments.
With repetition allowed (multisets), the number of k-element selections from n types is C(n+k−1,k); this is a standard variant used in compositions and stars-and-bars arguments.

Applications and computational notes

Combinations appear across probability, statistics, enumerative combinatorics, and algorithm design. Binomial coefficients are the coefficients of the binomial theorem and count subsets of given sizes in a finite set, which makes them useful for calculating event probabilities and for combinatorial proofs. In computation, large n choose k values are often computed using multiplicative formulas or dynamic programming (Pascal's triangle) to avoid directly computing very large factorials and to reduce rounding or overflow issues.

Because of their simple definition and wide applicability, combinations and the binomial coefficients remain a fundamental tool for reasoning about finite choices, sampling without order, and many elementary counting problems.