Combinatorics

See also the Wikipedia article:

Combinatorics

Combinatorics is an area of discrete mathematics that studies collections of distinct objects and the ways that they can be counted or ordered, or used to satisfy some optimality criterion.

The most basic ideas in combinatorics include:

factorials

The number of possible arrangements of $n$ distinct items is n-factorial, written $n!$ , which equals

$n\times(n-1)\times(n-2)\times\cdots\times2\times1$

• Example: Three items, A, B, and C, can be arranged in $3! = 3 \times 2 \times 1 = 6$ different ways: ABC, ACB, BAC, BCA, CAB, and CBA.

permutations

The number of arrangements that are possible when a subset of $k$ items is taken from a set of $n$ distinct items is a "permutation of $n$ objects taken $k$ at a time", which can be written as $P^n_k$ or ${}_nP_k$ , and is equal to $\frac{n!}{(n-k)!}$ .

• Example: The number of possible arrangements of the four letters A, B, C, D, taken two at a time, is $P^4_3=\frac{4!}{(4-2)!}=\frac{24}{2}=12$: AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, and DC.

combinations

The number of possible subsets of $k$ items taken from a set of $n$ items, where the order of the items doesn't matter (e.g., the sets ABC and BCA are considered equivalent), is a "combination of $n$ objects taken $k$ at a time", which is written $C^n_k$ or ${}_nC_k$ or $\binom{n}{k}$ , and is equal to $\frac{n!}{k!(n-k)!}$ .

• Example: The number of subsets of two letters chosen from the four letters A, B, C, and D, is $C^4_2=\frac{4!}{2!(4-2)!}=\frac{24}{2\times2}=6$ : AB, AC, AD, BC, BD, and CD.

distributions

partitions of integers or of sets

recurrence relations

inclusions

inversions

inclusion/exclusion principle

derangements and subfactorials

repetitions and replacements

various restrictions placed on problems

fundamental counting principle

circular permutations

generating functions

free and fixed permutations, rotational symmetry and reflective symmetry

cyclic permutations

multisets

Pascal's Triangle