Enumerative combinatorics

Enumerative combinatorics is an area of <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a> that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting <a href="/facts/Combination/nmvrhMm1">combinations</a> and counting <a href="/facts/Permutation/JSw9ukmv">permutations</a>. More generally, given an infinite collection of finite sets Si indexed by the <a href="/facts/Natural_number/u65og8JE">natural numbers</a>, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although <a href="/facts/Counting/DsRhH9RT">counting</a> the number of elements in a set is a rather broad <a href="/facts/Mathematical_problem/lFMR51de">mathematical problem</a>, many of the problems that arise in applications have a relatively simple <a href="/facts/Combinatorial/k14xUoKT">combinatorial</a> description. The <a href="/facts/Twelvefold_way/uc32hbQj">twelvefold way</a> provides a unified framework for counting <a href="/facts/Permutation/JSw9ukmv">permutations</a>, <a href="/facts/Combination/nmvrhMm1">combinations</a> and <a href="/facts/Partition_of_a_set/VeP9g8CA">partitions</a>.
The simplest such functions are <a href="/facts/Closed_formula/y0xCXlSk">closed formulas</a>, which can be expressed as a composition of elementary functions such as <a href="/facts/Factorial/kkfy1Bwe">factorials</a>, <a href="/facts/Exponentiation/pac6QY2g">powers</a>, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. The problem of finding a closed formula is known as <a href="/facts/Algebraic_enumeration/BjyEnuJ0">algebraic enumeration</a>, and frequently involves deriving a <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a> or <a href="/facts/Generating_function/K7UVjnjL">generating function</a> and using this to arrive at the desired closed form.
Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. 
In these cases, a simple <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic</a> approximation may be preferable. A function 
 
 
 
 g
 (
 n
 )
 
 
 {\displaystyle g(n)}
 
 is an asymptotic approximation to 
 
 
 
 f
 (
 n
 )
 
 
 {\displaystyle f(n)}
 
 if 
 
 
 
 f
 (
 n
 )
 
 /
 
 g
 (
 n
 )
 →
 1
 
 
 {\displaystyle f(n)/g(n)\rightarrow 1}
 
 as 
 
 
 
 n
 →
 ∞
 
 
 {\displaystyle n\rightarrow \infty }
 
. In this case, we write 
 
 
 
 f
 (
 n
 )
 ∼
 g
 (
 n
 )
 .
 
 
 
 {\displaystyle f(n)\sim g(n).\,}

Enumerative combinatorics open-in-new

Enumerative combinatorics