Twelvefold way

From Wikipedia, the free encyclopedia

In combinatorics, a branch of mathematics, the twelvefold way provides a unified framework for counting permutations, combinations and partitions.

Let $N$ and $X$ be finite sets. Let $\,n = |N|$ and $\,x = |X|$ . Thus $N$ is an $n$ -set, and $X$ is an $x$ -set. The general problem we consider is the enumeration of functions from $N$ to $X$ .

There are three different conditions which may be imposed upon $f : N \rightarrow X$ .

no condition;
$f$ is injective;
$f$ is surjective.

There are four different equivalence relations which may be imposed upon the set of functions from $N$ to $X$ .

equality;
equality up to a permutation of $N$ ;
equality up to a permutation of $X$ ;
equality up to permutations of $N$ and $X$ .

These criteria can be joined in $3 \times 4 = 12$ ways.

1 Selection versus Partition
2 Ordered Selections and Partitions
3 Unordered Selections
4 Unordered Partitions
5 Balls and Boxes
6 Formulas
7 Generalizations
8 References

[edit] Selection versus Partition

A function $f : N \rightarrow X$ admits two different combinatorial interpretations.

$f$ selects $n$ elements from the set $X$ . The selection is indexed by $N$ .

$f$ partitions $N$ into $x$ disjoint subsets, labeled by the elements of $X$ .

[edit] Ordered Selections and Partitions

If $f$ is injective, then $f$ does not select any element more than once. In this case we say that $f$ selects elements without repetition. If $f$ is not required to be injective, then we say that repetition is allowed.

If $f$ is surjective, then every element of $X$ labels a non-empty subset of $N$ . In this case we say that $f$ is a partition of $N$ into $x$ parts. If $f$ is not required to be surjective, then we say that $f$ partitions $N$ into at most $x$ parts.

[edit] Unordered Selections

We interpret a function $f : N \rightarrow X$ as a selection from $X$ . The elements of $X$ are said to be indistinguishable if we do not distinguish between two selections that differ by a permutation of N.

Formally, an unordered selection is an equivalence class of functions $f : N \rightarrow X$ . Two functions $f$ and $F$ represent the same unordered selection if and only if there exists a bijection $h : N \rightarrow N$ such that $\, F = f \circ h$ .

Ordered selections are often called "permutations", and unordered selections are often called "combinations". The word "permutation" has a second meaning: namely, a bijection from a set to itself. We hope that this dual usage is not unduly confusing.

[edit] Unordered Partitions

We also interpret a function $f : N \rightarrow X$ as a partition of $N$ . The elements of $N$ are said to be indistinguishable if we do not distinguish between two partitions that differ by a permutation of $N$ . If the elements of $N$ are indistinguishable, then we usually speak of partitions of $n$ , rather than of an $N$ -set.

Formally, an unordered partition is an equivalence class of functions $f : N \rightarrow X$ . Two functions $f$ and $F$ represent the same unordered partition if and only if there exists a bijection $h : X \rightarrow X$ so that $F = h \circ f$ .

[edit] Balls and Boxes

Placing "balls" in "boxes" is a useful metaphor for counting problems. We think of N as the set of balls, and X as the set of boxes. The balls may be either distinguishable or indistinguishable, and the same is true of the boxes.

Injectivity of $f$ means that no box may contain more than one ball. Surjectivity of $f$ means that each box will contain at least one ball.

[edit] Formulas

Functions from $N$ to $X$ .

n

-permutations of an

x

-set with repetition allowed.

$\, x^n$

Functions from $N$ to X, up to a permutation of $N$ .

n

-combinations of an

x

-set with repetition allowed.

${x+n-1 \choose n}$

Functions from $N$ to $X$ , up to a permutation of $X$

Unordered partitions of an

n

-set into at most

x

parts.

$\, S(n,1) + S(n,2) + \cdots + S(n,x)$

whereas $\, S(n,k)$ is a Stirling number of the second kind.

Functions from $N$ to $X$ , up to permutations of $N$ and $X$

Unordered partitions of

n

into at most

x

parts.

$\, p_1(n) + p_2(n) + \cdots + p_x(n)$

where $\, p_k(n)$ is the number of partitions of

n

into

k

parts.

Injective functions from $N$ to $X$

n

-permutations of an

x

-set, without repetition.

$(x)_n = \frac{x!}{(x-n)!}$

Injective functions from $N$ to $X$ , up to a permutation of $N$

n

-combinations of an

x

-set, without repetition.

${x \choose n} = \frac{x!}{(x-n)!\, n!}$

Injective functions from $N$ to $X$ , up to a permutation of $X$ .

$1\ \mbox{if}\ n \leq x, \ 0\ \mbox{if}\ n>x$

Injective functions from $N$ to $X$ , up to permutations of $N$ and $X$ .

$1\ \mbox{if}\ n \leq x, \ 0\ \mbox{if}\ n>x$

Surjective functions from $N$ to $X$

Ordered partitions of an

n

-set into

x

parts.

$\, x!\, S(n,x)$

Surjective functions from $N$ to $X$ , up to a permutation of $N$ .

Ordered partitions of

n

into

x

parts.

${n-1 \choose x-1}$

Surjective functions from $N$ to $X$ , up to a permutation of $X$ .

Unordered partitions of an

n

-set into

x

parts.

$\, S(n,x)$

Surjective functions from $N$ to $X$ , up to permutations of $N$ and $X$ .

Unordered partitions of

n

into

x

parts.

$\, p_x(n)$

[edit] Generalizations

We can generalize further by allowing other groups of permutations to act on $N$ and $X$ . If $G$ is a group of permutations of $N$ , and $H$ is a group of permutations of $X$ , then we count equivalence classes of functions $f \colon N \rightarrow X$ . Two functions $f$ and $F$ are considered equivalent if, and only if, there exist $g\in G, h \in H$ so that $F = h \circ f \circ g$ . This extension leads to notions such as cyclic and dihedral permutations, as well as cyclic and dihedral partitions of numbers and sets.