Permutação alternada

 Em Matemática Combinatória, uma permutação alternada ( ou permutação em zigue-zague) do conjunto Predefinição:Math} é 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 Predefinição:Math 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.

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 Predefinição:Math é 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 Predefinição:Math Predefinição:Math é 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 Predefinição:Math , chamando as permutações "baixo-cima" que satisfazem Predefinição:Math 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 Predefinição:Math por Predefinição:Math 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 Predefinição:Math é 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, ... Predefinição: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 Predefinição:Math de acordo com a posição k da maior entrada Predefinição:Math, pode-se mostrar que

$2A_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})A_k{A}_{n-k}$

para todo Predefinição:Math . Predefinição:Harvtxt utilizou esta recorrência para dar uma equação diferencial satisfeita pela função geradora exponencial

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

para a sequência Predefinição:Math . Na verdade, a recorrência dá:

$2\sum _{n\ge 1}{A}_{n+1}\frac{x^{n+1}}{(n+1)!}=\sum _{n\ge 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\ge 0}{A}_k\frac{x^k}{k!}\right)\left(\sum _{j\ge 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)=\mathrm{tg}(\frac{\pi }{4}+\frac{x}{2})=\sec x+\mathrm{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

Segue do teorema de André que o raio de convergência da série Predefinição:Math é Predefinição:Pi /2. Isso permite calcular a expansão assintótica

$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 Predefinição:Math 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, ... Predefinição: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:

$E(0,0)=1$

$E(n,0)=0\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 Predefinição:Math . Os primeiros valores são 1, 1, 5, 61, 1385, 50521, ... Predefinição: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, ... Predefinição: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

$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{array}{cc}(-1{)}^{\frac{r-1}{2}}(1+2^{-r})& \text{se r é ímpar}\\ (-1{)}^{\frac{r}{2}}& \text{se r é par}\end{array},$

$(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.

Referências

• Predefinição:Citation.

• Predefinição:Citation.

• Predefinição:Citar periódico.

• Predefinição:Citar livro

Ligações externas

• Predefinição:MathWorld
• 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