§ Rota's twelvefold way

• Count functions from $I \rightarrow O$.
• See that any such function is a subset of $O^I$.
• We can write such a function as $(o_1, o_2, \dots, o_{|I|}) \in O^I$
• if we have $S_I \circ f$, this means that we can permute images.
• If we have $f \circ S_O$, this means that we can permute fibers.

§ f any function

• we count $O^I$

§ f injective

• We count $O^{(I)} = O(O-1)\dots(O-I+1)$ as given by the falling factorial.

§ f surjective, with equivalence $S_I \circ f$.

• For each element $o \in O$, pick some subset $I_o \subseteq I$. We need the subsets $I_o$ to be disjoint, and all $I_o$ to be non-empty.
• We can permute the fibers $I_o$, so we can place them by weakly decreasing order of size.
• Then this is the same as counting partitions of $I$ into $O$ subsets, given by $S(n, x)$/ ${n\brace m}$ (stirling numbers of the second kind).

§ f surjective

• For each element $o \in O$, pick some subset $I_o \subseteq I$. We need the subsets $I_o$ to be disjoint, and all $I_o$ to be non-empty.
• We get partway there by counting compositions of $I$: the number of ways to split $|I|$ into $(a_1, a_2, \dots, a_k)$ such that each $(a_i > 0)$ and $\sum_i a_i = |I|$. Note that ordering matters here, since we write a tuple $(a_1, a_2, \dots a_k)$.
• For example, the compositions of $3$ are $(1, 1, 1)$, $(1, 2)$ and $(2, 1)$. See that we have both $(1, 2)$ and $(2, 1)$.
• Contrast this with partitions, which I write in weakly decreasing: $(1, 1, 1)$, $(2, 1)$.
• This can be counted by the stars and bars method:

1 _ 2 _ 3 _ 4 _ ... _  |I|

• We want to fill the $|I|-1$ blanks ( _) with $k$ bars if we want a $k$-composition (remember that compositions can't have zeros). So we can count this by $\binom{|I|-1}{k}$.

§ f surjective, with equivalence $S_I \circ f \circ S_O$: