MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

At the beginning of a paper by McKay and Robinson on enumerating eulerian circuits, the authors state that the number of regular tournaments containing a directed rooted tree $T$ on vertices $v_1,\dots,v_n$ with root $v_n$ coincides with the constant term in the generating function $$\prod_{1\le j<k\le n}(x_j^{-1}x_k+x_jx_k^{-1})\,\prod_{jk\in\textrm{ edges of }T}\frac{x_jx_k^{-1}}{x_j^{-1}x_k+x_jx_k^{-1}}\,.$$ Unlike most everything else in the paper, this statement is made without justification, which makes me think that it's either a well-known result or obvious, i.e., except to me.

Could someone provide a reference or a few words to justify this claim?

share|cite|improve this question
The paper gives email addresses for each author. You could try contacting them – Chris Godsil Mar 16 '12 at 19:37
up vote 6 down vote accepted

The coefficient of $x_1^{i_1}\cdots x_n^{i_n}$ in $$\prod_{1\le j<k\le n}(x_j^{-1}x_k+x_jx_k^{-1})$$ is the number of tournaments on vertices 1, 2, ..., $n$ in which the outdegree minus the indegree of vertex $l$ is $i_l$ for each $l$. This is because each edge $\{j,k\}$ in the complete graph contributes either 1 to vertex $j$ and $-1$ to vertex $k$ or 1 to vertex $k$ and $-1$ to vertex $j$, corresponding to the factor $x_j^{-1}x_k+x_jx_k^{-1}$. So the constant term will count regular tournaments (every vertex has the same indegree as outdegree). If we require that the edge $\{j,k\}$ be directed from $j$ to $k$ then we replace the factor $x_j^{-1}x_k+x_jx_k^{-1}$ with $x_j x_k^{-1}$. (The fact that the edges form a directed rooted tree is not necessary.)

share|cite|improve this answer
Thank you, Ira. That helps very much. – Russell May Mar 16 '12 at 21:26
Thanks Ira, I couldn't have put it better myself ;). – Brendan McKay Mar 17 '12 at 1:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.