Constructive proof for the positivity of the orbit polynomial $O_d^{n,2}(q)$

Abstract

The cyclic group $C_n=\langle (12\cdots n)\rangle$ acts on the set $\binom {[n]}k$ of all $k$-subsets of $[n]$. In this action of $C_n$ the number of orbits of size $d$, for $d\mid n$, is
$$
O_d^{n,k}=\frac 1d\sum_{\frac nd\mid s\mid n}\mu\left(\frac{ds}n\right)\binom{n/s}{k/s}.
$$
Stanton and White\cite{sw} generalized the above identity to construct the orbit polynomials

$$
O_d^{n,k}(q)=\frac{1}{[d]_{q^{n/d}}}\sum_{\frac nd\mid s\mid n}
\mu\left(\frac{ds}n\right) \left[ \begin{matrix} n/s \\ k/s \end{matrix} \right]_{q^s}
$$

and conjectured that $O_d^{n,k}(q)$ have non-negative coefficients. In this paper we give a constructive proof for the positivity of coefficients of the orbit polynomial $O_d^{n,2}(q)$.