Partition Principle in Combinatorics
Theorem 1
Definition of a many-to-one function
Let finite sets $S$ and $T$ and a natural number $d \in \mathbb{N}$ be given. For each $s \in S$, if exactly $d$ elements $t \in T$ correspond to $f(t) = s$ under the function $f : T \to S$, then $f : T \to S$ is called $d$-to-one.
Division principle
If there exists a $d$-to-one mapping $f : T \to S$ between the finite sets $S$ and $T$, then the following holds. $$ |S| = {\frac{ |T| }{ d }} $$ Here $|X|$ is the cardinality of the set $X$.
Explanation
For example, the function $f$ defined as in the figure above is a three-to-one mapping.
A many-to-one mapping is, as the name suggests, a generalization of a one-to-one correspondence, and if $d = 1$ then it is precisely injective2.
The division principle is a conclusion that follows naturally from the definition of a many-to-one mapping; a separate proof is omitted.
Example: Circular permutations
As a standard application of the division principle, consider circular permutations. Given $n$ items, arranging them in a line is called a permutation, and the number of such arrangements is usually expressed as $_{n} P _{n} = n!$.
By contrast, a circular permutation is defined by arranging the items around a table with no start or end; two arrangements that appear different but can be made identical by rotation are considered the same circular permutation. To treat circular permutations mathematically without invoking the notions of “table” or “rotation”, one can first define the shift operator $S$ on finite lists as follows. $$ \begin{align*} S :& \left( a_{1} , \cdots , a_{n} \right) \mapsto \left( a_{2} , \cdots , a_{n} , a_{1} \right) \\ S^{k} :=& S \circ S^{k-1} \end{align*} $$ As shown, the shift operator moves the first item of a list to the end, and the superscript indicates the operator applied multiple times. Accordingly, the equivalence relation $L_{1} \equiv L_{2}$ that two lists $L_{1}$ and $L_{2}$ are the same in the context of circular permutations can be defined as equivalent to the existence of a natural number $k$ satisfying $L_{1} = S^{k} \left( L_{2} \right)$. When the number of items is $n$, the list $L$ has $n$ variants as follows. $$ L \equiv S \left( L \right) \equiv \cdots \equiv S^{n-1} \left( L \right) $$ Now let $T$ be the set of permutations formed from $n$ items, and let $S$ be the set of circular permutations formed from $n$ items. Then $f : T \to S$ is a $n$-to-one correspondence in which a single circular permutation $s \in S$ corresponds to $n$ permutations $t \in T$. By the division principle, the cardinality of $S$ is as follows, and this cardinality is precisely the number of circular permutations formed from $n$ items. $$ \left| S \right| = {\frac{ \left| T \right| }{ n }} = \frac{ n! }{ n } = (n - 1)! $$