§ Rota's twelvefold way
- Count functions from .
- See that any such function is a subset of .
- We can write such a function as
- if we have , this means that we can permute images.
- If we have , this means that we can permute fibers.
§ f any function
§ f injective
- We count as given by the falling factorial.
§ f surjective, with equivalence .
- For each element , pick some subset . We need thesubsets to be disjoint, and all to be non-empty.
- We can permute the fibers , so we can place them by weakly decreasing order of size.
- Then this is the same as counting partitions of into subsets, given by / (stirling numbers of the second kind).
§ f surjective
- For each element , pick some subset . We need the subsets to be disjoint,and all to be non-empty.
- We get partway there by counting compositions of : the number of ways to split into such that each and .Note that ordering matters here, since we write a tuple .
- For example, the compositions of are , and .See that we have both and .
- Contrast this with partitions, which I write in weakly decreasing: , .
- This can be counted by the stars and bars method:
1 _ 2 _ 3 _ 4 _ ... _ |I|
- We want to fill the blanks (
_) with bars if we want a -composition (remember that compositionscan't have zeros). So we can count this by .
§ f surjective, with equivalence :