The Generating Function is Rational for the Number of Rooted Forests in a Circulant Graph

We consider the generating function $$\Phi $$ for the number $$f_{\Gamma }(n) $$ of rooted spanning forests in the circulant graph $$\Gamma $$ , where $$\Phi (x)= \sum _{n=1}^{\infty } f_{\Gamma }(n) x^n$$ and either $$\Gamma =C_n(s_1,s_2,\dots ,s_k) $$ or $$\Gamma =C_{2n}(s_1,s_2,\dots ,s_k,n) $$ . We show that $$\Phi $$ is a rational function with integer coefficients that satisfies the condition $$\Phi (x)=-\Phi (1/x) $$ . We illustrate this result by a series of examples.

Перевод пока недоступен