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

Jaejin Lee


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


$q$-binomial coefficient, cyclic group, action, orbit, orbit polynomial

Full Text:



G. Andrews, The Friedman-Joichi-Stanton monotonicity conjecture at primes, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 64 (2004), AMS, 9–15.

K. Drudge, On the orbits of Singer groups and their subgroups, Elec. J. Comb. 9 (2002), R15.

M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Alg. Comb. 3 (1994), 17–76.

V. Reiner, D. Stanton and D. White, The Cyclic Sieving Phenomenon, J. Combin. Theory Ser. A, 108 (1) (2004), 17–50.

B. Sagan, The cyclic sieving phenomenon: a survey, in “Surveys in Combinatorics 2011”, London Mathematical Society Lecture Note Series, Vol. 392 (2011), Cambridge University Press, Cambridge, 183–234.

D. Stanton and D. White, Sieved q-Binomial Coefficients, Preprint.

J.R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser A 68 (1994), 372–409.



  • There are currently no refbacks.

ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: