ENUMERATION OF SPLITTING SUBSETS OF ENDOFUNCTIONS ON FINITE SETS

NEW

Problem: Let $X$ be a finite set of size $n$, let $T:X\to X$, and let $d\mid n$. A subset $W\subseteq X$ with $|W|=n/d$ is $d$-splitting if

Let $\sigma(d;T)$ be the number of such subsets. The paper’s Problem 1.2 asks for $\sigma(d;T)$ for arbitrary $T$.

Result: For $d=1$, $\sigma(1;T)=1$. For $d\ge2$, the following gives an exact formula.

Decompose the functional digraph of $T$ into weak connected components. For each component $C$, let its directed cycle be

For each vertex $v$, let $\operatorname{ch}(v)$ be the set of non-cycle preimages of $v$, i.e. $u\in\operatorname{ch}(v)$ iff $T(u)=v$, excluding the cycle predecessor when $v$ lies on the cycle.

Define recursively, from leaves upward, numbers $F_v(a)$ for $a\in\{0,\dots,d-1\}$:

and for $1\le a\le d-1$,

Empty products are $1$, empty sums are $0$.

For a cycle vertex $c_i$, define

and for $1\le b\le d-1$,

Now form the $d\times d$ matrix $M_i$, whose rows and columns are indexed by $0,\dots,d-1$, by

Then the contribution of the component $C$ is

and the desired number is

where the product is over all weak connected components of the functional digraph of $T$.

Why this works: a $d$-splitting subset $W$ is equivalent to a coloring

with $W=\kappa^{-1}(0)$, such that every vertex of color $0$ has only preimages of color $d-1$, while every vertex of color $b>0$ has exactly one preimage of color $b-1$, all other preimages having color $d-1$. This local condition is exactly what the above tree recursions and cycle transfer matrices count. Conversely, any such coloring gives a splitting set because $T$ maps color $i$ bijectively onto color $i+1$ for $0\le i<d-1$, so the color classes are precisely

Citation: No known general closed formula for arbitrary endofunctions appears in Aggarwal’s paper; the formula above is a direct resolution by dynamic programming on the functional graph decomposition.