Counting Finite Maps through Functional Digraphs and Fibers

@misc{alekseyev2026counting,
  title = {{Counting Finite Maps through Functional Digraphs and Fibers}},
  author = {Max A. Alekseyev},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.08674},
  eprint = {2611.08674},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08674},
}

TY  - UNPB
TI  - Counting Finite Maps through Functional Digraphs and Fibers
AU  - Max A. Alekseyev
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.08674
UR  - https://arxiv.org/abs/2611.08674
AB  - We count solutions of composition identities for maps on finite sets, first for three identities in which both maps vary and then for commutation with a prescribed arithmetic map. For f∘ g=f∘ g∘ g, drawing an arrow from each element to its image reduces the enumeration to rooted trees attached to directed cycles. For f∘ f=f∘ g∘ f, grouping elements with the same f-value leads instead to a partition-based enumeration. A classical rooted-forest enumeration leads in both problems to 𝒯(x), the exponential generating function for rooted labeled trees. For f=g∘ f∘ g, the values on the cycles of g determine all remaining values. The exponential generating function 𝒟 for these ordered pairs and the ordinary generating function 𝒜 for endofunctions up to relabeling satisfy 𝒟(x)=𝒜(𝒯(x)). Finally, we count functions on ℤ/nℤ satisfying f(ax)=af(x), first for prime multipliers a and then for a broader class of composite multipliers. In each problem, fixing one map exposes independent choices for the other through its functional digraph or its fibers.
ER  -