Combinatorial Identities & Laws

NOTE

Identities are mathematical truths that remain equal for all values. In combinatorics, these often represent two different ways of counting the same set, proving that the left-hand side and right-hand side are logically equivalent.

The Fundamental Laws

Logic-based identities used to simplify the boundaries of sets.

• Demorgan’s Law
  • The Law: $\neg (A\cup B)=\neg A\cap \neg B$ and $\neg (A\cap B)=\neg A\cup \neg B$.
  • Why it matters: Essential for switching between “OR” problems and “AND” problems, especially when using the Complement Rule.
• Sum Identity
  • The Law: The total number of ways to choose any number of elements from a set of $n$ is $2^n$.
  • Connection: ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$.

Binomial & Pascal Identities

The DNA of the Pascal Triangle and polynomial expansions.

• Binomial Theorem
  • The Law: $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$.
  • Why it matters: Links algebra to combinatorics; the coefficients of expanded polynomials are exactly the combinations $C(n,k)$.
• Pascal’s Identity
  • The Law: $\left(\genfrac{}{}{0ex}{}{n+1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.
  • Why it matters: The recursive definition of the Pascal Triangle. It represents the choice of either including or excluding a specific element from a selection.

Symmetry & Selection

Identities that exploit the “mirror” nature of combinations.

• Symmetry Identity
  • The Law: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$.
  • Why it matters: Choosing $k$ items to keep is mathematically identical to choosing $n-k$ items to discard. This significantly simplifies calculations when $k$ is large.

Identity Quick-Reference