4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I think $a_j$ is the number of equivalence relations with exactly $j$ classes on $X$, up to the action of $G$. $\endgroup$
    – Nate
    Commented Jan 31, 2022 at 15:59
  • $\begingroup$ @Nate: I'm trying to understand your comment. Let $G=\langle (1,2,3,4) \rangle$ act on $X = \{1,2,3,4\}$ in the usual way. Then the polynomial is $\frac{1}{4}(k^4+k^2+2k)=6 \binom{k}{4} + 9\binom{k}{3} + 4 \binom{k}{2} + \binom{k}{1}$. But there are not $6$ equivalence relations with $4$ classes on $X$, right? Maybe you intend "labeled equivalence relations"? $\endgroup$
    – Sam Hopkins
    Commented Jan 31, 2022 at 17:18

1 Answer 1

Reset to default
8
$\begingroup$

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$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ahh yea I realized this ordering issue when I was at lunch just now and was going to comment but you beat me to it. The equivalence relation formulation I mentioned instead gives you the coefficients for expanding it in terms of permutation polynomials $j! \binom{x}{j}$. $\endgroup$
    – Nate
    Commented Jan 31, 2022 at 18:22
  • 1
    $\begingroup$ @Nate I don't think that expansion has integer coefficients always. $a_j$ is not necessarily a multiple of $j!$. You get some kind of non-freeness problems with your action. $\endgroup$
    – darij grinberg
    Commented Jan 31, 2022 at 18:24
  • $\begingroup$ @darijgrinberg Oh yea, good point. $\endgroup$
    – Nate
    Commented Jan 31, 2022 at 18:28
  • $\begingroup$ This does make me wonder if there is a way to understand the basic Pólya counting results in terms of the quotient of the ordered partition lattice by $G$, and maybe Möbius inversion on this poset... $\endgroup$
    – Sam Hopkins
    Commented Jan 31, 2022 at 22:51
  • 2
    $\begingroup$ @SamHopkins: this is essentially what appears in Section 5.3 of Combinatorics: The Rota Way by Kung, Rota, and Yan. $\endgroup$
    – Richard Stanley
    Commented Jan 31, 2022 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .