Permutação alternada

Em Matemática Combinatória, uma permutação alternada ( ou permutação em zigue-zague) do conjunto ${1, 2, 3, ..., n$ } é uma permutação (arranjo) desses números de modo que cada entrada seja alternadamente maior ou menor que a entrada anterior. Por exemplo, as cinco permutações alternadas de ${1, 2, 3 ,4}$ são:

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, e
3, 4, 1, 2 porque 3 < 4 > 1 < 2.

Este tipo de permutação foi estudado pela primeira vez por Désiré André no século XIX.^[1]

Diferentes autores usam o termo permutação alternada de forma ligeiramente diferente: alguns exigem que a segunda entrada em uma permutação alternada seja maior que a primeira (como nos exemplos acima), outros exigem que a alternância seja invertida (de modo que a segunda entrada seja menor que a primeira, então a terceira maior que a segunda, e assim por diante), enquanto outros chamam ambos os tipos pelo nome de permutação alternada.

A determinação do número A _n de permutações alternadas do conjunto ${1, ..., n}$ é chamada de problema de André . Os números A _n são conhecidos como números de Euler, números em zigue-zague ou números para cima/para baixo . Quando n é par, o número A é conhecido como um número secante, enquanto se n é ímpar, é conhecido como um número tangente . Esses últimos nomes vêm do estudo da função geradora da sequência.

Definições

Uma permutação $c 1, ..., c n$ $c 1, ..., c n$ é dito alternada se suas entradas sobem e descem alternadamente. Portanto, cada entrada, exceto a primeira e a última, deve ser maior ou menor que ambas as suas vizinhas. Alguns autores usam o termo alternado para se referir apenas às permutações "cima-baixo" para as quais $c 1 < c 2 > c 3 < ...$ , chamando as permutações "baixo-cima" que satisfazem $c 1 > c 2 < c 3 > ...$ pelo nome de alternância reversa . Outros autores invertem essa convenção ou usam a palavra "alternada" para se referir às permutações de cima para baixo e de baixo para cima.

Há uma correspondência simples um-para-um entre as permutações de baixo para cima e de cima para baixo: substituir cada entrada $c i$ por $n + 1 - c i$ inverte a ordem relativa das entradas.

Por convenção, em qualquer esquema de nomenclatura, as permutações únicas de comprimento 0 (a permutação do conjunto vazio) e 1 (a permutação que consiste em uma única entrada 1) são consideradas alternadas.

Teorema de André

Os números em ziguezague em Bernoulli (1742), Opera Omnia vol. 4, pág. 105

A determinação do número A _n de permutações alternadas do conjunto ${1, ..., n}$ é chamada de problema de André . Os números A _n são conhecidos como números de Euler, números em zigue-zague, números para cima/para baixo ou por algumas combinações desses nomes. O nome números de Euler, em particular, às vezes é usado para uma sequência intimamente relacionada. Os primeiros valores de A _n são 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequência A000111 na OEIS)

Esses números satisfazem uma recorrência simples, semelhante à dos números de Catalunha : dividindo o conjunto de permutações alternadas (tanto baixo-cima quanto cima-baixo) do conjunto ${1, 2, 3, ..., n, n + 1}$ de acordo com a posição k da maior entrada $n + 1$ , pode-se mostrar que

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

para todo $n \geq 1$ . André (1881) utilizou esta recorrência para dar uma equação diferencial satisfeita pela função geradora exponencial

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

para a sequência $A n$ . Na verdade, a recorrência dá:

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

onde substituímos $j=n-k$ e ${\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx$ . Isso fornece a equação integral

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

que após a diferenciação se torna $2{\frac {dA}{dx}}-2=A^{2}-1$ . Esta equação diferencial pode ser resolvida pela separação de variáveis (usando a condição inicial $A(0)=A_{0}/0!=1$ ), e simplificado usando uma fórmula de meio ângulo tangente, dando o resultado final

A(x)=\operatorname {tg} \left({\frac {\pi }{4}}+{\frac {x}{2}}\right)=\sec x+\operatorname {tg} x

,

a soma das funções secante e tangente . Este resultado é conhecido como teorema de André . Uma interpretação geométrica deste resultado pode ser dada usando uma generalização de um teorema de Johann Bernoulli^[2]

Segue do teorema de André que o raio de convergência da série $A (x)$ é $π$ /2. Isso permite calcular a expansão assintótica^[3]

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

Sequências relacionadas

Os números em zigue-zague de índice ímpar (ou seja, os números tangentes) estão intimamente relacionados aos números de Bernoulli . A relação é dada pela fórmula

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

para n > 0.

Se Z _n denota o número de permutações de ${1, ..., n}$ que são cima-baixo ou baixo-cima (ou ambos, para n < 2), então segue do pareamento dado acima que Z _n = 2A_n para n ≥ 2. Os primeiros valores de Z_n são 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequência A001250 na OEIS) .

Os números em zigue-zague de Euler estão relacionados aos números de Entringer, a partir dos quais os números em zigue-zague podem ser calculados. Os números de Entringer podem ser definidos recursivamente como segue: ^[4]

E(0,0)=1

E(n,0)=0\qquad {\text{, para }}n>0

E(n,k)=E(n,k-1)+E(n-1,n-k)

.

O n- ^ésimo número em zigue-zague é igual ao número de Entringer E (n, n).

Os números A_2n com índices pares são chamados números secantes ou números zigue: como a função secante é par e a tangente é ímpar, segue do teorema de André acima que eles são os numeradores na série de Maclaurin de $sec x$ . Os primeiros valores são 1, 1, 5, 61, 1385, 50521, ... (sequência A000364 na OEIS).

Os números secantes estão relacionados aos números de Euler com sinais (coeficientes de Taylor da secante hiperbólica) pela fórmula E_2n = (−1)ⁿA2_n.(E_n = 0 quando n é ímpar).

Correspondentemente, os números A_2n+1 com índices ímpares são chamados de números tangentes ou números zague. Os primeiros valores são 1, 2, 16, 272, 7936, ... (sequência A000182 na OEIS).

Fórmula explícita em termos dos números de Stirling de segundo tipo

As relações dos números em zigue-zague de Euler com os números de Euler e os números de Bernoulli podem ser usadas para provar o seguinte^[5]^[6]

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)}

onde

a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\text{se r é ímpar}}\\(-1)^{\frac {r}{2}}&{\text{se r é par}}\end{cases}},

$(x)^{(n)}=(x)(x+1)\cdots (x+n-1)$ denota o fatorial crescente, e $S(r,k)$ denota números de Stirling do segundo tipo.

Citações

↑ Jessica Millar, N. J. A. Sloane, Neal E. Young, "A New Operation on Sequences: the Boustrouphedon Transform" Journal of Combinatorial Theory, Series A 76(1):44–54 (1996)
↑ Philippe Henry, Gerhard Wanner, "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle", Elemente der Mathematik 74 (4) : 141–168 (2019)
↑ Stanley, Richard P. (2010), «A survey of alternating permutations», Combinatorics and graphs, Contemporary Mathematics, 531, Providence, RI: American Mathematical Society, pp. 165–196, MR 2757798, arXiv:0912.4240 , doi:10.1090/conm/531/10466
↑ Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html
↑ Mező, István; Ramírez, José L. (2019). «The r-alternating permutations». Aequationes Mathematicae. doi:10.1007/s00010-019-00658-5
↑ Mendes, Anthony (2007). «A Note on Alternating Permutations». The American Mathematical Monthly. 114 (5): 437–440. JSTOR 27642223. doi:10.1080/00029890.2007.11920432

Referências

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, cópia arquivada (PDF) em 22 de novembro de 2021 .

Henry, Philippe; Wanner, Gerhard (2019). «Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol'd triangle». Elemente der Mathematik. 74 (4): 141–168. doi:10.4171/EM/393 .

Stanley, Richard P. (2011). Enumerative Combinatorics. I 2nd ed. [S.l.]: Cambridge University Press

Ligações externas

Weisstein, Eric W. «Alternating Permutation». MathWorld (em inglês)
Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for A_n.
"A Survey of Alternating Permutations", a preprint by Richard P. Stanley

[1] Jessica Millar, N. J. A. Sloane, Neal E. Young, "A New Operation on Sequences: the Boustrouphedon Transform" Journal of Combinatorial Theory, Series A 76(1):44–54 (1996)

[2] Philippe Henry, Gerhard Wanner, "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle", Elemente der Mathematik 74 (4) : 141–168 (2019)

[3] Stanley, Richard P. (2010), «A survey of alternating permutations», Combinatorics and graphs, Contemporary Mathematics, 531, Providence, RI: American Mathematical Society, pp. 165–196, MR 2757798, arXiv:0912.4240 , doi:10.1090/conm/531/10466

[4] Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html

[5] Mező, István; Ramírez, José L. (2019). «The r-alternating permutations». Aequationes Mathematicae. doi:10.1007/s00010-019-00658-5

[6] Mendes, Anthony (2007). «A Note on Alternating Permutations». The American Mathematical Monthly. 114 (5): 437–440. JSTOR 27642223. doi:10.1080/00029890.2007.11920432

[1]

[2]

[3]

[4]

[5]

[6]