kombinace

Kombinace (combinations) are a fundamental concept in combinatorics describing the selection of elements from a finite set when the order of selection does not matter. They are contrasted with permutations, where the order is relevant.

Notation and formula: The number of ways to choose k elements from a set of n is denoted as n choose k and written C(n, k). It equals n! / (k!(n − k)!). It holds that C(n, k) = C(n, n − k).

Types: Without repetition, each element can be chosen at most once, giving C(n, k) possibilities. With repetition, where elements may be selected multiple times, the number of multisets is C(n + k − 1, k).

Examples: From a deck of 52 cards, the number of 5-card hands is C(52, 5) = 2,598,960. From 5 letters, choosing 3 with repetition allowed: C(5 + 3 − 1, 3) = C(7, 3) = 35.

Applications: Combinations are used in counting problems, probability distributions (such as the hypergeometric distribution), and algebraic contexts like the binomial theorem. They provide the foundation for determining how many distinct selections are possible in scenarios where order does not influence the outcome.

Relation to other concepts: Combinations differ from permutations, which count ordered arrangements. Multiset combinations extend the idea to scenarios where repetition is allowed. The binomial coefficient appears in various mathematical formulas and plays a central role in combinatorial identities and proofs.

History and terminology: The concept is tied to the binomial coefficient, named for its appearance in expanding (x + y)^n. In many languages, including Czech and Slovak, the term for this concept is “kombinace.”