kcombinations

In combinatorics, a k-combination of a set of n distinct elements is an unordered selection of k elements from the n elements. Order is irrelevant and repetitions are not allowed. It is commonly denoted C(n,k) or written as the binomial coefficient (n choose k).

The number of k-combinations from an n-element set is given by n choose k = n!/(k!(n−k)!). This is defined for 0 ≤ k ≤ n; if k < 0 or k > n, the value is zero. Example: from {A,B,C,D} choosing 2 gives 6 combinations: AB, AC, AD, BC, BD, CD.

For combinations with repetition (multisets) where elements may be repeated, the count is C(n+k-1, k). These are also called combinations with repetition or stars and bars problems.

Key properties include symmetry C(n,k) = C(n,n−k) and the Pascal relation C(n,k) = C(n−1,k) + C(n−1,k−1). The binomial coefficients appear in the expansion of (1+x)^n and in many counting problems.

K-combinations are used in probability, statistics, lottery draws, design of experiments, and algorithmic generation of subsets. Efficient generation and counting depend on factorial arithmetic and dynamic programming for larger n and k.