Combinatorics

Start here

• ConceptCombinatorics

  Combinatorics is the part of mathematics that studies finite or countable discrete structures. It asks three main types of question about such structures. Enumerative questions ask how many structures of a given type exist. Existence questions ask if a structure with given properties exists. Extremal questions ask how large or small a structure with given properties can be.

• ConceptDouble counting

  Double counting is a proof technique in combinatorics. To prove that two expressions are equal, one shows that both count the elements of the same finite set. Each expression comes from a different way to count that set.

• TheoremPigeonhole principle

  Let $A$ and $B$ be finite sets with $|A| > |B|$, and let $f : A \to B$ be a function. Then there are elements $a \neq a'$ of $A$ with $f(a) = f(a')$. In other words, $f$ is not injective.

• ConceptFactorial

  The factorial of a natural number $n$ is the product of the positive integers up to $n$. It counts the orderings of $n$ distinct objects and appears in most counting formulas. The node factorial gives the precise definition.

• ConceptPermutation

  A permutation of a set is a rearrangement of its elements, that is, a bijection from the set to itself. Permutations are the basic objects of enumerative combinatorics and of the theory of symmetric groups. The node permutation gives the precise definition.

• ConceptFalling and rising factorials

  The falling factorial $x^{\underline{n}}$ multiplies $n$ consecutive factors going down from $x$, and the rising factorial $x^{\overline{n}}$ multiplies $n$ consecutive factors going up from $x$. Both are polynomials of degree $n$ in $x$, and both reduce to the factorial $n!$ for a suitable choice of $x$. The falling factorial counts ordered selections without repetition, and the rising factorial (the Pochhammer symbol of special functions) appears in hypergeometric series. The node falling factorial treats the falling case alone.