Permutación alternada

Tipo de permutación

En matemáticas combinatorias , una permutación alternada (o permutación en zigzag ) del conjunto {1, 2, 3, ..., n } es una permutación (disposición) de esos números de modo que cada entrada sea alternativamente mayor o menor que la entrada 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 estudiado por primera vez por Désiré André en el siglo XIX. ^[1]

Distintos autores utilizan el término permutación alternada de forma ligeramente diferente: algunos requieren que la segunda entrada de una permutación alternada sea mayor que la primera (como en los ejemplos anteriores), otros requieren que la alternancia se invierta (de modo que la segunda entrada sea menor que la primera, luego la tercera mayor que la segunda, y así sucesivamente), mientras que otros llaman a ambos tipos con el nombre de permutación alternada.

La determinación del número A _n de permutaciones alternadas del conjunto {1, ..., n } se denomina problema de André . Los números A _n se conocen como números de Euler , números en zigzag o números arriba/abajo . 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 sucesión.

Definiciones

Se dice que una permutación c ₁ , ..., c _n es alternada si sus entradas ascienden y descienden alternativamente. Por lo tanto, cada entrada que no sea la primera ni la última debe ser mayor o menor que sus dos vecinas. Algunos autores usan el término alternada para referirse únicamente a las permutaciones "arriba-abajo" para las que c ₁ < c ₂ > c ₃ < ... , y denominan alternada inversa a las permutaciones "abajo-arriba" que satisfacen c ₁ > c ₂ < c ₃ > ... . Otros autores invierten esta convención o usan la palabra "alternada" para referirse tanto a las permutaciones arriba-abajo como a las permutaciones abajo-arriba.

Existe una correspondencia simple uno a uno entre las permutaciones abajo-arriba y arriba-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 nombres las permutaciones únicas de longitud 0 (la permutación del conjunto vacío ) y 1 (la permutación que consiste en una única entrada 1) se consideran alternas.

Teorema de André

Los números en zigzag en Bernoulli (1742), Opera Omnia vol. 4, p. 105

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 de diversas formas: números de Euler , números en zigzag , números arriba/abajo o mediante algunas combinaciones de estos nombres. 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 catalanes : al dividir el conjunto de permutaciones alternas (tanto de abajo hacia arriba como de arriba hacia abajo) 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_{n-k}}$

para todo n ≥ 1. André (1881) utilizó esta recurrencia para dar una ecuación diferencial satisfecha por la función generadora exponencial

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

para la sucesión 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 y . Esto nos da la ecuación integral ${\displaystyle j=n-k}$ ${\displaystyle {\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx}$

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

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

${\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 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!\,.}$

Secuencias relacionadas

Los números en zigzag de índice impar (es decir, los números tangentes) están estrechamente relacionados con los números de Bernoulli . La relación está 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 la OEIS ).

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

${\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 en 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 zigzagueantes : puesto que la función secante es par y la tangente es impar , se deduce del teorema de André 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) por la fórmula E _{2 n}  = (−1) ⁿ A _{2 n} . ( E _n  = 0 cuando n es impar).

De manera 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 la OEIS ).

Fórmula explícita en términos de números de Stirling de segundo tipo

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

${\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)}$denota el factorial ascendente , y denota números de Stirling de segundo tipo . ${\displaystyle S(r,k)}$

Véase también

• Subsecuencia alterna más larga
• Transformación de bustrofedón
• Valla (matemáticas) , un conjunto parcialmente ordenado que tiene permutaciones alternas como sus extensiones lineales

Citas

1. Jessica Millar, NJA Sloane, Neal E. Young, "Una nueva operación en secuencias: la transformada de Boustrouphedon" Journal of Combinatorial Theory, Serie A 76(1):44–54 (1996)
2. Philippe Henry, Gerhard Wanner, "Zigzags con Bürgi, Bernoulli, Euler y el triángulo Seidel-Entringer-Arnol'd", Elemente der Mathematik 74 (4): 141–168 (2019)
3. Stanley, Richard P. (2010), "Un estudio de permutaciones alternas", Combinatoria y gráficos , Contemporary Mathematics, vol. 531, Providence, RI: American Mathematical Society, págs. 165–196, arXiv : 0912.4240 , doi : 10.1090/conm/531/10466, MR  2757798
4. Weisstein, Eric W. "Número de entrada". De MathWorld, un recurso web de Wolfram. http://mathworld.wolfram.com/EntringerNumber.html
5. Mendes, Anthony (2007). "Una nota sobre permutaciones alternas". The American Mathematical Monthly . 114 (5): 437–440. doi :10.1080/00029890.2007.11920432. JSTOR  27642223.
6. Mező, István; Ramírez, José L. (2019). "Las permutaciones alternas r". Aecuaciones Mathematicae . doi :10.1007/s00010-019-00658-5.

Referencias

• 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 .

Enlaces externos

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