"Type" of a permutation, set function, partition

71 Views Asked by At

Suppose I take the permutations on $n$ letters, $\mathcal{S}_n$, and consider two functions from it

$$f:\mathcal{S}_n \xrightarrow{\substack{\text{count} \\ \text{number} \\ \text{of cycles}}} \{1, \dotsc, n\}$$ $$g:\mathcal{S}_n \xrightarrow{\substack{\text{get} \\ \text{type}}} \substack{\text{Cycle types} \\ \text{ of }\mathcal{S}_n} \cong \substack{\text{partitions}\\ \text{ of } n}$$

Given $i \in \{1, 2, \dotsc, \#S\}$, the fiber of $f$ over $i$ will have cardinality $\displaystyle {n \brack i}$. As for $g$, given a cycle type, represented by the formal monomial $1^{m_1}2^{m_2}\dotsb n^{m_n}$ the fiber of $g$ over that element will have cardinality

$$\frac{n!}{1^{m_1}m_1! \dotsb n^{m_n}m_n!} \tag{1}$$

Now suppose I switch gears and compare partitions of sets to partitions of integers. Given a set $S$, there is a surjection

$$\bar{f}: \substack{\text{Partitions} \\ \text{ of }S} \xrightarrow{\substack{\text{count} \\ \text{number} \\ \text{of parts}}} \{1,\dotsc, \#S\}$$ $$\bar{g}: \substack{\text{Partitions} \\ \text{ of }S} \xrightarrow{\substack{\text{forget} \\ \text{elements}}} \substack{\text{Partitions} \\ \text{ of }\#S}$$

Given $i \in \{1, 2, \dotsc, \#S\}$, the fiber of $\bar{f}$ over $i$ will have cardinality $\displaystyle {n \brace i}$. As for $\bar{g}$, given a partition of the integer $\#S$, represented by $1^{n_1}2^{n_2}\dotsb \#S^{n_{\# S}}$ the fiber of $\bar{g}$ over that element will have cardinality

$$\frac{\#S!}{\prod\limits_{k=1}^{\# S} k!^{n_k} n_k!} \tag{2}$$

Now suppose I switch gears again and talk about set functions from $\{1, \dotsc, k\} \to \{1, \dotsc, n\}$. Denote the sets of these by $F_{k,n}$. Consider the two maps

$$\hat{f}: F_{k,n} \xrightarrow{\substack{\text{quotient by} \\ \text{left action of } \\ S_k}} \substack{\text{Multisets} \\ \text{of }\{1, \dotsc, n\} \\ \text{of size }k}$$ $$\hat{g}: F_{k,n} \xrightarrow{\substack{\text{get} \\ \text{"type"}}} \substack{\text{(Weak) } \\ n-\text{compositions} \\ \text{ of }k} \cong \substack{\text{(Strong) } \\ n-\text{compositions} \\ \text{ of }n + k}$$

Given a multiset of $\{1, \dotsc, n\}$ of size $k$, written as $1^{m_1}\dotsb n^{m_n}$, the number of elements in the fiber of $\hat{f}$ over that multiset is the multinomial coefficient $\displaystyle {k \choose m_1, \dotsc, m_n}$. As for $\hat{g}$, given a weak $k$-composition of $n$, the number of elements in the fiber of $\hat{g}$ over that element is

$$?? \tag{3}$$

Question: It is mostly (2) that I am interested in. Does it have a name? (This came up when I was studying the Faa di Bruno formula, in particular related to moments and cumulants of a probability distribution.) I am also particularly interested in the relation to "types" in statistics (which are like the multi-sets you can get when you draw from a categorical distribution).

Also, is there some unifying framework for these things? Why are the fibers of $f, \bar{f}, \hat{f}$ such well-named and familiar combinatorial objects, but the fibers of $g, \bar{g}, \hat{g}$ aren't (in my limited experience)?