no. 16 · Tuesday 17 November 2026
Enumerating Solutions to Type (2,3) Composition Identities of Finite Endofunctions
Abstract
We enumerate ordered pairs $(f,g)$ of endofunctions on a finite labeled set $X$ satisfying a composition identity of type $(2,3)$, with two factors on one side and three on the other. For all sixteen forms up to exchanging $f$ and $g$, we derive formulas involving finite sums and generating functions. The arguments use images and fibers, homomorphisms between functional digraphs, and isomorphism types of iterates. A common construction decomposes weighted allocations of fibers into trees and cycles, yielding determinant expressions for several generating functions. Colored functional digraphs provide further formulas. As a by-product, for arbitrary prescribed endofunctions $A,B$ on $X$, we derive an inclusion–exclusion formula over subsets of $X$ for the number of endofunctions $g$ on $X$ satisfying $B=gAg$.
- fields
- Combinatorics, Rings and Algebras