Combinatorial Interpretation

Question

In many problems of enumerative combinatorics, one finds the solution formula that involve complex roots of unity, $\cos(\frac{n \pi }{ k})$ and $\sin(\frac{n \pi }{k})$. Can someone highlight any combinatorial interpretation of such expressions. I haven't find any book or paper highlighting this except some rudiments in papers by Arthur T.Benjamin. (If this question is not appropriate for MathOverflow, I am extremely sorry.)

Answer 1

The appearance of roots of unity or $\cos(\frac{n\\pi}{k})$ and $\sin(\frac{n\pi}{k})$ in combinatorial contexts can almost always be explained through the representation theory of $\mathbb{Z}/n\mathbb Z$. The language of representation theory is avoided most of the time, and one attributes the appearance of $\cos(\frac{n\pi}{k})$'s to the appearance of circulant matrices, which have eigenvalues that are linear combinations of roots of unity, however, notice that the space of $n\times n$ circulant matrices is simply the group ring of $\mathbb Z/n \mathbb Z$.

Now, circulant matrices (or similarly manageable Toeplitz matrices) will appear in combinatorial problems whenever your objects come with a $\mathbb Z/n \mathbb Z$ action. The numbers $\cos(\frac{n\pi}{k})$ are not integers, so they will not have a combinatorial meaning themselves, but they make their way through as eigenvalues of circulant matrices. This can happen through a Fourier transform such as in Brendan McKay's answer, or through traces or determinants.

For example most formulas on the number of spanning trees, perfect matching, or closed walks on graphs with circular symmetry will contain roots of unity. Take circulant graphs, for instance, which have cyclic symmetry. These are defined by an integer $n$ and a sequence $s_1,s_2,\dots,s_k$ so that the vertex set is $\lbrace 1,2,\dots,n\rbrace$, and two vertices are connected whenever $|i-j|=s_r$ for some $1\le r\le k$. Denoting this graph by $G$ and the number of spanning trees by $\kappa(G)$, one has $$\kappa(G)=\frac{1}{n}\prod_{j=1}^{n-1}\left(2k-2\sum_{i=1}^{k}\cos(\frac{2\pi s_i j}{n})\right).$$

Now, as I mentioned earlier, circulant matrices and $\mathbb Z/n\mathbb Z$ actions don't exactly tell the whole story, because there are other nice Toeplitz matrices (or combinations of these) with eigenvalues being linear combinations of roots of unity. Some of the simplest examples are grid graphs. My favourite example to illustrate this is Kasteleyn's formula for counting domino tilings of an $n\times m$ grid. This number is $$\prod_{j=1}^{m}\prod_{k=1}^n \left(4\cos^2 \frac{\pi j}{m+1}+4\cos^2 \frac{\pi k}{n+1}\right)^{1/4}.$$

And of course there are appearances of roots of unity which happen in situations with a number theoretic flavour, such as Gauss sums or the Möbius function, but here the roots of unity usually don't make it to the enumeration formula as they usually cancel on the way, or are hidden behind expressions like Legendre symbols. :)

Answer 2

If you have a polynomial or sufficiently convergent power series $f(x)$, and you sum it over $x$ being each of the $k$-th roots of unity, then you get $k$ times the sum of the coefficients of the powers of $x$ that are multiples of $k$. The simplest case is that $f(1)+f(-1)$ is twice the sum of the coefficients of the even powers. This is one way that items like $e^{-2ij\pi/k}$ or its real and imaginary parts can get into a formula.

http://en.wikipedia.org/wiki/Series_multisection gives the general formula.