Lagmental Vicfred

Rook Polynomials Encode Nonattacking Placements by Vicfred

tags: mathematics, graph enumeration, chromatic polynomials, matroids

The coefficient r_k counts ways to place k nonattacking rooks on an allowed board. This is a compact note, but the quantifiers and hypotheses stay on the page.

Objects and notation

Graph invariants often satisfy deletion--contraction recurrences. The chromatic polynomial \(P_G(q)\) and Tutte polynomial \(T_G(x,y)\) package many counts into algebraic form.

$$ R_B(x)=\sum_{k\ge0}r_k(B)x^k $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ R_B(x)=R_{B\setminus s}(x)+xR_{B\setminus(\operatorname{row}s\cup\operatorname{col}s)}(x) $$

Push the symbols

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ B=\begin{pmatrix}1&1\\1&1\end{pmatrix}\quad\Longrightarrow\quad R_B(x)=1+4x+2x^2 $$

Structural reading

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad R_B(x)=\sum_{k\ge0}r_k(B)x^k,\\[5pt] \mathsf{C}\;&:\quad R_B(x)=R_{B\setminus s}(x)+xR_{B\setminus(\operatorname{row}s\cup\operatorname{col}s)}(x). \end{aligned} $$

A hypothesis worth keeping

Deletion--contraction must distinguish loops and bridges. Applying the generic edge recurrence to either special case changes the invariant incorrectly.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] R_B(x)=R_{B\setminus s}(x)+xR_{B\setminus(\operatorname{row}s\cup\operatorname{col}s)}(x) \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Tue 23 July 2013. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.