Mostrar código-fonte de Permutação alternada

{{Não confundir com|grupo alternante}}

 Em [[Matemática]] [[Combinatória]], uma '''permutação alternada''' ( ou '''permutação em zigue-zague''') do conjunto {{Math|{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 {{Math|{1, 2, 3 ,4<nowiki>}</nowiki>}} são:

* 1, 3, 2, 4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;porque&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1 < 3 > 2 < 4,
* 1, 4, 2, 3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;porque&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1 < 4 > 2 < 3,
* 2, 3, 1, 4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;porque&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2 < 3 > 1 < 4,
* 2, 4, 1, 3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;porque&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2 < 4 > 1 < 3, e
* 3, 4, 1, 2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;porque&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3 < 4 > 1 < 2.

Este tipo de permutação foi estudado pela primeira vez por [[Désiré André]] no século XIX.<ref>Jessica Millar, N. J. A. Sloane, Neal E. Young, [[arxiv:math/0205218v3|"A New Operation on Sequences: the Boustrouphedon Transform"]] Journal of Combinatorial Theory, Series A 76(1):44–54 (1996)</ref>

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'' <sub>''n''</sub> de permutações alternadas do conjunto {{Math|{1, ..., ''n''<nowiki>}</nowiki>}} é chamada de '''problema de André''' . Os números ''A'' <sub>''n''</sub> 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]] {{Math|''c''<sub>1</sub>, ..., ''c''<sub>''n''</sub>}} {{Math|''c''<sub>1</sub>, ..., ''c''<sub>''n''</sub>}} é 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 {{Math|''c''<sub>1</sub> < ''c''<sub>2</sub> > ''c''<sub>3</sub> < ...}} , chamando as permutações "baixo-cima" que satisfazem {{Math|''c''<sub>1</sub> > ''c''<sub>2</sub> < ''c''<sub>3</sub> > ...}} 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 [[Função bijectiva|correspondência simples um-para-um]] entre as permutações de baixo para cima e de cima para baixo: substituir cada entrada {{Math|''c''<sub>''i''</sub>}} por {{Math|''n'' + 1 - ''c''<sub>''i''</sub>}} 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é ==
[[Ficheiro:Bernoulli-zigzag.jpg|miniaturadaimagem| Os números em ziguezague em Bernoulli (1742), ''Opera Omnia'' vol. 4, pág. 105]]
A determinação do número ''A'' <sub>''n''</sub> de permutações alternadas do conjunto {{Math|{1, ..., ''n''<nowiki>}</nowiki>}} é chamada de ''problema de André'' . Os números ''A'' <sub>''n''</sub> 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'' <sub>''n''</sub> são 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... {{OEIS|id=A000111}}

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

: <math> 2A_{n+1} = \sum_{k=0}^n \binom{n}{k} A_k A_{n-k}</math>

para todo {{Math|''n'' ≥ 1}} . {{Harvtxt|André|1881}} utilizou esta recorrência para dar uma [[equação diferencial]] satisfeita pela [[Função geradora|função geradora exponencial]]

: <math> A(x) = \sum_{n=0}^\infty A_n \frac{x^n}{n!}</math>

para a sequência {{Math|''A<sub>n</sub>''}} . Na verdade, a recorrência dá:

: <math>
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
</math>

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

: <math>
2(A(x) - 1 - x) = \int A(x)^2\,dx - x,
</math>

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

: <math> A(x) = \operatorname{tg} \left(\frac\pi4 + \frac x2\right) = \sec x + \operatorname{tg} x</math> ,

a soma das funções [[Função trigonométrica|secante]] e [[Função trigonométrica|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<ref>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)</ref>

Segue do teorema de André que o [[raio de convergência]] da série {{Math|''A''(''x'')}} é&nbsp;{{Pi}} /2. Isso permite calcular a [[expansão assintótica]]<ref>{{Citation|último=Stanley|primeiro1=Richard P.|autorlink=Richard P. Stanley|arxiv=0912.4240|capítulo=A survey of alternating permutations|doi=10.1090/conm/531/10466|mr=2757798|páginas=165–196|publicado=American Mathematical Society|local=Providence, RI|series=Contemporary Mathematics|título=Combinatorics and graphs|volume=531|ano=2010}}</ref>

: <math> A_n \sim 2 \left(\frac{2}{\pi}\right)^{n + 1} n!\,. </math>

== 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

: <math>B_{2n} =(-1)^{n-1}\frac{2n}{4^{2n}-2^{2n}} A_{2n-1}</math>

para&nbsp;''n''&nbsp;>&nbsp;0.

Se ''Z'' <sub>''n''</sub> denota o número de permutações de {{Math|{1, ..., ''n''<nowiki>}</nowiki>}} que são cima-baixo ou baixo-cima (ou ambos, para ''n'' < 2), então segue do pareamento dado acima que ''Z'' <sub>''n''</sub> =&nbsp;2''A''<sub>''n''</sub> para ''n''&nbsp;≥&nbsp;2. Os primeiros valores de ''Z''<sub>''n''</sub> são 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... {{OEIS|A001250}}     .

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: <ref>Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html</ref>

: <math> E(0,0) = 1 </math>
: <math> E(n,0) = 0 \qquad \text{, para } n > 0 </math>
: <math> E(n,k) = E(n, k-1) + E(n-1, n-k) </math> .

O ''n-'' <sup>ésimo</sup> número em zigue-zague é igual ao número de Entringer ''E'' (''n'', ''n'').

Os números ''A''<sub>2''n''</sub> com índices pares são chamados '''números secantes''' ou '''números zigue''': como a função secante é [[Paridade de funções|par]] e a tangente é [[Paridade de funções|ímpar]], segue do teorema de André acima que eles são os numeradores na [[Série de Taylor|série de Maclaurin]] de {{Math|sec ''x''}} . Os primeiros valores são 1, 1, 5, 61, 1385, 50521, ... {{OEIS|id=A000364}}.

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''<sub>2''n''</sub>&nbsp;=&nbsp;(&#x2212;1)<sup>''n''</sup>''A''2<sub>''n''</sub>.(''E''<sub>''n''</sub>&nbsp;=&nbsp;0 quando ''n'' é ímpar).

Correspondentemente, os números ''A''<sub>2''n''+1</sub> com índices ímpares são chamados '''de números tangentes''' ou '''números zague'''. Os primeiros valores são 1, 2, 16, 272, 7936, ... {{OEIS|id=A000182}}.

== 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<ref>{{Citar periódico |título=The r-alternating permutations |periódico=Aequationes Mathematicae |ultimo=Mező |primeiro=István |ultimo2=Ramírez |primeiro2=José L. |ano=2019 |doi=10.1007/s00010-019-00658-5}}</ref><ref>{{Citar periódico |título=A Note on Alternating Permutations |periódico=The American Mathematical Monthly |número=5 |ultimo=Mendes |primeiro=Anthony |ano=2007 |paginas=437–440 |doi=10.1080/00029890.2007.11920432 |jstor=27642223 |volume=114}}</ref>

: <math> 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)} </math>

onde

: <math> 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}, </math>

<math>(x)^{(n)}=(x)(x+1)\cdots (x+n-1)</math> denota o [[Fatoriais crescentes e decrescentes|fatorial crescente]], e <math> S(r,k) </math> denota [[números de Stirling do segundo tipo]].


== Citações ==
{{Reflist}}

== Referências ==

* {{Citation|último=André|primeiro1=Désiré|autorlink=Désiré André|título=Développements de séc x et de tang x|periódico=[[Comptes rendus de l'Académie des sciences]]|volume=88|páginas=965–967|ano=1879|url=http://gallica.bnf.fr/ark:/12148/bpt6k30457/f961.image}}.

* {{Citation|último=André|primeiro1=Désiré|autorlink=Désiré André|título=Sur les permutations alternées|periódico=[[Journal de mathématiques pures et appliquées]]|series=3e série|volume=7|ano=1881|páginas=167–184|url=http://portail.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf|arquivourl=https://web.archive.org/web/20211122232221/http://portail.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf|arquivodata=22 de novembro de 2021}}.

* {{Citar periódico |título=Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle |periódico=Elemente der Mathematik |número=4 |ultimo=Henry |primeiro=Philippe |ultimo2=Wanner |primeiro2=Gerhard |ano=2019 |paginas=141–168 |doi=10.4171/EM/393 |volume=74}}.

* {{Citar livro|título=Enumerative Combinatorics|ultimo=Stanley|primeiro=Richard P.|editora=[[Cambridge University Press]]|ano=2011|volume=I|autorlink=Richard P. Stanley|edição=2nd}}

== Ligações externas ==

* {{MathWorld|titulo=Alternating Permutation|id=AlternatingPermutation}}
* [http://www.voofie.com/content/117/an-explicit-formula-for-the-euler-zigzag-numbers-updown-numbers-from-power-series/ Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series"] A simple explicit formula for ''A''<sub>''n''</sub>.
* [http://www-math.mit.edu/~rstan/papers/altperm.pdf "A Survey of Alternating Permutations"], a preprint by [[Richard Peter Stanley|Richard P. Stanley]]
[[Categoria:Permutações]]