Permutación alterna

No confundir con el grupo alterno .

Tipo de permutación

En matemática combinatoria , una permutación alterna (o permutación en zigzag ) del conjunto {1, 2, 3, ..., n } es una permutación (disposición) de esos números para que cada entrada sea alternativamente mayor o menor que la entrada anterior. . Por ejemplo, las cinco permutaciones alternas 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]

Diferentes autores usan el término permutación alterna de forma ligeramente diferente: algunos requieren que la segunda entrada en una permutación alterna sea más grande que la primera (como en los ejemplos anteriores), otros requieren que la alternancia se invierta (para que la segunda entrada sea más pequeña que el primero, luego el tercero más grande que el segundo, y así sucesivamente), mientras que otros llaman a ambos tipos por el nombre de permutación alterna.

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

Definiciones

Se dice que una permutación c ₁ , ..., c _n es alterna si sus entradas suben y bajan alternativamente. Por lo tanto, cada entrada que no sea la primera y la última debe ser más grande o más pequeña que sus dos vecinas. Algunos autores usan el término alternancia para referirse solo a las permutaciones "arriba-abajo" para las cuales c ₁ < c ₂ > c ₃ <... , llamando a las permutaciones "abajo-arriba" que satisfacen c ₁ > c ₂ < c ₃ > ... por el nombre reverso alternando. Otros autores invierten esta convención, o usan la palabra "alternar" para referirse a permutaciones tanto de arriba hacia abajo como de abajo hacia arriba.

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 consiste en una sola entrada 1) se consideran alternas.

Teorema de André

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 son conocidos diversamente como números de Euler , números de zigzag , arriba / abajo números , o por algunas combinaciones de estos nombres. El nombre de números de Euler en particular se usa 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 : dividiendo el conjunto de permutaciones alternas (tanto hacia arriba como hacia abajo) del conjunto {1, 2, 3, ...,  n ,  n  + 1} de acuerdo con la posición k de la entrada más grande n + 1 , se puede mostrar que

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

para todo n ≥ 1 . André (1881) usó 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 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 y . Esto 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 . Esta ecuación diferencial puede resolverse mediante la separación de variables (usando la condición inicial ) y simplificarse usando una fórmula de medio á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 deduce del teorema de André que el radio de convergencia de la serie A ( x ) es  π / 2. Esto permite calcular la expansión asintótica ^[2]

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

Secuencias enteras relacionadas

Los números en zigzag con índices impares (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 ambos, para n <2) entonces se deduce del emparejamiento dado arriba 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 de forma recursiva de la siguiente manera: ^[3]

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

En consecuencia, 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 del segundo tipo

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

${\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 del segundo tipo .${\displaystyle S(r,k)}$

Ver también

• La subsecuencia alterna más larga
• Transformada de boustrophedon
• Fence (matemáticas) , un conjunto parcialmente ordenado que tiene permutaciones alternas como extensiones lineales

Citas

1. Jessica Millar, NJA Sloane, Neal E. Young, "Una nueva operación sobre secuencias: la transformación de Boustrouphedon" Diario de teoría combinatoria, Serie A 76 (1): 44-54 (1996)
2. Stanley, Richard P. (2010), "Una encuesta de permutaciones alternas", Combinatoria y gráficos , Matemáticas contemporáneas, 531 , Providence, RI: American Mathematical Society, págs. 165-196, arXiv : 0912.4240 , doi : 10.1090 / conm / 531/10466 , MR  2757798
3. Weisstein, Eric W. "Número de entrada". De MathWorld - Un recurso web de Wolfram. http://mathworld.wolfram.com/EntringerNumber.html
4. Mendes, Anthony (2007). "Una nota sobre permutaciones alternas". The American Mathematical Monthly . 114 (5): 437–440. doi : 10.1080 / 00029890.2007.11920432 . JSTOR 27642223 . 
5. Mező, István; Ramírez, José L. (2019). "Las permutaciones r-alternas". Aequationes 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^{[ enlace muerto permanente ]} .

• Stanley, Richard P. (2011). Combinatoria enumerativa . Vol. I (2ª ed.). Prensa de la Universidad de Cambridge .

Enlaces externos

• Weisstein, Eric W. "Permutación alternante" . 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