# Combinatorial Interpretation

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

• So are you asking for examples of combinatorial problems whose solutions involve $\cos(\frac{n \pi}{k}), \sin (\frac{n \pi}{k})$? – Vinoth Aug 23 '11 at 12:38
• The fact that roots of unity appear alongside $\cos(n\pi/k)$ and $\sin(n\pi/k)$ is a consequence of Euler's formula: $e^{i\theta} = \cos \theta + i \sin \theta$. As far as combinatorial interpretations, could you be more specific? – Shaun Ault Aug 23 '11 at 12:39
• Also note De Moivre's Formula may provide a link with the binomial coefficients if one expands the lhs: $(\cos \theta + i \sin \theta)^n = \cos n\theta + i \sin n\theta$. – Shaun Ault Aug 23 '11 at 12:42
• @Vinoth I have a couple of examples but some more will be helpful in better understanding. @Shaun Alt By combinatorial interpretation means like is it counting some general structure that pops out so often in combinatorial problems. Like $\binom{n}{k}$ counts the number of k-subsets of an n-set. – UmerScientist Aug 25 '11 at 0:47

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

• "The numbers $\cos(n\pi/k)$ are not real..."; maybe you mean, they are not integers? – Gerry Myerson Aug 24 '11 at 5:33
• @ Gjergji Zaimi Thanks for explanation. It was quite helpful. But I still need some other interpretations. May be its the only one.... But thanks again. – UmerScientist Aug 25 '11 at 0:57
• a "\" is surplus in the first row. I can't edit it because of characters limit. :) – MR_BD Aug 31 '16 at 13:12

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.

• @Brendan McKay Thanks but this is one of the instances when they pops out and further it does not lead to some combinatorial structure but just an algebraic technique. Nevertheless the answer was helpful. – UmerScientist Aug 25 '11 at 0:50