Let finite group $G$ act on a finite set $X$ and hence on colorings $Y^X$, where $Y=\{1,2,\ldots,k\}$ is a set of colors. The Burnside-Pólya-Redfield-etc. counting theorem says that the number of orbits of $G$ acting on $Y^X$ is
$$ \frac{1}{\#G} \sum\_{g \in G} k^{c(g)},$$
where for $g\in G$, we use $c(g)$ to denote the number of cycles of the permutation $g\colon X \to X$.


Note that this number $P(k)$ is a polynomial in $k$, and it is an integer, so by the basic theory of integer-valued polynomials there are integral constants $a\_j \in \mathbb{Z}$ such that $P(k) = \sum\_j a\_j\binom{k}{j}$. (Recall $\binom{x}{j} := x(x-1)\ldots(x-(j-1))/j!$.)


**Question**: is there a simple formula for these $a\_j$?


This must've been considered before, but a cursory Googling did not lead me to anything.



Integer-valued polynomials from Pólya counting
Okay, I understand Nate's comment now and am posting this elucidation of it as a community wiki answer.


Recall that an *ordered set partition* of $X$ into $j$ blocks is an ordered tuple $(T\_1,T\_2,\ldots,T\_j)$ of non-empty subsets $\varnothing \neq T\_i \subseteq X$ that are pairwise disjoint and whose union is all of $X$. Since $G$ acts on $X$ it acts naturally on the ordered set partitions of $X$. Moreover, to any ordered set partition $(T\_1,T\_2,\ldots,T\_j)$ and choice of subset $\{y\_1 < y\_2 < \cdots < y\_j\} \subseteq Y$ of $j$ colors, we can associate the coloring $f\colon X \to Y$ determined by $f(x) = y\_i$ iff $x \in T\_i$. And two such colorings are equivalent under the action of $G$ exactly when the ordered set partitions are equivalent.


This shows
$$ P(k) = \sum\_{j\geq 1} (\textrm{$\#$ of orbits of $G$ acting on ordered set partitions of $X$ into $j$ blocks}) \cdot \binom{k}{j},$$
i.e., that
$$ a\_j = \textrm{$\#$ of orbits of $G$ acting on ordered set partitions of $X$ into $j$ blocks}.$$


This is a perfectly fine formula that shows the $a\_j$ are nonnegative integers, but it's a bit different from the Burnside's Lemma formula for $P(k)$ in that the Burnside's Lemma formula is "local" in the sense of looking at each $g\in G$ individually. I guess it would be hard to give a similar "local" formula for the $a\_j$.


