Combination Formulas to Know for Combinatorics

Combination formulas are essential in combinatorics, helping us count selections from sets. They cover various scenarios, from basic selections to those allowing repetition, and connect to concepts like Pascal's Triangle and the Binomial Theorem, enriching our understanding of counting.

1. Basic combination formula: C(n,r) = n! / (r! * (n-r)!)

   • Represents the number of ways to choose r elements from a set of n elements without regard to the order of selection.
   • The factorial notation (n!) indicates the product of all positive integers up to n.
   • The formula accounts for the fact that the order of selection does not matter by dividing by r! and (n-r)!.

2. Combination with repetition: C(n+r-1,r)

   • Used when selecting r elements from n types of items where repetition is allowed.
   • This formula transforms the problem into one of distributing r indistinguishable objects into n distinguishable boxes.
   • It simplifies counting scenarios where the same item can be chosen multiple times.

3. Complementary combination: C(n,r) = C(n,n-r)

   • Highlights the relationship between choosing r elements and leaving out n-r elements.
   • This property can simplify calculations by allowing the use of the smaller of r and n-r.
   • It emphasizes the symmetry in combinations.

4. Pascal's Triangle and its relation to combinations

   • Each entry in Pascal's Triangle corresponds to a combination value C(n,k).
   • The triangle is constructed such that each number is the sum of the two directly above it, reflecting the identity C(n,k) = C(n-1,k-1) + C(n-1,k).
   • It provides a visual representation of combinations and can be used to quickly find values.

5. Binomial Theorem: (x + y)^n = Σ C(n,k) * x^(n-k) * y^k

   • Describes the expansion of a binomial raised to a power n.
   • Each term in the expansion involves a combination C(n,k), which counts the ways to choose k elements from n.
   • This theorem connects algebra with combinatorial counting.

6. Vandermonde's Identity: C(m+n,r) = Σ C(m,k) * C(n,r-k)

   • Relates to counting the ways to choose r elements from two distinct groups of sizes m and n.
   • The identity shows how to break down a larger combination problem into smaller, manageable parts.
   • It is useful in problems involving multiple sets.

7. Hockey-stick identity: Σ C(n+i,i) = C(n+k+1,k)

   • A combinatorial identity that sums combinations in a specific pattern resembling a hockey stick in Pascal's Triangle.
   • It provides a way to calculate combinations by summing a series of values.
   • Useful for deriving results in combinatorial proofs and problems.

8. Combination of multisets: C(n+k-1,k)

   • Used when selecting k elements from n types of items where repetitions are allowed and order does not matter.
   • This formula generalizes the concept of combinations to cases where items can appear multiple times.
   • It is applicable in problems involving distributions and partitions.

9. Lucas' Theorem for combinations modulo prime numbers

   • Provides a way to compute combinations modulo a prime number by breaking down the problem into smaller parts based on the digits of the numbers in a specific base.
   • It is particularly useful in number theory and combinatorial problems involving modular arithmetic.
   • The theorem simplifies calculations that would otherwise be computationally intensive.

10. Stirling's approximation for large combinations

    • An approximation method for calculating factorials, useful for large n in combination formulas.
    • It states that n! is approximately √(2πn) * (n/e)^n, which simplifies the computation of combinations for large values.
    • This approximation helps in estimating the size of combinations without calculating exact values.