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.
[Math] Cyclotomic Polynomials in Combinatorics
co.combinatorics
Best Answer
For $p$ prime, the cyclotomic polynomials are $\Phi_p(x)=\frac{1-x^p}{1-x}=1+x+x^2+ ... +x^{p-1}$. 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)^{p-1}\Phi_p(1-m)=(-1)^{p-1} \frac{1-(1-m)^p}{1-(1-m)}=\frac{(m-1)^{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)=3-3m+m^2$$ $$W(m,4)=-4+6m-4m^2+m^3$$ $$W(m,5)=5-10m+10m^2-5m^3+m^4,$$
so these numbers can also be related to colored or weighted $n$-simplexes.
Relation to K-theory: 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 K-Theory, 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{1-x^{n+1}}{1-x}=\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{1-p.(x)^{n+1}}{1-p.(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 $(x-1)^k$ to obtain the binomial coefficients (A135278) $T(n,k)=\binom{n+1}{k+1}$ that counts the k-faces of a regular n-simplex, or reversed A074909 related to Martin Gardener's "bulgarian solitaire":
$$\displaystyle \frac{1-x^{n+1}}{1-x} = \sum_{k=0}^{n} \binom{n+1}{k+1} (x-1)^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.
Edit (Jul, 2020):
E) Again for $p$ prime,
$$\int_0^1\Phi_p(x) \; dx= \int_0^1\frac{x^p-1}{x-1} \; dx = H_p$$
where $H_n = St1_{n,2}/n!$ are the harmonic numbers and $St1_{n,k}$ are the Stirling numbers of the first kind. The harmonic numbers and their generalization are intimately related to the digamma function, the Riemann zeta function, and fractional calculus (MSE-Q&A and MO-Q) over the basis functions $H(x)\frac{x^n}{n!}$ (with $H(x)$, the Heaviside step function) and Dirac delta distributions $\delta^{(n)}(x)$.
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{1-x^{n+1}}{1-x}$, 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}$.