Permutación alterna

Type of permutation

En matemáticas combinatorias , 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 de modo 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 manera ligeramente diferente: algunos requieren que la segunda entrada en una permutación alterna sea mayor que la primera (como en los ejemplos anteriores), otros requieren que la alternancia se invierta (de modo que la segunda entrada sea más pequeña que el primero, luego el tercero mayor que el segundo, y así sucesivamente), mientras que otros llaman a ambos tipos con el nombre de permutación alterna.

La determinación del número An de permutaciones alternas del conjunto {1,..., _n } se llama problema de André . Los números An se conocen como números de Euler , números en zigzag o números arriba/ _abajo . Cuando n es par el número _An 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 distinta de la primera y la última debe ser mayor o menor que sus dos vecinas. Algunos autores utilizan el término alternancia para referirse únicamente 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 alternancia inversa . Otros autores invierten esta convención o utilizan la palabra "alternando" para referirse a permutaciones tanto de arriba a abajo como de abajo a arriba.

Existe una correspondencia simple uno a uno entre las permutaciones descendentes y ascendentes: reemplazar cada entrada _ci con n + 1 - ci _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.

teorema de andré

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

La determinación del número An de permutaciones alternas del conjunto {1,..., _n } se llama problema de André . Los números An se conocen como números de Euler , números en zigzag , números arriba/abajo _o algunas combinaciones de estos nombres. El nombre números de Euler en particular se utiliza a veces para una secuencia estrechamente relacionada. Los primeros valores de An son 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (secuencia _A000111 en el OEIS ).

Estos números satisfacen una recurrencia simple, similar a la de los números catalanes : dividiendo 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 norte ≥ 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 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 en . Esta ecuación diferencial se puede resolver separando variables (usando la condición inicial ) y simplificada 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 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 con í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  norte  > 0.

Si Z _n denota el número de permutaciones de {1, ..., n } que son de arriba a abajo o de abajo a arriba (o ambas, para n < 2), entonces se deduce del emparejamiento dado anteriormente que Z _n = 2 An _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 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 ené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 llaman 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 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 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 OEIS ).

Fórmula explícita en términos de números de Stirling de segunda especie.

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 los números de Stirling del segundo tipo . ${\displaystyle S(r,k)}$

Ver también

• Subsecuencia alterna más larga
• Transformada de Boustrophedon
• Valla (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 transformada de Boustrouphedon" Revista de teoría combinatoria, 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áficas , Matemáticas contemporáneas, vol. 531, Providence, RI: Sociedad Matemática Estadounidense, 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, Antonio (2007). "Una nota sobre permutaciones alternas". El Mensual Matemático Estadounidense . 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. Yo (2ª ed.). Prensa de la Universidad de Cambridge .

enlaces externos

• Weisstein, Eric W. "Permutación alterna". MundoMatemático .
• 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 sobre permutaciones alternas", una preimpresión de Richard P. Stanley