7
$\begingroup$

Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\{t \})$. Then $\sum_{t \in f(S)} |\alpha_t|$ is a partition of $|S|$ with $k$ nonempty parts.

I would really like to have a nice expression, or indeed bijection, for the number of pairs $g, h: S \to S$ such that $f = g \circ h$. These can be enumerated in a naive way with Bell and Stirling numbers of the second kind, by considering that the $h$-fibers need to refine $\alpha$ and $g(S)$ needs to contain $f(S)$ (and the $g$-fibers need to partition $h(S)$ in the right way), but the expression is not enlightening at all. If there's some nice identity or known bijective correspondence to which someone could point me, I'd be very grateful.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Suppose $f$ is a constant function, i.e., $\alpha=\{S\}$. Let $n=\#S$. Then the number of such factorizations is $\sum_{i=0}^{n} n^{n-i} \cdot (n)_i \cdot S(n,i)$ where $S(n,i)$ is the Stirling number of the 2nd kind and $(n)_i := n(n-1)\cdots(n-i+1)$. Already in this special case it does not seem like we can do better than a summation. For example, with $n=8$ this evaluates to $28186856832 = 2^7\times 3\times 73403273$, which has a huge prime factor (so there cannot be a product formula). $\endgroup$
    – Sam Hopkins
    Commented Nov 9, 2021 at 22:46
  • 1
    $\begingroup$ @SamHopkins thanks for doing that calculation! Indeed, the constant maps are maximal. More generally, if $f_1, f_2$ are such that the partition into $f_1$-fibers refines the partition into $f_2$-fibers, then there are at least as many factorizations of $f_2$ as of $f_1$. (Any $h$ that works for $f_2$ will work for $f_1$, and once you've picked $h$, say $|h(S)| = m$, you have $n^{n-m}$ choices for $g$, whether factoring $f_1$ or $f_2$.) $\endgroup$
    – Sophie M
    Commented Nov 10, 2021 at 2:07

0

Reset to default

You must log in to answer this question.