1 Definition and notation
A combination is a way of choosing objects from a collection when the order of selection is irrelevant. If the same group of objects is selected, it is counted as the same combination regardless of how the objects were arranged during the choice. This idea appears throughout discrete mathematics because many problems depend only on membership, not sequence.
1.1 Basic idea of selection without order
The essential feature of a combination is that it records which elements are chosen, not the order in which they are chosen. For example, selecting apples, oranges, and pears is the same outcome as selecting pears, apples, and oranges. In counting problems, this distinction prevents overcounting outcomes that differ only by arrangement.
1.2 Combinations versus permutations
Combinations and permutations both describe selections from a set, but they answer different questions. A permutation concerns ordered arrangements, so different orders produce different outcomes. A combination ignores order, so only the chosen collection matters. This difference is central in counting because permutation counts are usually larger than combination counts for the same number of selected objects.
1.3 Set notation and subset interpretation
Combinations can be understood as subsets of a set. If a set has \(n\) elements, then selecting \(r\) elements corresponds to forming a subset of size \(r\). Under this interpretation, the number of combinations is the number of distinct \(r\)-element subsets.
1.4 Binomial coefficient notation
The number of combinations of \(n\) objects taken \(r\) at a time is commonly written as \(\binom{n}{r}\), read as “\(n\) choose \(r\).” Other notations such as \(C(n,r)\) or \({}_nC_r\) also appear in textbooks and applications. The binomial coefficient notation is especially common because of its connection to algebra and the binomial theorem.
2 Counting combinations
Counting combinations requires determining how many distinct groups of a given size can be formed from a larger set. The answer depends on how many elements are available and how many are selected. The standard formula provides a compact way to compute this number.
2.1 Derivation of the formula
To count the number of \(r\)-element combinations from an \(n\)-element set, one may first count ordered selections and then remove the effect of order. This leads to the familiar expression for \(\binom{n}{r}\). The derivation shows why combinations are smaller than permutations: each group is counted many times when order is ignored.
2.1.1 Factorial-based derivation
The number of ways to choose \(r\) objects in order from \(n\) objects is \[ n(n-1)(n-2)\cdots(n-r+1). \] Since the \(r\) chosen objects can be arranged in \(r!\) different orders, dividing by \(r!\) removes repeated counting. Thus, \[ \binom{n}{r}=\frac{n!}{r!(n-r)!}. \] This formula is one of the most widely used results in elementary combinatorics.
2.1.2 Symmetry property nCr = nC(n-r)
Choosing \(r\) objects from \(n\) is equivalent to choosing the \(n-r\) objects left unchosen. Because each selection determines a unique complement, the counts are equal: \[ \binom{n}{r}=\binom{n}{n-r}. \] This symmetry is often useful for simplifying calculations, especially when \(r\) is large.
2.2 Special cases
Certain values of \(r\) produce especially simple outcomes. These cases help anchor the general formula and are frequently used in proofs and applications.
2.2.1 Choosing zero items
There is exactly one way to choose no items from a set: select the empty subset. Therefore, \[ \binom{n}{0}=1. \]
2.2.2 Choosing all items
There is also exactly one way to choose all \(n\) items from an \(n\)-element set. Hence, \[ \binom{n}{n}=1. \]
2.2.3 Choosing one item
Selecting one item from \(n\) available objects can be done in \(n\) ways: \[ \binom{n}{1}=n. \] This case is the simplest nontrivial example of a combination count.
2.3 Combinations with repeated elements
Some counting problems allow repeated choice of the same type of object. In these settings, the selected items are not all distinct, and the ordinary formula for combinations must be adapted. Such problems arise in counting multisets and in distributing identical objects into categories.
2.3.1 Multiset combinations
A multiset allows repeated elements, so selecting items may include multiple copies of the same kind. The count depends on whether repetition is allowed and how many copies can be chosen. Multiset combinations are useful in problems involving repeated symbols, ingredient selections, or allocations among categories.
2.3.2 Stars and bars method
The stars and bars method counts ways to distribute identical objects among distinct bins or to choose repeated elements from a set. It converts a selection problem into a sequence of symbols that represent items and separators. This technique gives the number of nonnegative integer solutions to many equations and is a standard tool in combinatorics.
3 Properties and identities
Binomial coefficients satisfy many identities that make them flexible in algebraic and combinatorial arguments. These relationships often arise from counting the same set in more than one way. They also appear naturally in recursive tables and polynomial expansions.
3.1 Pascal's rule
Pascal’s rule states that \[ \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}. \] It reflects a simple choice: a selected element is either included or excluded. This rule underlies recursive computation of combinations and the structure of Pascal’s triangle.
3.2 Pascal's triangle
Pascal’s triangle arranges binomial coefficients in triangular form, with each entry formed by adding the two entries above it. The rows display the values of \(\binom{n}{r}\) for successive \(n\). The triangle provides an intuitive visual pattern for combinations and reveals many arithmetic regularities.
3.3 Binomial identities
Several identities follow from algebraic manipulation or combinatorial reasoning. They simplify sums involving combinations and support proofs in discrete mathematics.
3.3.1 Sum of combinations
The sum of all combinations in a row of Pascal’s triangle satisfies \[ \sum_{r=0}^{n}\binom{n}{r}=2^n. \] This identity counts all subsets of an \(n\)-element set, since each element is either included or excluded.
3.3.2 Alternating sums
Alternating sums such as \[ \sum_{r=0}^{n}(-1)^r\binom{n}{r} \] often evaluate to simple values. These expressions arise from expanding \((1-1)^n\) and from cancellation arguments in combinatorial proofs.
3.3.3 Vandermonde's identity
Vandermonde’s identity states that \[ \sum_k \binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}. \] It counts the number of ways to choose \(r\) objects from two separate groups of sizes \(m\) and \(n\). This identity is a classic example of combining algebraic and counting arguments.
3.4 Symmetry and complementarity
Binomial coefficients exhibit symmetry not only in the formula \(\binom{n}{r}=\binom{n}{n-r}\) but also in many related identities. Complementary choices, where selected and unselected elements are swapped, often provide the simplest interpretation of these symmetries. Such relationships make combination counts easier to analyze and remember.
4 Combinations in algebra
Combinations play a central role in algebra through polynomial expansion and coefficient extraction. They provide the numerical factors that appear when powers of sums are expanded. This link makes them especially important in the binomial theorem.
4.1 The binomial theorem
The binomial theorem gives the expansion of \((x+y)^n\) as \[ (x+y)^n=\sum_{r=0}^{n}\binom{n}{r}x^{n-r}y^r. \] Each binomial coefficient gives the number of ways to choose which factors contribute \(y\) rather than \(x\). The theorem connects counting with algebra in a direct and elegant way.
4.2 Coefficients in polynomial expansion
When a polynomial product or power is expanded, combination counts often determine the coefficients of terms. For example, in \((a+b)^n\), each term arises from selecting one of the two symbols from each factor. The coefficient counts how many selections produce the same monomial.
4.3 Combinatorial interpretation of powers
Powers such as \(2^n\) and more general expressions can be interpreted by counting selections. Since each of \(n\) elements may be either chosen or not chosen, the total number of subsets is \(2^n\). Similar reasoning applies to expressions with more than two options, where combinations organize the resulting counts.
5 Combinations in probability
Combinations are essential in probability because they count possible outcomes when order does not matter. Many probability models assume equally likely selections from a population, making combination counts the natural denominator. This is especially true in sampling without replacement.
5.1 Counting equally likely outcomes
In many experiments, outcomes are treated as equally likely when they involve selecting a group from a larger set. Combinations count the number of possible groups, which helps determine probabilities by comparing favorable outcomes with all possible outcomes. This method is standard in card games, lotteries, and sample selection.
5.2 Hypergeometric distribution
The hypergeometric distribution describes the probability of obtaining a given number of successes when sampling without replacement. Its formula uses binomial coefficients to count favorable and total selections. Because the draws are dependent, combinations are more appropriate than simple repeated-trial models.
5.3 Lottery and sampling problems
Lottery-style problems often ask for the chance of matching a selected set of numbers. These questions are naturally answered with combinations because the order of the drawn numbers does not matter. Similar reasoning applies to sampling problems in statistics, where a subset is drawn from a larger population.
5.4 Choosing without replacement
When items are selected without replacement, each choice changes the available pool. Combination counts are useful because they describe the number of possible selected groups independent of the order in which items were drawn. This principle appears in card dealing, random sampling, and quality-control models.
6 Advanced topics
More advanced uses of combinations extend beyond simple subset counting. They include collections of sets, structural problems in graphs, proof techniques, and analytic tools. These topics show the broad reach of combination theory in discrete mathematics.
6.1 Combinations of sets and families
Combinations can refer not only to elements of a set but also to collections of sets. In such cases, one studies subfamilies chosen from a larger family of sets. This perspective is useful in extremal combinatorics and in the study of intersecting families.
6.2 Combinations in graph theory
In graph theory, combinations appear when selecting vertices, edges, or subsets with certain properties. For example, counting the number of possible edges among \(n\) vertices uses the combination \(\binom{n}{2}\). Such counts are foundational in understanding graph structure and size.
6.3 Combinatorial proofs
A combinatorial proof establishes an identity by showing that both sides count the same set of objects. Combinations are often central to these arguments because they naturally describe selections. Such proofs are valued for their clarity and for revealing why an identity is true.
6.4 Generating functions
Generating functions encode combination counts into algebraic series. Binomial coefficients appear in expansions such as \((1+x)^n\) and in more general power series methods. These functions provide a powerful framework for solving recurrence relations and summation problems.
7 Applications
Combination counts are useful in many practical and theoretical settings. They help organize data, assess uncertainty, and design structured experiments. Their versatility explains why they appear in so many branches of mathematics and computation.
7.1 Statistics and sampling
In statistics, combinations are used to describe samples drawn from a population and to calculate probabilities for sample-based events. They also support the analysis of randomized study designs and the interpretation of sample spaces. Combination formulas make it possible to count possible selections without considering order.
7.2 Computer science and algorithms
Computer science uses combinations in search problems, brute-force enumeration, optimization, and data analysis. Algorithms that generate subsets, test candidate groups, or analyze networks often rely on combination counts to estimate complexity. They also appear in coding theory, database querying, and feature selection.
7.3 Design of experiments
Experimental design often requires choosing subsets of treatments, subjects, or factor levels. Combinations help determine how many test conditions or trial groups are possible. This supports balanced planning and systematic comparison across experimental setups.
7.4 Everyday counting problems
Everyday situations such as choosing menu items, forming teams, or selecting books from a shelf can be modeled with combinations. Any time the order of choice does not matter, combination counting may apply. This makes the concept useful far beyond formal mathematics.