Permutación alternada

En matemáticas combinatorias , una permutación alternada (o permutación en zigzag ) del conjunto {1, 2, 3, ..., n } es una permutación (ordenación) de esos números de tal manera que cada elemento es alternativamente mayor o menor que el anterior. Por ejemplo, las cinco permutaciones alternadas de {1, 2, 3, 4} son:

• 1, 3, 2, 4 porque 1 < 3 > 2 < 4,              
• 1, 4, 2, 3 porque 1 < 4 > 2 < 3,              
• 2, 3, 1, 4 porque 2 < 3 > 1 < 4,              
• 2, 4, 1, 3 porque 2 < 4 > 1 < 3, y              
• 3, 4, 1, 2 porque 3 < 4 > 1 < 2.              

Este tipo de permutación fue estudiada por primera vez por Désiré André en el siglo XIX. ^{[ 1 ]}

Diferentes autores utilizan el término permutación alternada de forma ligeramente distinta: algunos exigen que el segundo elemento de una permutación alternada sea mayor que el primero (como en los ejemplos anteriores), otros exigen que la alternancia se invierta (de modo que el segundo elemento sea menor que el primero, luego el tercero mayor que el segundo, y así sucesivamente), mientras que otros denominan a ambos tipos permutación alternada.

La determinación del número A _n de permutaciones alternas del conjunto {1, ..., n } se conoce como el problema de André . Los números A _n se denominan números de Euler , números en zigzag o números ascendentes/descendentes . Cuando n es par, el número A _n se conoce como número secante , mientras que si n es impar se conoce como número tangente . Estos últimos nombres provienen del estudio de la función generadora de la secuencia.

Se dice que una permutación c ₁ , ..., c _n es alternante si sus entradas suben y bajan alternativamente. Por lo tanto, cada entrada, excepto la primera y la última, debe ser mayor o menor que sus dos vecinas. Algunos autores usan el término alternante para referirse solo a las permutaciones "ascendentes-descendentes" para las cuales c ₁ < c ₂ > c ₃ < ... , llamando a las permutaciones "descendentes-ascendentes" que satisfacen c ₁ > c ₂ < c ₃ > ... alternantes inversas . Otros autores invierten esta convención, o usan la palabra "alternante" para referirse tanto a las permutaciones ascendentes-descendentes como a las descendentes-ascendentes.

Existe una correspondencia simple uno a uno entre las permutaciones de abajo hacia arriba y de arriba hacia abajo: reemplazar cada entrada c _i con n + 1 - c _i invierte el orden relativo de las entradas.

Por convención, en cualquier esquema de nomenclatura, las permutaciones únicas de longitud 0 (la permutación del conjunto vacío ) y 1 (la permutación que consta de una sola entrada 1) se consideran alternas.

La determinación del número A _n de permutaciones alternas del conjunto {1, ..., n } se denomina problema de André . Los números A _n se conocen con diversos nombres, como números de Euler , números en zigzag , números ascendentes/descendentes o combinaciones de estos. El nombre de números de Euler, en particular, se utiliza a veces para una secuencia estrechamente relacionada. Los primeros valores de A _n son 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (secuencia A000111 en la OEIS ) .

Estos números satisfacen una recurrencia simple, similar a la de los números de Catalan : al dividir el conjunto de permutaciones alternas (tanto descendentes como ascendentes) del conjunto {  1,  2,  3,  ..., n , n + 1 } según la posición k de la entrada más grande n + 1 , se puede demostrar que     

${\displaystyle 2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{nk}}$

para todo n ≥ 1. André (1881) utilizó esta recurrencia para dar una ecuación diferencial que satisface la función generatriz exponencial.

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}}$

para la secuencia A _n . De hecho, la recurrencia da:

${\displaystyle 2\sum _{n\geq 1}A_{n+1}{\frac {x^{n+1}}{(n+1)!}}=\sum _{n\geq 1}\sum _{k=0}^{n}{\frac {A_{k}}{k!}}{\frac {A_{n-k}}{(n-k)!}}{\frac {x^{n+1}}{n+1}}=\int \left(\sum _{k\geq 0}A_{k}{\frac {x^{k}}{k!}}\right)\left(\sum _{j\geq 0}A_{j}{\frac {x^{j}}{j!}}\right)\,dx-x}$

donde sustituimos${\displaystyle j=n-k}$y${\displaystyle {\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx}$Esto da como resultado la ecuación integral .

${\displaystyle 2(A(x)-1-x)=\int A(x)^{2}\,dx-x,}$

que después de la diferenciación se convierte en${\displaystyle 2{\frac {dA}{dx}}-2=A^{2}-1}$Esta ecuación diferencial se puede resolver mediante separación de variables (utilizando la condición inicial) .${\displaystyle A(0)=A_{0}/0!=1}$), y simplificado usando una fórmula de tangente de medio ángulo , dando el resultado final

${\displaystyle A(x)=\tan \left({\frac {\pi }{4}}+{\frac {x}{2}}\right)=\sec x+\tan x}$,

la suma de las funciones secante y tangente . Este resultado se conoce como el teorema de André . Se puede dar una interpretación geométrica de este resultado utilizando una generalización de un teorema de Johann Bernoulli . ^{[ 2 ]}

Del teorema de André se deduce que el radio de convergencia de la serie A ( x ) es π /2. Esto permite calcular la expansión asintótica ^{[ 3 ].} 

${\displaystyle A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}n!\,.}$

En 1877, Philipp Ludwig von Seidel publicó un algoritmo que simplifica el cálculo de A _n . ^{[ 4 ]}

${\displaystyle {\begin{array}{crrrcc}{}&{}&{\color {red}1}&{}&{}&{}\\{}&{\rightarrow }&{\color {blue}1}&{\color {red}1}&{}\\{}&{\color {red}2}&{\color {blue}2}&{\color {blue}1}&{\leftarrow }\\{\rightarrow }&{\color {blue}2}&{\color {blue}4}&{\color {blue}5}&{\color {red}5}\\{\color {red}16}&{\color {blue}16}&{\color {blue}14}&{\color {blue}10}&{\color {blue}5}&{\leftarrow }\end{array}}}$

El algoritmo de Seidel para A _n

1. Comience colocando el 1 en la fila 0 y sea k el número de la fila que se está llenando actualmente.
2. Si k es impar, entonces coloca el número del extremo izquierdo de la fila k − 1 en la primera posición de la fila k , y llena la fila de izquierda a derecha, de modo que cada entrada sea la suma del número de la izquierda y el número de la derecha.
3. Al final de la fila, duplique el último número.
4. Si k es par, proceda de forma similar en la otra dirección.

El algoritmo de Seidel es de hecho mucho más general (véase la exposición de Dominique Dumont ^{[ 5 ]} ) y fue redescubierto varias veces posteriormente.

De forma similar al enfoque de Seidel, DE Knuth y TJ Buckholtz dieron una ecuación de recurrencia para los números A _{2 n} y recomendaron este método para calcular los números de Bernoulli B _{2 n} y los números de Euler E _{2 n} 'en computadoras electrónicas utilizando solo operaciones simples con números enteros'. ^{[ 6 ]}

VI Arnold ^{[ 7 ]} redescubrió el algoritmo de Seidel y más tarde Millar, Sloane y Young popularizaron el algoritmo de Seidel bajo el nombre de transformada bustrophedon .

Forma triangular:

Solo OEIS : A000657  , con un 1, y OEIS : A214267  , con dos 1, están en el OEIS .

Distribución con un 1 suplementario y un 0 en las siguientes filas:

Este es OEIS : A239005  , una versión firmada de OEIS : A008280  . La diagonal principal es OEIS : A122045  . La diagonal principal es OEIS : A155585  . La columna central es OEIS : A099023  . Sumas de fila: 1, 1, −2, −5, 16, 61.... Ver OEIS : A163747  . Ver la matriz que comienza con 1, 1, 0, −2, 0, 16, 0 a continuación.

El algoritmo de Akiyama-Tanigawa aplicado a OEIS : A046978  ( n + 1 )/ OEIS : A016116  ( n ) produce:

1. La primera columna es OEIS : A122045  . Su transformación binomial da como resultado:

La primera fila de esta matriz es OEIS : A155585 .  Los valores absolutos de las antidiagonales crecientes son OEIS : A008280  . La suma de las antidiagonales es −OEIS : A163747  ( n + 1 ).

2. La segunda columna es 1 1 −1 −5 5 61 −61 −1385 1385... . Su transformación binomial produce:

La primera fila de esta matriz es 1 2 2 −4 −16 32 272 544 −7936 15872 353792 −707584... . Los valores absolutos de la segunda bisección son el doble de los valores absolutos de la primera bisección.

Considere el algoritmo de Akiyama-Tanigawa aplicado a OEIS : A046978  ( n )/( OEIS : A158780  ( n + 1 ) =  abs( OEIS : A117575  ( n )) + 1 = 1 , 2, 2, ⁠ 3/2 ⁠ , 1 , ⁠ 3/4 ⁠ , ⁠ 3 / 4 ⁠ , ⁠ 7 / 8 ⁠ , 1, ⁠ 17 / 16 ⁠ , ⁠ 17 / 16 ⁠ , ⁠ 33 / 32 ⁠ ... .

La primera columna cuyos valores absolutos son OEIS : A000111  podría ser el numerador de una función trigonométrica.

OEIS : A163747  es una autosecuencia de primer tipo (la diagonal principal es OEIS : A000004  ). La matriz correspondiente es:

Las dos primeras diagonales superiores son −1 3 −24 402... = (−1) ^{n + 1}  × OEIS : A002832 . La suma de las antidiagonales es 0 −2 0 10... = 2 × OEIS : A122045 ( n + 1).       

− OEIS : A163982  es una autosecuencia de segundo tipo, como por ejemplo OEIS : A164555  / OEIS : A027642  . Por lo tanto, el array:

La diagonal principal, aquí 2 −2 8 −92... , es el doble de la primera superior, aquí OEIS : A099023  . La suma de las antidiagonales es 2 0 −4 0... = 2  × OEIS : A155585 ( n + 1). OEIS : A163747 − OEIS : A163982 = 2 × OEIS : A122045 .          

Los números zigzag de índice impar (es decir, los números tangentes) están estrechamente relacionados con los números de Bernoulli . La relación viene dada por la fórmula

${\displaystyle B_{2n}=(-1)^{n-1}{\frac {2n}{4^{2n}-2^{2n}}}A_{2n-1}}$

para n > 0.   

Si Z _n denota el número de permutaciones de {1, ..., n } que son arriba-abajo o abajo-arriba (o ambas, para n < 2), entonces se deduce del emparejamiento dado anteriormente que Z _n =  2 A _n para n  ≥  2. Los primeros valores de Z _n son 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (secuencia A001250 en el OEIS ) .

Los números de zigzag de Euler están relacionados con los números de Entringer, a partir de los cuales se pueden calcular los números de zigzag. Los números de Entringer se pueden definir recursivamente de la siguiente manera: ^{[ 8 ]}

${\displaystyle E(0,0)=1}$

${\displaystyle E(n,0)=0\qquad {\mbox{for }}n>0}$

${\displaystyle E(n,k)=E(n,k-1)+E(n-1,n-k)}$.

El n ^-ésimo número de zigzag es igual al número de Entringer E ( n , n ).

Los números A _{2 n} con índices pares se denominan números secantes o números zig : dado que la función secante es par y la tangente es impar , se deduce del teorema de André mencionado anteriormente que son los numeradores de la serie de Maclaurin de sec x . Los primeros valores son 1, 1, 5, 61, 1385, 50521, ... (secuencia A000364 en la OEIS ) .

Los números secantes están relacionados con los números de Euler con signo (coeficientes de Taylor de la secante hiperbólica) mediante la fórmula E _{2 n}  =  ( − 1) ⁿ A _{2 n} . ( E _n  =  0 cuando n es impar).

De forma correspondiente, los números A _{2 n +1} con índices impares se denominan números tangentes o números zag . Los primeros valores son 1, 2, 16, 272, 7936, ... (secuencia A000182 en el OEIS ) .

Las relaciones de los números de Euler en zigzag con los números de Euler y los números de Bernoulli se pueden utilizar para demostrar lo siguiente ^{[ 9 ] [ 10 ]}

${\displaystyle A_{r}=-{\frac {4^{r}}{a_{r}}}\sum _{k=1}^{r}{\frac {(-1)^{k}\,S(r,k)}{k+1}}\left({\frac {3}{4}}\right)^{(k)}}$

dónde

${\displaystyle a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{if r is odd}}\\(-1)^{\frac {r}{2}}&{\mbox{if r is even}}\end{cases}},}$

${\displaystyle (x)^{(n)}=(x)(x+1)\cdots (x+n-1)}$ denotes the rising factorial, and ${\displaystyle S(r,k)}$ denotes Stirling numbers of the second kind.

• Longest alternating subsequence
• Boustrophedon transform
• Fence (mathematics), a partially ordered set that has alternating permutations as its linear extensions

• André, Désiré (1879), "Développements de séc x et de tang x" , Comptes rendus de l'Académie des sciences , 88 : 965– 967.

• André, Désiré (1881), "Sur les permutations alternées" (PDF) , Journal de mathématiques pures et appliquées , 3e série, 7 : 167– 184, archivado desde el original (PDF) el 22 de noviembre de 2021.

• Enrique, Felipe; Wanner, Gerhard (2019). "Zigzags con Bürgi, Bernoulli, Euler y el triángulo Seidel-Entringer-Arnol'd". Elementos de Matemáticas . 74 (4): 141– 168. doi : 10.4171/EM/393 ..

• Stanley, Richard P. (2011). Combinatoria enumerativa . Vol.  I (2ª  ed.). Cambridge University Press .

• Weisstein, Eric W. "Permutación alternada" . MathWorld .
• Ross Tang, "Una fórmula explícita para los números en zigzag de Euler (números ascendentes/descendentes) a partir de series de potencias" Una fórmula explícita simple para A _n .
• "Un estudio de permutaciones alternas" , un preimpreso de Richard P. Stanley