Números de Euler

Centro de Competência de Ciências Exactas e da Engenharia

Disciplina: Combinatória – Fundamentos e Aplicações

Docente: Teresa Gouveia

Discente: Raquel Camacho; Número: 2030305

Os Números de Euler (ou

números Eulerianos)

Funchal

2011

1

Números de Euler ou Números Eulerianos

Os números de Euler (ou Eulerianos) permitem contar o número de permutações de n

elementos com k ascendentes.

Nota 1: Uma permutação é um rearranjo de uma lista ordenada de elementos.

Ao olharmos atentamente para a descrição feita anteriormente, pode surgir a dúvida

sobre o termo “ascendente”. Para melhor compreendermos este conceito, suponhamos

que ( )1 2 3, , ,..., nπ = π π π π é uma permutação de { }1,2,3,...,n . Dizemos que o índice i,

com 1 i n≤ < , é um ascendente da permutação π se 1i i+π < π .

Exemplo1:

Consideremos o conjunto { }1,2,3 .

a) Determine as permutações de { }1,2,3 .

Facilmente conseguimos descobrir as diferentes permutações deste conjunto,

combinando todos os elementos em todas as posições possíveis:

( )1,2,3

( )1,3,2

( )2,1,3

( )2,3,1

( )3,1,2

( )3,2,1

b) Das permutações encontradas, indique quantas têm apenas um ascendente.

Para determinarmos o número de ascendentes de cada uma das permutações, temos

de comparar os elementos dois a dois, tendo o cuidado de comparar um elemento

sempre com o seu sucessor. Para descobrir o número de ascendentes deveremos

sempre fazer a questão “Será que este elemento é menor do que este elemento?”. Se

a resposta for positiva, então estamos perante um ascendente.

Analisemos, pois, cada uma das permutações, assumindo cada uma das permutações

como ( )1 2 3, ,π = π π π :

� Para ( )1,2,3π =

1π 2π 3π

2

Vamos, então, comparar o 1 com o 2, fazendo a questão “Será que 1 é menor do que

2?” A resposta é obviamente positiva. Logo, temos que 1 2 1 2π < π ⇔ < →

Verdadeiro.

Vamos agora comparar o 2 com o 3, questionando “Será que 2 é menor do que 3?”.

A resposta é positiva, logo temos que 2 3 2 3π < π ⇔ < → Verdadeiro.

Logo, esta permutação tem dois ascendentes, pois obtivemos duas respostas

verdadeiras. Estes ascendentes são 1i = e 2i = .

� Para ( )1,3,2π =

Repetiremos o processo elaborado anteriormente, comparando os elementos dois a

dois:

1 2 1 3π < π ⇔ < → Verdadeiro

2 3 3 2π < π ⇔ < → Falso

Logo, esta permutação tem apenas um ascendente, pois só obtivemos uma condição

verdadeira. Este ascendente é 1i = .

� Para ( )2,1,3π = :

1 2 2 1π < π ⇔ < → Falso

2 3 1 3π < π ⇔ < → Verdadeiro

Logo, esta permutação tem um ascendente, pois só obtivemos uma condição


� Para ( )2,3,1π = :

1 2 2 3π < π ⇔ < →Verdadeiro

2 3 3 1π < π ⇔ < → Falso



� Para ( )3,1,2π = :

1 2 3 1π < π ⇔ < → Falso

2 3 1 2π < π ⇔ < →Verdadeiro



3

� Para ( )3,2,1π = :

1 2 3 2π < π ⇔ < →Falso

2 3 2 1π < π ⇔ < →Falso

Logo, esta permutação não tem ascendentes, pois não obtivemos condições

verdadeiras.

Respondendo à questão, podemos concluir que quatro permutações de { }1,2,3 têm

apenas um ascendente.

No entanto, quando trabalhamos com permutações surge um outro termo quando

comparamos os elementos da permutação dois a dois. Já vimos o que é e como

identificar um ascendente, mas também podemos pensar no caso contrário. Se em vez

de perguntarmos “Será que este elemento é menor do que este?”, perguntarmos “Será

que este elemento é maior do que este?” estamos a falar de descendentes.

Ainda nesta linha das permutações surgem outros termos relacionados com a posição

que cada elemento da permutação ocupa: os excedentes e os excedentes fracos.

Podemos, portanto, definir cada um destes termos para o caso geral:

Suponhamos que ( )1 2 3, , ,..., nπ = π π π π é uma permutação de { }1,2,3,...,n .

Dizemos que o índice i, com 1 i n≤ < , é um ascendente da permutação π se

1.i i+π < π

Um descendente da permutação π é o índice i com 1 i n≤ < , tal que 1i i+π > π .

O índice i, com 1 i n≤ ≤ , é um excedente da permutação π se i iπ > . Enquanto o

índice i, com1 i n≤ ≤ , diz-se um excedente fraco da permutação π se i iπ ≥ .

Agora que sabemos como definir cada um destes conceitos, podemos completar uma

tabela com esses dados, referentes ao Exemplo 1:

4

Permutação Nº de

ascendentes Nº de

descendentes Nº de

excedentes

Nº de excedentes

fracos

( )1,2,3 2 0 0 3

( )1,3,2 1 1 1 2

( )2,1,3 1 1 1 2

( )2,3,1 1 1 2 2

( )3,1,2 1 1 1 1

( )3,2,1 0 2 1 2

Nota 2: No caso dos excedentes, pode surgir alguma dúvida sobre como foram obtidos

estes valores. Por isso, mostraremos como foi obtido o valor para a permutação

( )1,3,2π = , já que para as outras permutações o processo é o mesmo.

Para ser excedente da permutação tem de verificar i iπ > , com 1 3i≤ ≤ (porque

3n = ), portanto:

1 1 1 1π > ⇔ > → Falso

2 2 3 2π > ⇔ > →Verdadeiro

3 3 2 3π > ⇔ > →Falso

Então, esta permutação de { }1,2,3 tem apenas um excedente. Este excedente é 2i = .

Nota 3: No caso dos excedentes fracos, procedemos da mesma forma que no caso dos

excedentes, tendo apenas em atenção que para ser excedente fraco de uma permutação

tem de verificar i iπ ≥ , com 1 3i≤ ≤ (já que, no exemplo dado, 3n = ).

A partir da tabela podemos responder a perguntas simples como: Quantas

permutações de { }1,2,3 têm apenas um ascendente? Quantas permutações de { }1,2,3

têm um descendente? Quantas permutações de { }1,2,3 têm apenas um excedente? E, por

fim, quantas permutações de { }1,2,3 têm apenas dois excedente fracos?

A resposta a estas questões é quatro permutações.

A partir da análise da tabela, podemos facilmente chegar a uma conclusão: se

determinarmos o número de permutações com k ascendentes, saberemos

automaticamente o número de permutações com k descendentes, com k excedentes e

com 1k + excedentes fracos.

5

Por exemplo, analisando a tabela, podemos responder às questões:

Quantas permutações têm exactamente dois ascendentes? Uma.

Quantas permutações têm exactamente dois descendentes? Uma.

Quantas permutações têm exactamente dois excedentes? Uma.

Quantas permutações têm exactamente três excedentes fracos? Uma.

( )1 2 1k + = +

Nº de ascendentes

Assim, se tivermos um conjunto com n permutações com k ascendentes, sabemos

que esse conjunto terá n permutações com k descendentes, n permutações com k

excedentes e n permutações com 1k + excedentes fracos.

O exemplo que trabalhámos anteriormente é bastante simples e perfeitamente

exequível aplicando este método de análise directa de cada uma das permutações,

verificando o número de ascendentes, descendentes, excedentes e excedentes fracos de

cada uma delas. No entanto, existem casos em que se torna moroso determinar todas as

permutações do conjunto e, consequentemente, determinar os ascendentes,

descendentes, excedentes e excedentes fracos torna-se numa tarefa extremamente

ingrata.

Nestes casos (como veremos de seguida), será útil utilizarmos os Números de Euler

neste processo de encontrar o número de permutações com um determinado número de

ascendentes. E, como vimos anteriormente, a partir do cálculo do número de

permutações com k ascendentes, poderemos saber o número de permutações com k

descendentes, com k excedentes e com 1k + excedentes fracos.

Como já vimos anteriormente, o número de Euler é o número de permutações de

{ }1,2,3,...,n com exactamente k ascendentes. O número de Euler pode ser representado

por ( ),E n k ou

n

k,

Como determinar os números de Euler?

Podemos determinar os números de Euler, recorrendo à seguinte fórmula:

( ) ( ) ( )

0

1, 1 1 , 1

ki n

i

n nE n k k i n

k i=

+ = = − + − ≥

∑

6

Existem, ainda, algumas propriedades relativas aos números de Euler, que facilitam o

seu cálculo:

i)

1 , 10 1

n nn

n= = ≥

−

ii)

, 11

n nn

k n k= ≥

− −

iii) ( ) ( )1 11 + , 1

1

n n nk n k n

k k k

− −= + − ≥

−

Veremos, agora, um exemplo em que a utilização dos números de Euler é bastante

útil.

Exemplo 2:

Determine o número de permutações de { }1,2,3,4,5,6com:

a) um único ascendente;

Se utilizássemos o método utilizado no Exemplo 1, teríamos de determinar todas as

permutações de { }1,2,3,4,5,6 , o que é bastante moroso.

Utilizando os números de Euler, temos apenas de recorrer, por exemplo, à fórmula da

propriedade iii). Neste caso, sabemos que 6n = (número de elementos do conjunto)

e 1k = (número de ascendentes):

( ) ( )6 6 1 6 11 1 + 6 1

1 1 1 1

5 5 2 5

1 0

n

k

− −= = + −

−

= +

=1, pela propriedade i)

( ) ( )5 1 5 1 2 1 1 + 5 1 5

1 1 1

4 4 4 4 2 2 +4 5 4 8 5 4 13

1 0 1 1

− −= + − + −

= + = + + = +


Voltamos a utilizar a

propriedade iii)

7

( ) ( )4 1 4 1 4 1 1 + 4 1 13

1 1 1

3 3 3 3 4 2 +3 13 8 12 13 8 25

1 0 1 1

− −= + − + −

= + = + + = +


( ) ( )3 1 3 1 8 1 1 + 3 1 25

1 1 1

2 2 8 2 +2 25 16 16 25 57

1 0

− −= + − + −

= + = + + =


Existem 57 permutações de { }1,2,3,4,5,6com apenas um ascendente.

b) exactamente quatro ascendentes;

Pela propriedade ii) temos que:

, 1

1

n nn

k n k= ≥

− −

Então,

6 6 6.

4 6 1 4 1= =

− −

Quer isto dizer que o número de permutações de{ }1,2,3,4,5,6com um ascendente é

igual ao número de permutações de { }1,2,3,4,5,6 com quatro ascendentes.

Como calculámos na alínea anterior

657

1= e como

6 6

1 4= , então

657

4= .

Logo, existem 57 permutações de { }1,2,3,4,5,6 com, exactamente, quatro

ascendentes.

c) exactamente dois excedentes;


propriedade iii)


propriedade iii)

8

Como já vimos, os números de Euler também podem ser utilizados para calcular o

número de permutações com k excedentes.

Para resolver esta alínea vamos utilizar a fórmula

( ) ( ) ( )0

1, 1 1 , 1

ki n

i

n nE n k k i n

k i=

+ = = − + − ≥

∑

Nota 4: Poderíamos continuar a utilizar a fórmula da propriedade iii).

( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( )

26

0

0 6 1 6 2 6

6 6 6

6 6 16,2 1 2 1

2

7 7 71 3 0 1 3 1 1 3 2

0 1 2

7! 7! 7!3 2 1

0!7! 1!6! 2!5!

729 448 21 302

i

i

E ii=

+ = = − + − =

= − − + − − + − − =

= − + =

= − + =

∑

Portanto, existem 302 permutações de { }1,2,3,4,5,6com, exactamente, dois

excedentes.

d) exactamente dois descendentes;

Reparemos que ( ),n

E n kk

= é o número de permutações com k ascendentes ou o

número de permutações com k descendentes ou o número de permutações com k

excedentes ou, ainda, o número de permutações com 1k + excedentes fracos. Assim,

para calcular o número de permutações com exactamente dois descendentes,

podemos calcular 6

.2

Na alínea anterior, vimos que 6

302.2

= Logo, existem 302 permutações de

{ }1,2,3,4,5,6 com, exactamente, dois descendentes.

e) seis excedentes fracos.

9

Como já vimos, ( ),

nE n k

k= é o número de permutações com 1k +

excedentes

fracos. Portanto, para determinar o número de permutações de { }1,2,3,4,5,6com seis

excedentes fracos, temos de pensar qual será o valor de k. Para isso basta reparar que

1k + terá de ser, necessariamente, igual a 6, já que este é o número de excedentes

fracos. Portanto, 1 6 5k k+ = ⇔ = .

Assim, para determinarmos o número de permutações de { }1,2,3,4,5,6 com seis

excedentes fracos, basta calcularmos

6 61

5 0

n

k= = =

pela propriedade i)

Portanto, existe apenas uma permutação de { }1,2,3,4,5,6 com seis excedentes

fracos. Também podemos reparar que só existe uma permutação de { }1,2,3,4,5,6

com apenas um excedente fraco, já que 6

10

= . Verificamos que neste caso k

(número de ascendentes) é 0, logo o número de excedentes fracos será

1 0 1 1k + = + = . Assim, existe apenas uma permutação de { }1,2,3,4,5,6 que não tem

ascendentes e uma permutação de { }1,2,3,4,5,6 que tem apenas um excedente fraco.

Deste modo, verificámos a importância da utilização dos números de Euler. Sem este

método, seria quase impossível determinar o número de permutações de um

determinado conjunto com um certo número de ascendentes, descendentes, excedentes e

excedentes fracos.

O método utilizado no Exemplo 1 é prático apenas para conjuntos pequenos, onde

podemos facilmente determinar todas as suas permutações. Quando passamos para

conjuntos maiores, este método torna-se quase impraticável, o que nos leva aos

Números de Euler, já que é um método muito mais prático e de fácil utilização.

Education

Números de Euler