Timeline for Factoring a function from a finite set to itself
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2021 at 2:07 | comment | added | Sophie M | @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$.) | |
| Nov 9, 2021 at 22:46 | comment | added | Sam Hopkins | 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). | |
| Nov 9, 2021 at 18:50 | history | asked | Sophie M | CC BY-SA 4.0 |