Es este formales no conmutativa de alimentación de la serie identidad conocida?

Question

Recientemente he descubierto el siguiente lindo formal no conmutativa de alimentación de la serie de la identidad: si $(x_i)_{i \in I}$ es de alguna colección finita de noncommuting variables, entonces el poder formal de la serie $$ 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$$ es el recíproco del poder formal de la serie \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*} donde la suma de los índices se entiende por rango en $I$ si no se especifica lo contrario. (Tenga en cuenta que nosotros no requieren de la $i_1,\dots,i_k$ a todo ser distintos el uno del otro; es sólo consecutivos índices de $i_j, i_{j+1}$ que se requiere para ser distintos. Así que esto no es sólo la de Newton identidades relativas poder sumas elementales simétrica polinomios, aunque parece ser un primo de estas identidades.)

Por ejemplo, si $\lvert I\rvert=n$ e $x_i=x$, esta identidad cantidades (después de la suma de la serie geométrica) a la (formal) de aserción $$ \left(1 + \frac{nx}{1-x}\right)^{-1} = 1 - \frac{nx}{1+(n-1)x}$$ lo que sigue de la escuela secundaria álgebra.

Una vez escrita, la identidad general no es difícil de probar: se multiplican los dos de la serie juntos y observar que todos los no-término constante con un coeficiente de $+1$ se cancela por un término con un coeficiente de $-1$ y viceversa. Pero estoy seguro de que una identidad básica de la que ya debe estar en la combinatoria enumerativa o la física de la literatura (EDIT: es muy implícitamente en la libre probabilidad de la literatura, que es la forma en que lo descubrí en el primer lugar, pero para mi conocimiento, no se indica explícitamente que hay). ¿Tiene un nombre, y donde se utiliza? Presumiblemente, también hay algo de natural categorification (o, al menos, un bijective o probabilística de la prueba).

Answer 1

OK, aquí está una excesivamente larga expansión de mi comentario.

De acuerdo a Goulden y Jackson Combinatoria Enumerativa (p. 76), la propiedad conmutativa de la versión de la fórmula original es debido a MacMahon, a pesar de que sólo se refieren a su libro Análisis Combinatorio y no dar una referencia más específica. Yo no era capaz de encontrar esta fórmula en MacMahon del libro, pero en las páginas 99-100 del Volumen I (Sección III, Capítulo III) MacMahon da la relacionada con la generación de la función (en notación moderna) $$\frac{1}{1-e_2 -2e_3 -3e_4-\cdots},$$ para el recuento de las alteraciones de un conjunto múltiple. Aquí $e_i$ es el $i$th primaria simétrica de la función. (MacMahon utiliza $p_i$ para la primaria simétrica de la función, que es la notación moderna de la suma de la energía simétrica de la función.) No es difícil mostrar que (con $p_i$ la suma de la energía simétrica de la función $x_1^i+x_2^i+\cdots$) tenemos $$ \frac{1}{1-p_1+p_2-\cdots} = \frac{1+e_1+e_2+\cdots}{1-e_2 -2e_3 -3e_4-\cdots}. $$ Una combinatoria interpretación de la relación entre estas dos funciones de generación ha sido dada por J. Dollhopf, I. Goulden, y C. Greene, Palabras evitando reflexiva acíclicos relación, Electrónica J. Combinat. 11, no. 2, 2004-2006.

Palabras con las letras adyacentes diferentes fueron llamados ondas por L. Carlitz, quien se dio a la (propiedad conmutativa) la generación de la función de ellos en la Enumeración de las secuencias de sube y baja: un refinamiento de la Simon Newcomb problema, Duque de Matemáticas. J. 39 (1972), 267-280. Esta es probablemente la primera aparición de la generación de la función, a menos que se esconde en algún lugar de MacMahon. (Carlitz en realidad resuelto el problema más general de recuento de palabras se eleva, cae, y niveles). Hoy en día las palabras con las letras adyacentes diferentes son generalmente llamados Smirnov palabras o Smirnov secuencias. Este término fue introducido por Goulden y Jackson; al parecer Smirnov sugirió que el problema de contar estas palabras, aunque no está claro que él no hizo nada para solucionar el problema. De acuerdo con la revisión en Matemática Revisiones de O. V. Sarmanov y V. K. Zaharov, Un problema combinatorio de N. V. Smirnov(ruso), Dokl. Akad. Nauk SSSR 176 (1967) 530-532 (no he mirado el papel real), "El difunto N. V. Smirnov plantea de manera informal el siguiente problema de la teoría de las estadísticas de orden: Dado $n$ objetos de $s+1$ tipos distintos (con $r_i$ objetos de tipo $i$, $r_1+\cdots+r_{s+1}=n$), hallar el número de maneras en que estos objetos pueden ser dispuestos en una cadena, de modo que los objetos adyacentes son siempre de distintos tipos."

Cuando se la considera como composiciones, es decir, cuando las entradas se agregan juntos, Smirnov palabras son a menudo llamados Carlitz composiciones, como lo fueron estudiadas desde este punto de vista por L. Carlitz, Restringido composiciones, Fibonacci Cuarto De Galón. 14 (1976), no. 3, 254-264. La generalización de que Darij describe en su cuarto comentario se demostró por primera vez, que yo sepa (aunque afirmó en una débil conmutativa) por Ralph Fröberg, la Determinación de una clase de Poincaré de la serie, Matemáticas. Scand. 37 (1975), 29-39 (página 35). Se ha comprobado (de forma independiente) poco después, en L. Carlitz, R. Scoville, y T. Vaughan, la Enumeración de pares de secuencias se eleva, cae, y los niveles, Manuscripta de Matemáticas. 19 (1976), 211-243 (Teorema 7.3). Su declaración de que el teorema no se parecen utilizar noncommuting variables, aunque su prueba contiene una fórmula de la ecuación (7.7)-que en su esencia es no conmutativa de la versión. (No estoy seguro de que esto realmente hace la diferencia.) Para que quede claro, voy a reformular el teorema de aquí, más o menos, aunque no exactamente, la manera Carlitz, Scoville y Vaughan estado, con algunos comentarios entre corchetes.

Deje $S$ ser un conjunto finito de objetos y deje $A$ e $B$ ser complementarios subconjuntos de $S\times S$. Deje $F_A$ ser la generación de la función de caminos [hoy íbamos a llamar palabras, o, posiblemente, las secuencias de] que evitar las relaciones de $A$. [Esto se refiere a una partición de $A$ , la cual está relacionada a sus aplicaciones del teorema, pero no es realmente relevante para el teorema.] Más específicamente, definir $$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,$$ donde, por ejemplo, la última suma se toma sobre todos los $i_1,i_2,i_3$ tal que $s_{i_1} \mathrel{B}s_{i_2}$ e $s_{i_2}\mathrel{B} s_{i_3}$. (Se usan minúsculas $s_i$'s tanto para los miembros del conjunto, $S$ y para el indeterminates [que presumiblemente son los desplazamientos] en la enumeración.) Se introduce también $$\tilde F_B = 1-\sum s_i +\sum s_{i_1}s_{i_2}-\cdots$$ donde los signos se alternan y las relaciones deben ser de $A$ en lugar de $B$.

7.3 TEOREMA. Las funciones de $F_A$ e $\tilde F_B$ están relacionados por $F_A\cdot \tilde F_B = 1$.

Ambos Fröberg y Carlitz–Scoville–Vaughhan probar esta mostrando que todos los términos en $F_A\cdot \tilde F_B$ excepto el 1 de cancelar en pares. Sin embargo, hay otra manera de demostrarlo: expandir $\tilde F_B^{-1}$como $\sum_{k=0}^\infty (1-\tilde F_B)^k$ y el uso de la inclusión-exclusión.

Carlitz, Scoville, y Vaughan, a continuación, aplicar el teorema de contar Smirnov palabras.

El Carlitz–Scoville–Vaughan teorema es uno de mis favoritos de las fórmulas de combinatoria enumerativa, y mi 1977 Tel. D. tesis tiene muchas aplicaciones de la misma. Las diapositivas de la charla que di sobre este teorema se puede encontrar aquí.