Em Matemática Combinatória, uma permutação alternada ( ou permutação em zigue-zague) do conjunto } é 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 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.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)
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 é 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 é 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 , chamando as permutações "baixo-cima" que satisfazem 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 por 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é miniaturadaimagem| 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 é 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, ...
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 de acordo com a posição k da maior entrada , pode-se mostrar que
para todo . utilizou esta recorrência para dar uma equação diferencial satisfeita pela função geradora exponencial
para a sequência . Na verdade, a recorrência dá:
onde substituímos e . Isso fornece a equação integral
que após a diferenciação se torna . Esta equação diferencial pode ser resolvida pela separação de variáveis (usando a condição inicial ), e simplificado usando uma fórmula de meio ângulo tangente, dando o resultado final
,
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 BernoulliPhilippe Henry, Gerhard Wanner, "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle", Elemente der Mathematik 74 (4) : 141–168 (2019)
Segue do teorema de André que o raio de convergência da série é /2. Isso permite calcular a expansão assintótica
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
para n > 0.
Se Z n denota o número de permutações de que são cima-baixo ou baixo-cima (ou ambos, para n < 2), então segue do pareamento dado acima que Z n = 2An para n ≥ 2. Os primeiros valores de Zn são 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... .
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: Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html
.
O n- ésimo número em zigue-zague é igual ao número de Entringer E (n, n).
Os números A2n 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 . Os primeiros valores são 1, 1, 5, 61, 1385, 50521, ... .
Os números secantes estão relacionados aos números de Euler com sinais (coeficientes de Taylor da secante hiperbólica) pela fórmula E2n = (−1)nA2n.(En = 0 quando n é ímpar).
Correspondentemente, os números A2n+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, ... .
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
onde
denota o fatorial crescente, e denota números de Stirling do segundo tipo.
Citações
Referências
.
.
.
Ligações externas
Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for An. "A Survey of Alternating Permutations", a preprint by Richard P. Stanley Categoria:Permutações