Definition and Basic Concepts
Combinations Defined
Selection of k elements from n distinct elements without regard to order. Order irrelevant: {a,b} = {b,a}. Fundamental counting unit in subset selection and combinatorics.
Difference from Permutations
Permutations: ordered arrangements, combinations: unordered subsets. Permutations count orderings; combinations count distinct sets.
Set-Theoretic Interpretation
Combinations correspond to k-element subsets of an n-element set. Number of such subsets given by binomial coefficients. Basis for combinatorial enumeration.
Formulas and Notation
Binomial Coefficient Notation
Notation: C(n, k), n choose k, or \(\binom{n}{k}\). Represents number of combinations of k elements chosen from n.
Explicit Formula
Defined by factorials:
\(\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}\)Factorial Definition
n! = n × (n-1) × ... × 2 × 1, with 0! = 1 by convention. Factorials measure permutations of n distinct elements.
Binomial Theorem and Coefficients
Statement of the Binomial Theorem
Expansion of powers of binomials:
\(\displaystyle (x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{k} y^{n-k}\)Role of Combinations
Coefficients \(\binom{n}{k}\) count ways to select k x-terms among n factors. Fundamental link between algebra and combinatorics.
Applications
Used in probability, algebraic expansions, discrete distributions, and analysis of algorithms.
Pascal’s Triangle
Construction
Triangular array where each number is sum of two above:
Row 0: 1Row 1: 1 1Row 2: 1 2 1Row 3: 1 3 3 1... Relation to Combinations
Element at row n, position k equals \(\binom{n}{k}\). Provides recursive method to compute combinations without factorials.
Properties
Symmetry, additive identity, diagonal counts (e.g., natural numbers, triangular numbers).
Properties and Identities
Symmetry Property
\(\displaystyle \binom{n}{k} = \binom{n}{n-k}\). Equivalence of choosing k out of n or excluding n-k.
Pascal’s Identity
\(\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Basis for recursive computations.
Summation Identities
Sum over k: \(\sum_{k=0}^n \binom{n}{k} = 2^n\). Total subsets of n-element set.
Permutations vs Combinations
Permutations
Ordered selections: number of k-permutations from n is:
\(\displaystyle P(n,k) = \frac{n!}{(n-k)!}\)Combinations
Unordered selections: number of k-combinations from n is:
\(\displaystyle C(n,k) = \frac{n!}{k!(n-k)!}\)Relation
Permutations count = combinations count × k! (arrangements of selected elements).
Calculation Methods
Direct Factorial Computation
Using factorial formula; efficient for small n, k. Computationally expensive for large values.
Recursive Computation via Pascal’s Identity
Computes \(\binom{n}{k}\) using \(\binom{n-1}{k-1} + \binom{n-1}{k}\). Efficient for dynamic programming.
Multiplicative Formula
Product form to avoid large factorials:
\(\displaystyle \binom{n}{k} = \prod_{i=1}^k \frac{n - k + i}{i}\)Applications of Combinations
Probability Theory
Calculating probabilities of events involving selection without replacement. Basis for hypergeometric distribution.
Statistics
Sample selection, hypothesis testing, combinatorial designs.
Computer Science
Algorithm complexity, data structure enumeration, cryptography keyspaces.
Other Fields
Physics (state counting), biology (genetic combinations), game theory (strategy enumeration).
Combinatorial Proofs
Proof of Symmetry
Counting subsets of size k and their complements of size n-k. Both counts equal total subsets.
Proof of Pascal’s Identity
Partition subsets by presence or absence of a fixed element. Sum counts to derive identity.
Proof of Summation Identity
Total subsets equal sum of all k-subsets: \(\sum_{k=0}^n \binom{n}{k} = 2^n\).
Advanced Topics in Combinations
Multiset Combinations
Selection with repetitions allowed. Number of multisets:
\(\displaystyle \binom{n + k - 1}{k}\)Combinations with Restrictions
Constraints on selection, e.g., minimum or maximum element counts, inclusion-exclusion principle.
q-Binomial Coefficients
Generalization with parameter q, appearing in combinatorial identities and quantum algebra.
Problems and Exercises
Basic Practice
Calculate \(\binom{7}{3}\), \(\binom{10}{0}\), \(\binom{5}{5}\).
Application Problems
Number of ways to select committees, form poker hands, or distribute identical items.
Proof Exercises
Prove identities using combinatorial arguments or algebraic manipulation.
| Problem | Solution Hint |
|---|---|
| Find number of 5-card hands from 52 cards | Use \(\binom{52}{5}\) |
| Count subsets of size 4 from set of size 10 | Compute \(\binom{10}{4}\) |
References
- Graham, R. L., Knuth, D. E., & Patashnik, O. - Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994, pp. 160-185.
- Stanley, R. P. - Enumerative Combinatorics, Volume 1, Cambridge University Press, 1997, pp. 30-75.
- Feller, W. - An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., Wiley, 1968, pp. 40-60.
- Brualdi, R. A. - Introductory Combinatorics, 5th ed., Pearson, 2010, pp. 50-85.
- Van Lint, J. H., & Wilson, R. M. - A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001, pp. 20-55.