Extraña identidad factorial

Question

El siguiente parece ser cierto. \begin{align*} n! &= \sum_{k=0}^n \sum_{j=0}^{\lfloor\frac{k}{3}\rfloor}\sum_{i=0}^{k-3j} (-1)^{i+j}\binom{k-2j}{i,j,k-i-3j}\frac{(n-i-2j)!}{(n-k)!}\\ &\qquad +\sum_{k=0}^n\sum_{j=1}^{\lfloor\frac{k+1}{3}\rfloor}\sum_{i=0}^{k+1-3j} (-1)^{i+j}\binom{k-2j}{i,j-1,k+1-i-3j}\frac{(n-i-2j)!}{(n-k)!} \end{align*}

Yo he verificado hasta $n=100$.

En teoría, debería sucumbir a un martillo de Zeilberger Wilf lo suficientemente grande, pero no poseo tal martillo.

He adjuntado una biyectiva prueba de ello (el writeup necesita trabajo, pero estoy seguro de que el subyacente bijection es sonido), pero todavía mucho quisiera una prueba algebraica.

Answer 1

Combinatoria Definición

Una $(n,k)$ parcial de permutación es una palabra de longitud $k$ hechos de los números en $[n]$ sin repeticiones. Alternativamente es una inyección que se $\sigma$$[k]$$[n]$. Estamos interesados en el conjunto de $G_{n,k}$ $(n,k)$ que satisfacen la siguiente condición.

Si establecemos $\sigma(0)=n+1$ (prefijo de la palabra con $n+1$), a continuación, el siguiente se cumplen dos condiciones.

1. Para todos $0\le i \le k-1$, $\sigma(i+1) \ne \sigma(i) - 1$
2. Para todos $0\le i \le k-2$, $\sigma(i+1) \ne \sigma(i) - 2$ o $\sigma(i+2) \ne \sigma(i) - 1$.

Estos son el equivalente a decir que el parcial de permutación no contiene $a$ $a-1$ consecutivamente y no contiene $a$, $a-2$, y $a-1$, consecutivamente.

Por ejemplo \begin{align*} G_{3,0} &= \{\epsilon\}\\ G_{3,1} &= \{1, 2\}\\ G_{3,2} &= \{12, 13\}\\ G_{3,3} &= \{123\} \end{align*}

y \begin{align*} G_{4,0} &= \{\epsilon\}\\ G_{4,1} &= \{1, 2, 3\}\\ G_{4,2} &= \{12, 13, 14, 23, 24, 31\}\\ G_{4,3} &= \{123, 124, 134, 142, 231, 234, 241, 314\}\\ G_{4,4} &= \{1234, 1342, 2314, 2341, 2413, 3142\} \end{align*}

Resulta que la conjetura es equivalente a $$n! = \sum_{k=0}^n |G_{n,k}|$$

Primero vamos a mostrar que la pregunta original cuenta los elementos en $\bigcup_{k=0}^n G_{n,k}$ por la inclusión-exclusión, a continuación, vamos a exponer un bijection entre las permutaciones de $[n]$$\bigcup_{k=0}^n G_{n,k}$, con lo que se establece el resultado. El bijection es más complicado de lo que uno puede desear, y un directo prueba algebraica sería muy bienvenido.

Contando con la inclusión-exclusión

Un parcial de permutación es excluido de la $G_{n,k}$ si tiene o $a$ $a+1$ consecutivamente (vamos a llamar a estas dos bloques) o se ha $a$, $a-2$, $a-1$ consecutivamente (vamos a llamar a estos tres bloques). Desde cada uno de los dos bloques, en efecto, asigna un símbolo de la palabra, y cada uno de los tres bloques, en efecto, asigna dos símbolos, hay $(n-i-2j)!/(k-i-2j)!$ $(n,k)$ parcial de permutaciones $i$ dado en dos bloques y $j$ dado tres bloques tan largo como es posible que un parcial de permutación para tener esa configuración.

Dos a dos cuadras se pueden superponer en una posición, y una de dos cuadras que pueden superponerse a la primera celda de un bloque de tres, pero no la última. Podemos representar la ubicación de un bloque de dos por una célula de domino que representa la ubicación de su primer celular, y la ubicación de una de tres bloques de tres células de domino. Por lo que el número admisible de las configuraciones de $i$ dos bloques y $j$ tres bloques es el número de maneras de colocar a $i$ de una célula de dominos y $j$ celulares de tres fichas de dominó en un $k+1\times 1$ celda de la tabla así que la última celda no contienen una celda de domino (desde la celda de una domino representa la primera celda de dos bloques, uno de células de domino en la última celda se tiene el bloque de dos a caer por el borde parcial de la permutación).

Podemos contar con estas considerando los dos casos 1. La última celda está vacía, esto es sólo el número de maneras de colocar a $i$ una celda de dominos y $j$ celulares de tres fichas de dominó en un $k$ celda de la junta. Este es $$\binom{k-2j}{i,j,k-i-3j}.$$ 2. La última celda que contiene el final de una de tres células de domino, este es el número de maneras de colocar a $i$ una celda de dominos y $j-1$ celulares de tres fichas de dominó en un $k-2$ celda de la junta. Esto es $$\binom{k-2j}{i,j-1,k+1-i-3j}.$$

Así que el uso de la inclusión-exclusión que podemos contar el número de elementos en $G_{n,k}$

\begin{align*} |G_{n,k}| &= \sum_{j=0}^{\lfloor\frac{k}{3}\rfloor}\sum_{i=0}^{k-3j} (-1)^{i+j}\binom{k-2j}{i,j,k-i-3j}\frac{(n-i-2j)!}{(n-k)!}\\ &\qquad +\sum_{j=1}^{\lfloor\frac{k+1}{3}\rfloor}\sum_{i=0}^{k+1-3j} (-1)^{i+j}\binom{k-2j}{i,j-1,k+1-i-3j}\frac{(n-i-2j)!}{(n-k)!} \end{align*}

Sumando esto a través de todos los valores de $k$ nos da la pregunta original.

Un bijection con permutaciones

Vamos a definir dos pasos recursivos operación $\phi$ que se lleva un $(n,k)$ parcial permutación $sigma$ y una posición $i$ (un entero en [k]) y devuelve una modificación parcial de la permutación.

1. Si $\sigma(i + 1) = \sigma(i) - 1$ luego intercambiar los símbolos $\sigma(i)$ $\sigma(i+1)$ y regresar $\sigma$.
2. Si $\sigma(i+1) = \sigma(i)-2$$\sigma(i+2) = \sigma(i) - 1$, a continuación, girar los tres $\sigma(i)\leftarrow\sigma(i+1)\leftarrow\sigma(i+2)\leftarrow\sigma(i)$ y regresar $\phi(\sigma,i+2)$

Ahora podemos definir una operación $\pi$ que toma un $(n,k)$, $k<n$ parcial de permutación $\sigma$ $(n,k+1)$ parcial permutación de la siguiente manera 1. Deje $a$ ser el miembro más grande de $[n]$ no $\sigma$. 2. Si $a=n$, entonces el prefijo $\sigma$ $a$ (añadir al principio), de lo contrario agregar $a$ $\sigma$inmediatamente después de la $a+1$. 3. Deje $i$ el índice de $a$. 4. Regresar $\phi(\sigma,i)$

Tenga en cuenta que si $\sigma$ no tiene un bloque de dos o tres cuadras de que los miembros más pequeños de $a$, el más pequeño bloque en $\pi(\sigma)$ es el bloque de dos $a+1,a$ o de los tres bloque$a+1, a-1, a$, por lo que podemos identificar que el símbolo fue añadido por encontrar el bloque con el más pequeño de la mano derecha elemento.

También podemos definir una operación $\zeta$ que se lleva un $(n,k)$ parcial de permutación que contiene un bloque de dos o tres cuadras y devuelve un $(n,k-1)$ parcial de permutación.

1. Deje $a$ ser el valor más pequeño que ocurren al final de un bloque de dos o tres cuadras de la
2. Si $a$ está inmediatamente precedida por $a+1$ eliminar $a$ y devolver el parcial resultante de permutación.
3. Deje $i$ ser uno menos que el índice de $a$
4. Retire $a$ $\sigma$ y regresar $\phi(\sigma,i)$

De nuevo, tenga en cuenta que el bloque que contiene a $a$ ha sido perturbado

Ahora podemos describir nuestra bijection:

Para tomar un miembro de $G_{n,k}$ y crear una permutación de $[n]$ aplicar $\pi$ $n-k$ veces. Para tomar una permutación de $[n]$ y consiga un miembro de $G_{n,k}$ algunos $k$ aplican $\zeta$ hasta que no hay más de dos bloques o tres bloques.

Por ejemplo, para $n = 4$:

\begin{align*} 1234 &\Leftrightarrow 1234\\ 1243 &\Leftrightarrow 124\\ 1324 &\Leftrightarrow 134\\ 1342 &\Leftrightarrow 1342\\ 1423 &\Leftrightarrow 142\\ 1432 &\Leftrightarrow 14\\ 2134 &\Leftrightarrow 234\\ 2143 &\Leftrightarrow 24\\ 2314 &\Leftrightarrow 2314\\ 2341 &\Leftrightarrow 2341\\ 2413 &\Leftrightarrow 2413\\ 2431 &\Leftrightarrow 241\\ 3124 &\Leftrightarrow 314\\ 3142 &\Leftrightarrow 3142\\ 3214 &\Leftrightarrow 3\\ 3241 &\Leftrightarrow 31\\ 3412 &\Leftrightarrow 231\\ 3421 &\Leftrightarrow 23\\ 4123 &\Leftrightarrow 123\\ 4132 &\Leftrightarrow 13\\ 4213 &\Leftrightarrow 2\\ 4231 &\Leftrightarrow 12\\ 4312 &\Leftrightarrow 1\\ 4321 &\Leftrightarrow \epsilon \end{align*}

Tenemos que mostrar que si $\sigma$ $(n,k)$ parcial de permutación que no contengan $a$, pero que contiene todos los de $a+1,\ldots,n$ que no tiene cualquiera de los dos bloques o tres bloques que contienen los valores de menos de $a$$\zeta(\pi(\sigma))=\sigma$, como si cada solicitud de $\zeta$ deshace una aplicación de $\pi$ vemos que las dos operaciones son inversos.

Si después de la adición de $a$, aplicando $\phi$ no hace nada, entonces $a$ es precedido por $a+1$ $\zeta$ sólo elimina $a$ darnos nuestro original parcial de permutación.

Si luego de agregar $a$, $\phi$ swaps $a$$a-1$, a continuación, después de la eliminación de $a$ conseguimos que nuestro original permutación de la espalda, y la aplicación de $\phi$ no hace nada (Si no pudiera, entonces nuestro original parcial de permutación hubiera contenido un bloque que contenga $a-1$ contradice nuestra suposición.)

Así, sólo tenemos que considerar el caso de que después de la adición de $a$, $\phi$ gira tres elementos más de una vez y luego intercambia dos elementos y se detiene, o simplemente se detiene.

Si luego de agregar $a$, $\phi$ gira a $m$ triples y se detiene, a continuación, después de la adición de $a$ que hemos tenido \begin{align*} \sigma(i) &= a & \\ \sigma(i+2j-1) &= a-2j \qquad &\text{for %#%#% }\\ \sigma(i+2j) &= a + 1 - 2j \qquad &\text{for %#%#% } \end{align*} y $0<j\le m$ $0<j\le m$ o $\sigma(i+2m+1)\ne a-2m-1$. Después de aplicar el $\sigma(i+2m+1)\ne a-2m-2$ hemos

\begin{align*} \sigma(i) &= a-1 & \\ \sigma(i+2j-1) &= a-2j+2 \qquad &\text{for %#%#% }\\ \sigma(i+2j) &= a - 1 - 2j \qquad &\text{for %#%#% } \end{align*}

Ahora bien, si quitamos la una de la posición $\sigma(i+2m+2)\ne a-2m-1$ y $\phi$ comenzando en la posición $0<j\le m$ realizamos $0<j\le m$ rotaciones y un final de intercambio.

El resto de los casos donde $i+1$ realiza $\phi$ rotaciones y una swap procede de manera similar y se deshace por $i$ rotaciones.

Libre parcialmente conmutativa de la izquierda regular bandas

Esta identidad fue traído a mi atención como una conjetura de Franco Saliola que el tamaño de la de un libre parcialmente conmutativa de la izquierda regular de la banda de un $m-1$ ciclo $\pi$$m$. Como un conjunto, el libre parcialmente conmutativa de la izquierda regular de la banda de un $m$ ciclo puede ser considerado como el conjunto de de clases de equivalencia parcial permutaciones de $n$ donde dos parciales permutaciones son equvalent si uno puede ser alcanzado a partir de la otra mediante el intercambio de símbolos adyacentes si difieren por $n>3$.

Dejando de lado la palabra vacía, es fácil ver que un símbolo se puede mover en la mayoría de las dos posiciones a la izquierda o a la derecha, ya que tiene sólo dos vecinos en el cíclico gráfico, así que para $n!+1$ lo suficientemente grande (5) de cada clase de equivalencia tiene un lexicográficamente más hacia la izquierda del elemento. Si se explotan las $n$-simetría podemos girar la palabra, para que la primera letra es $[n]$. Esta palabra no tiene dos bloques o tres bloques, bien podría ser trasladado a una más ccw palabra (en un solo paso para un bloque de dos, o dos pasos para una de tres bloques), y todos los bloques de ese tipo son las rotaciones de la mayoría de ccw palabras.