## § 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

#### § 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$: