Combinatorics

Introduction

Combinatorics is the mathematics of counting. How many ways can we arrange a set of objects? How many subsets does a set have? How many ways can we distribute items among recipients? These questions arise constantly in probability, computer science, and discrete mathematics.

The challenge in combinatorics is not the arithmetic—the challenge is setting up the problem correctly. The same verbal description can have vastly different answers depending on whether order matters, whether repetition is allowed, and how we define "different" arrangements.

Fundamental Counting Principles

The Multiplication Principle

If a procedure can be broken into stages, where stage 1 has (n_1) outcomes, stage 2 has (n_2) outcomes, and so on, then the total number of outcomes is:

(n_1)×(n_2)×⋯×(n_k)

The Addition Principle

If a task can be done in one of several mutually exclusive ways, with (n_1) ways for method 1, (n_2) ways for method 2, etc., then the total number of ways is:

(n_1)+(n_2)+⋯+(n_k)

Permutations

A permutation is an ordered arrangement. Order matters: ABC and BAC are different permutations.

Permutations of n Distinct Objects

The number of ways to arrange n distinct objects in a row is:

n!=n×(n−1)×(n−2)×⋯×2×1

By convention, 0!=1. For example, 5!=120 ways to arrange 5 books on a shelf.

Permutations of r Objects from n

The number of ways to choose and arrange r objects from n distinct objects (without replacement) is:

P(n,r)=(n!)/((n−r)!)=n×(n−1)×⋯×(n−r+1)

Combinations

A combination is an unordered selection. Order does not matter: choosing {A,B,C} is the same as choosing {C,B,A}.

Choosing r from n

The number of ways to choose r objects from n distinct objects (without replacement, order irrelevant) is the binomial coefficient:

C(n,r)=([n],[r])=n!/(r!(n-r)!)

The formula comes from dividing the permutation count by r! to account for the r! ways of arranging each selection.

Properties of Binomial Coefficients

Symmetry: ([n],[r])=([n],[n-r]) Choosing r items is equivalent to choosing n−r items to exclude.

Pascal's Identity: ([n],[r])=([n-1],[r-1])+([n-1],[r]) This recursion builds Pascal's Triangle.

Row Sum: (∑_r=0^n)(([n],[r]))=2 This counts all subsets of an nelement set.

The Binomial Theorem

The binomial theorem expands powers of a binomial:

(x+y)n=(∑_k=0^n)(([n],[k])*x(n-k)*yk)

Each term ([n],[k])*x(n-k)*yk counts the number of ways to choose k factors of y from the n factors of (x+y)

Permutations with Repetition

When arranging objects where some are identical, divide by the factorial of each group's size. For objects with (n_1) of type 1, (n_2) of type 2, etc.:

(n!)/((n_1)!⋅(n_2)!⋅…⋅(n_k)!)

Stars and Bars

The stars and bars method counts the number of ways to distribute n identical objects into k distinct bins.

The number of ways to distribute n identical items into k distinct bins (allowing empty bins) is: ([n+k-1],[k-1])=([n+k-1],[n])

The idea: represent the distribution as a sequence of n stars (items) and k−1 bars (dividers). We choose positions for the bars among the n+k−1 total positions.

Summary Table

Ordered, no repetition (permutation): P(n,r)=n!/(n−r)!

Ordered, with repetition: nr

Unordered, no repetition (combination): C(n,r)=([n],[r])=n!/(r!(n-r)!)

Unordered, with repetition (multiset): ([n+r-1],[r])

Connection to Other Concepts

Combinatorics is essential for probability. The probability of an event is often computed as (favorable outcomes) / (total outcomes), both of which require counting.

The binomial coefficient ([n],[k]) appears in the binomial distribution, where it counts the number of ways to get exactly k successes in n trials.

In algorithm analysis, combinatorics determines the number of inputs, iterations, or operations. The complexity of many algorithms depends on combinatorial quantities.

Summary

Combinatorics provides systematic methods for counting arrangements and selections. The key distinction is between permutations (order matters) and combinations (order doesn't matter), and between sampling with or without repetition.

The binomial coefficient ([n],[r]) counts combinations and appears in the binomial theorem for expanding (x+y)n The multiplication and addition principles are the foundation for more complex counting arguments.

The challenge in combinatorics is recognizing which counting principle applies to a given problem. Practice and careful analysis of what "different" means in each context are essential.