Is this formal noncommutative power series identity known?

Question

I recently discovered the following cute formal noncommutative power series identity: if $(x_i)_{i \in I}$ is some finite collection of noncommuting variables, then the formal power series $$ 1 + \sum_{m=1}^\infty \sum_i x_i^m = 1 + \sum_i x_i+ \sum_i x_i^2 + \sum_i x_i^3 + \dotsb$$ is the reciprocal of the formal power series \begin{multline*} \sum_{k=0}^\infty (-1)^k \sum_{i_1 \neq \dotsb \neq i_k} x_{i_1} \dotsb x_{i_k} \\ = 1 - \sum_i x_i + \sum_{i \neq j} x_i x_j - \sum_{i \neq j \neq k} x_i x_j x_k + \dotsb \end{multline*} where summation indices are understood to range in $I$ if not otherwise specified. (Note that we do not require the $i_1,\dots,i_k$ to all be distinct from each other; it is only consecutive indices $i_j, i_{j+1}$ that are required to be distinct. So this isn't just the Newton identities relating power sums with elementary symmetric polynomials, though it seems to be a cousin of these identities.)

For instance, if $\lvert I\rvert=n$ and $x_i=x$, this identity amounts (after summing the geometric series) to the (formal) assertion $$ \left(1 + \frac{nx}{1-x}\right)^{-1} = 1 - \frac{nx}{1+(n-1)x}$$ which follows from high school algebra.

Once written down, the general identity is not hard to prove: multiply the two power series together and observe that every non-constant term with a coefficient of $+1$ is cancelled by a term with a coefficient of $-1$ and vice versa. But I am certain that an identity this basic must already be in either the enumerative combinatorics or the physics literature (EDIT: it is very implicitly in the free probability literature, which is how I discovered it in the first place, but to my knowledge it is not explicitly stated there). Does it have a name, and where is it used? Presumably there is also some natural categorification (or at least a bijective or probabilistic proof).

Answer 1

OK, here's an excessively long expansion of my comment.

According to Goulden and Jackson's Enumerative Combinatorics (p. 76), the commutative version of the original formula is due to MacMahon, though they only refer to his book Combinatory Analysis and don't give a more specific reference. I was not able to find this formula in MacMahon's book, but on pages 99–100 of Volume I (Section III, Chapter III) MacMahon gives the related generating function (in modern notation) $$\frac{1}{1-e_2 -2e_3 -3e_4-\cdots},$$ for counting derangements of a multiset. Here $e_i$ is the $i$th elementary symmetric function. (MacMahon uses $p_i$ for the elementary symmetric function, which is the modern notation for the power sum symmetric function.) It's not hard to show that (with $p_i$ the power sum symmetric function $x_1^i+x_2^i+\cdots$) we have $$ \frac{1}{1-p_1+p_2-\cdots} = \frac{1+e_1+e_2+\cdots}{1-e_2 -2e_3 -3e_4-\cdots}. $$ A combinatorial interpretation of the connection between these two generating functions has been given by J. Dollhopf, I. Goulden, and C. Greene, Words avoiding a reflexive acyclic relation, Electronic J. Combin. 11, no. 2, 2004–2006.

Words with adjacent letters different were called waves by L. Carlitz, who gave the (commutative) generating function for them in Enumeration of sequences by rises and falls: a refinement of the Simon Newcomb problem, Duke Math. J. 39 (1972), 267–280. This is probably the first appearance of the generating function, unless it's hiding somewhere in MacMahon. (Carlitz actually solved the more general problem of counting words by rises, falls, and levels.) Nowadays words with adjacent letters different are usually called Smirnov words or Smirnov sequences. This term was introduced by Goulden and Jackson; apparently Smirnov suggested the problem of counting these words though it's not clear that he did anything to solve the problem. According to the review in Mathematical Reviews of O. V. Sarmanov and V. K. Zaharov, A combinatorial problem of N. V. Smirnov (Russian), Dokl. Akad. Nauk SSSR 176 (1967) 530–532 (I didn't look up the actual paper), “The late N. V. Smirnov posed informally the following problem from the theory of order statistics: Given $n$ objects of $s+1$ distinct types (with $r_i$ objects of type $i$, $r_1+\cdots+r_{s+1}=n$), find the number of ways these objects may be arranged in a chain, so that adjacent objects are always of distinct types.”

When considered as compositions, i.e., when the entries are added together, Smirnov words are often called Carlitz compositions, as they were studied from this point of view by L. Carlitz, Restricted compositions, Fibonacci Quart. 14 (1976), no. 3, 254–264. The generalization that Darij describes in his fourth comment was first proved, as far as I know (though stated in a weaker commutative form) by Ralph Fröberg, Determination of a class of Poincaré series, Math. Scand. 37 (1975), 29–39 (page 35). It was proved (independently) shortly thereafter in L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs of sequences by rises, falls, and levels, Manuscripta Math. 19 (1976), 211–243 (Theorem 7.3). Their statement of the theorem doesn't seem to use noncommuting variables, though their proof contains a formula—equation (7.7)—which is essentially the noncommutative version. (I am not sure that this really makes any difference.) Just to be clear, I'll restate the theorem here, more or less, though not exactly, the way Carlitz, Scoville and Vaughan state it, with some comments in brackets.

Let $S$ be a finite set of objects and let $A$ and $B$ be complementary subsets of $S\times S$. Let $F_A$ be the generating function for all paths [today we would call them words, or possibly sequences] which avoid relations from $A$. [This is referring to a partition of $A$ which is related to their applications of the theorem, but is not really relevant to the theorem.] More specifically, define $$F_A = 1+\sum s_{i_1}+\sum s_{i_1}s_{i_2}+\sum s_{i_1}s_{i_2}s_{i_3}+\cdots,$$ where, for example, the last sum is taken over all $i_1,i_2,i_3$ such that $s_{i_1} \mathrel{B}s_{i_2}$ and $s_{i_2}\mathrel{B} s_{i_3}$. (We use lower-case $s_i$'s for both the members of the set $S$ and for the indeterminates [which are presumably commuting] in the enumeration.) We also introduce $$\tilde F_B = 1-\sum s_i +\sum s_{i_1}s_{i_2}-\cdots$$ where the signs alternate and the relations must be from $A$ instead of $B$.

7.3 THEOREM. The functions $F_A$ and $\tilde F_B$ are related by $F_A\cdot \tilde F_B = 1$.

Both Fröberg and Carlitz–Scoville–Vaughhan prove this by showing that all the terms in $F_A\cdot \tilde F_B$ except 1 cancel in pairs. However there is another way to prove it: expand $\tilde F_B^{-1}$ as $\sum_{k=0}^\infty (1-\tilde F_B)^k$ and use inclusion-exclusion.

Carlitz, Scoville, and Vaughan then apply the theorem to counting Smirnov words.

The Carlitz–Scoville–Vaughan theorem is one of my favorite formulas in enumerative combinatorics, and my 1977 Ph.D. thesis has many applications of it. The slides from a talk I gave about this theorem can be found here.