I am searching for a combinatorial significance of cyclotomic polynomials. The only examples I got are a paper by Neville Robbins http://www.emis.de/journals/INTEGERS/papers/a6/a6.pdf and two recent papers by Gregg Musiker and Victor Reiner http://arxiv.org/PS_cache/arxiv/pdf/1012/1012.1844v2.pdf and http://combinatorics.cis.strath.ac.uk/fpsac2011/proceedings/dmAO0161.pdf but these do not essentially give a clear picture. I am interested in examples that relate cyclotomic polynomials to foundations of combinatorics (if these exist) or if someone can give a direct combinatorial interpretation of coefficients of cylotomic polynomials that'll be quite helpful.

For $p$ prime, the cyclotomic polynomials are $\Phi_p(x)=\frac{1x^p}{1x}=1+x+x^2+ ... +x^{p1}$. I've seen connections to combinatorics of these polynomials other than the ones noted in the other answers: A) When evaluated at negative integers, the polynomials give $W(m,p)$ the number of walks of length $p$ between any two distinct vertices of the complete graph $K_m$ for $m>2$: $$W(m,p)=(1)^{p1}\Phi_p(1m)=(1)^{p1} \frac{1(1m)^p}{1(1m)}=\frac{(m1)^{p}(1)^p}{m}.$$ For $K_3$, see the Jacobsthal sequence OEIS A001045; for $K_4$, A015518; for $K_5$, A015521; for $K_6$, A015531; for $K_7$, A015540; ... . The $W(m,p)$, ignoring primality, are the signed rows of A135278, alluded to in C below: $$W(m,1)=1$$ $$W(m,2)=2+m$$ $$W(m,3)=33m+m^2$$ $$W(m,4)=4+6m4m^2+m^3$$ $$W(m,5)=510m+10m^25m^3+m^4,$$ so these numbers can also be related to colored or weighted $n$simplexes. Relation to Ktheory: The unsigned matrix $W$ above acting on the column vector $(0,d,d^2,d^3,...)$ generates the Euler classes for a hypersurface of degree $d$ in $CP^n$. (Cf. Dugger, A Geometric Introduction to KTheory, p. 168, also A104712, A111492, and A238363). B) When the polynomials are expanded as sums of the sequence $(1+x)^k$ rather than $x^k$, many of the coefficients ($T(n,k)$ below) have combinatoric interpretations as presented for the first few columns of A239473 (signed A059260). Take your pick, but I don't see an overarching interpretation across columns (Whitney numbers for ?). Hidden in the simple expression of the polynomials is an underlying relation between the partial sums of a sequence of polynomials and their binomial transforms, that is independent of any interpretation of the cyclotomic polynomials: $$\displaystyle \sum_{k=0}^{n} x^k = \sum_{k=0}^{n} T(n,k) (1+x)^k = \frac{1x^{n+1}}{1x}=\Phi_{n+1}(x),$$ for $n+1$ an odd prime, is a specific example of $$\displaystyle \sum_{k=0}^{n} p_k(x) = \sum_{k=0}^{n} T(n,k) (1+p.(x))^k = \frac{1p.(x)^{n+1}}{1p.(x)},$$ umbrally, i.e., $\displaystyle (1+p.(x))^k=\sum_{j=0}^{k} \binom{k}{j}p_j(x)$. Furthermore (within this extended umbral presentation), the Wiki article simplex relates the inequality $\sum_{k=0}^{n} t_k<1$ to an $n$simplex as the corner of the $n$cube and the equality $\sum_{k=0}^{n+1} x_k=1$ to the algebraic standard $n$simplex in algebraic geometry. C) Simply expand the polynomials in terms of $(x1)^k$ to obtain the binomial coefficients (A135278) $T(n,k)=\binom{n+1}{k+1}$ that counts the kfaces of a regular nsimplex, or reversed A074909 related to Martin Gardener's "bulgarian solitaire": $$\displaystyle \frac{1x^{n+1}}{1x} = \sum_{k=0}^{n} \binom{n+1}{k+1} (x1)^k=\Phi_{n+1}(x),$$ or, $$\displaystyle \Phi_{n+1}(x+1)=\sum_{k=0}^{n} \binom{n+1}{k+1} x^k=\frac{(1+x)^{n+1}1}{x}$$ for $n+1$ an odd prime. These are also the Whitney numbers (except for the first) for any trees with n+1 vertices, making another contact with Rota's papers. D) For connections to weights of specific types of weighted Motzkin paths, see The Matrix Ansatz, Orthogonal Polynomials, and Permutations (pg. 4), or Matrix Ansatz Lattice Paths, and Rook Polynomials (pg. 40), by Sylvie Corteel et al. Added Oct 2014 A tangential note: The relation between products of $\Phi_m(x)$ and the Coxeter polynomial for $A_n$, $f_n(x)=\frac{1x^{n+1}}{1x}$, for $n$ not prime, are given on page 19 of "On the characteristic polynomials of Cartan matrices and the Chebyshev polynomials" by Pantelis Damianou. E.g., $$f_7(x)=\Phi_2(x)\Phi_4(x)\Phi_8(x).$$ More generally, Damianou reveals a relationship between products of $\Phi_m(x)$ and the characteristic polynomials of the Cartan matrix of the simple Lie algebras expressed in terms of the Chebyshev polynomials $U$ and $T$, which lead to interesting combinatorics in many entries of the OEIS, e.g., A119900 whose columns are the unsigned rows of A053122. For $A_n$, he presents the associated polynomial $Q_n(x)=f_n(x^2)=e^{i n \theta}U_n(cos(\theta))$ with $x=e^{i \theta}$. 


I don't know that this is foundational, but see 


Ethan Coven and Aaron Meyerowitz have a paper "Tiling the integers with translates of one finite set" (cited recently on Terry Tao's blog) about tiling the integers with a single prototile. That is, they are looking for conditions under which subsets of the integers, $A$ say, such that there are $n_1,n_2,n_3,...$ such that $n_1+A$, $n_2+A$, $\ldots$ disjointly cover all of the integers. In Coven and Meyerowitz's paper, two conditions are given directly in terms of cyclotomic polynomials for $A$ to have this property. If both conditions are satisfied, then $A$ tiles the integers. On the other hand, if $A$ tiles the integers, then one of the conditions is shown to be satisfied. They conjecture that the second condition must also be satisfied. 


http://math.ecnu.edu.cn/~jwguo/maths/congruence.pdf Here, the cyclotomic polynomials appear in an identity involving qbinomial coefficients. 


The following may be helpful to you: Coefficients of Cyclotomic Polynomials  Jordan Bell Memoirs of the AMS  Number 510  On the Coefficients of Cyclotomic Polynomials  Gennady Bachman 


My first thought was the pair of papers by Musiker and Reiner that you mention. Another paper involving combinatorics and cyclotomic polynomials is the following. Cyclotomic factors of the descent set polynomial Denis Chebikin, Richard Ehrenborg, Pavlo Pylyavskyy, Margaret Readdy Journal of Combinatorial Theory, Series A Volume 116, Issue 2, February 2009, Pages 247264 


I remember seeing in my student days in constructions of Block Designs, or more specifically, mutually orthogonal latin squares, finite fields play a crucial role and cyclotomic polynomials enter there. Sorry I cannot be any more specific. 

