I recently came across Ira Gessel's slides on a theorem he says should "be considered one of the fundamental theorems of enumerative combinatorics."
The Carlitz-Scoville-Vaughan Theorem: Let $A$ be an alphabet, and let $R$ be a relation on $A$, that is, a subset of $A × A = A^2 $. Let $A^{(R)}$ be the set of words $a_1 · · · a_n$ in $A^∗$ such that $a_1 R a_2 R · · · R a_n$ . Note that the empty word 1 and all words of length one are in $A^{(R)}$ . Let $\bar{R} = A^2 − R.$ Then $$\sum_{w\in A^{(\bar{R})}}w = \left(\sum_{w\in A^{({R})}}(-1)^{l(w)}w \right)^{-1}$$ Here $l(w)$ is the length of $w,$ and we are working in the ring of formal power series in noncommuting variables.
This does look like a pretty powerful theorem; it quickly yields combinatorial interpretations to several important sequences and yet I can't find anything like this in the standard enumerative combinatorics books, which suggests I'm not looking in the right places. Where can I find other reasonably elementary expositions of this or similar results?