Enumeration of splitting subsets of endofunctions on finite sets

Abstract

Let $d$ and $n$ be positive integers such that $d|n$. Let $[n]=\{1,2,\dots ,n\}$ and $T$ be an endofunction on $[n]$. A subset $W$ of $[n]$ of cardinality $n/d$ is said to be $d$-splitting if $W\cup TW\cup \cdots \cup T^{d-1}W=[n]$. Let $\sigma (d;T)$ denote the number of $d$-splitting subsets. If $\sigma (2;T)>0$, then we show that $\sigma (2;T)=g_T(-1)$, where $g_T(t)$ is the generating function for the number of $T$-invariant subsets of $[n]$. It is interesting to note that substituting a root of unity into a polynomial with integer coefficients has an enumerative meaning. More generally, let $g_T(t_1,\dots ,t_d)$ be the generating function for the number of $d$-flags of $T$-invariant subsets. We prove for certain endofunctions $T$, if $\sigma (d;T)>0$, then $\sigma (d;T)=g_T(\zeta ,{\zeta }^2,\dots ,{\zeta }^d)$, where $\zeta$ is a primitive $d^{th}$ root of unity.

19 pages, 12 figures