Combinació

Combinació (Catalan for "combination") is a concept in combinatorics describing a selection of elements from a finite set where the order of selection is irrelevant. It contrasts with a permutation, where order matters.

If a set has n distinct elements and one chooses k of them without repetition, the number of possible combinations is the binomial coefficient written as C(n, k), or "n choose k." It is defined by C(n, k) = n! / (k!(n−k)!). Special cases include k = 0 or k = n, which yield 1, and the symmetry C(n, k) = C(n, n−k).

Combinations with repetition—where elements may be chosen more than once—are counted by C(n+k−1, k). This arises in problems where selections are multisets rather than sets.

Key properties include symmetry and recurrence: C(n, k) = C(n, n−k) and C(n, k) = C(n−1, k−1) + C(n−1, k). These properties connect to Pascal’s triangle and the binomial theorem, where binomial coefficients appear as coefficients of expanded powers of sums.

Applications of combinació include counting outcomes in probability, forming committees from a group, selecting lottery numbers, and counting subgroups in statistics. The concept provides a foundational tool for many counting problems in mathematics and related disciplines.