Combinatorial principles: Difference between revisions

Latest revision as of 14:45, 19 April 2023

In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.

The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have same number of elements. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in discrete context.

Many combinatorial identities arise from double counting methods or the method of distinguished element. Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.

Rule of sum[edit]

The rule of sum is an intuitive principle stating that if there are a possible outcomes for an event (or ways to do something) and b possible outcomes for another event (or ways to do another thing), and the two events cannot both occur (or the two things can’t both be done), then there are a + b total possible outcomes for the events (or total possible ways to do one of the things). More formally, the sum of the sizes of two disjoint sets is equal to the size of their union.

Rule of product[edit]

The rule of product is another intuitive principle stating that if there are a ways to do something and b ways to do another thing, then there are a · b ways to do both things.

Inclusion–exclusion principle[edit]

Inclusion–exclusion illustrated for three sets

The inclusion–exclusion principle relates the size of the union of multiple sets, the size of each set, and the size of each possible intersection of the sets. The smallest example is when there are two sets: the number of elements in the union of A and B is equal to the sum of the number of elements in A and B, minus the number of elements in their intersection.

Generally, according to this principle, if A₁, …, A_n are finite sets, then

{displaystyle {begin{aligned}left|bigcup _{i=1}^{n}A_{i}right|&{}=sum _{i=1}^{n}left|A_{i}right|-sum _{i,j,:,1leq i<jleq n}left|A_{i}cap A_{j}right|\&{}qquad +sum _{i,j,k,:,1leq i<j<kleq n}left|A_{i}cap A_{j}cap A_{k}right|- cdots +left(-1right)^{n-1}left|A_{1}cap cdots cap A_{n}right|.end{aligned}}}

@@ Line 1: / Line 1: @@
 In proving results in [[combinatorics]] several useful ”’combinatorial rules”’ or ”’combinatorial principles”’ are commonly recognized and used.
-The [[rule of sum]], [[rule of product]], and [[inclusion–exclusion principle]] are often used for [[Enumerative combinatorics|enumerative]] purposes. [[Bijective proof]]s are utilized to demonstrate that two sets have the same [[cardinality|number of elements]]. The [[pigeonhole principle]] often ascertains the existence of something or is used to determine the minimum or maximum number of something in a [[Discrete mathematics|discrete]] context.
+The [[rule of sum]], [[rule of product]], and [[inclusion–exclusion principle]] are often used for [[Enumerative combinatorics|enumerative]] purposes. [[Bijective proof]]s are utilized to demonstrate that two sets have same [[cardinality|number of elements]]. The [[pigeonhole principle]] often ascertains the existence of something or is used to determine the minimum or maximum number of something in [[Discrete mathematics|discrete]] context.
 Many [[combinatorial identities]] arise from [[Double counting (proof technique)|double counting]] methods or the [[method of distinguished element]]. [[Generating function]]s and [[recurrence relation]]s are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.