Ementa

Ementa
Funções Geradoras
Relações de Recorrência
Introdução à Teoria dos Grafos Grafos – Conceitos Básicos
Grafos e Subgrafos
Conectividade
Representações
Instituto Multidisciplinar Listas e Matrizes de Adjacências
Universidade Federal Rural do Rio de Janeiro Árvores e Florestas
Grafos e Árvores Geradoras

Ementa Ementa

Ementa Ementa
Circuitos Eulerianos Busca em Largura
Ciclos Hamiltonianos Busca em Profundidade
Emparelhamento em Grafos Busca em Largura Lexicográfica
Cliques e Conjuntos Independentes Aplicações
Número e Índice Cromático
Coloração de Vértices e Arestas
Planaridade
Grafos Direcionados
Classes de Grafos e Caracterizações

Conteúdo Programático Conteúdo Programático

Conteúdo Programático Conteúdo Programático

Unidade I – Funções Geradoras e Unidade II – Teoria dos Grafos –
Relações de Recorrência Definições e Problemas
1. Funções Geradoras – Definição 1. Conceitos Básicos
2. Funções Geradoras – Exemplos de Aplicações 2. Representações
3. Relações de Recorrência - Definição 3. Algoritmos de Busca
4. Relações de Recorrência – Exemplos de 4. Árvores
Aplicações 5. Circuitos Eulerianos
6. Ciclos Hamiltonianos
7. Emparelhamentos

1
Conteúdo Programático Conteúdo Programático

Conteúdo Programático Conteúdo Programático

Unidade II – Teoria dos Grafos – Unidade III – Teoria dos Grafos –
Definições e Problemas Algoritmos
8. Cliques e Conjuntos Independentes 1. Busca em Largura
9. Coloração em Grafos 2. Busca em Profundidade
10. Planaridade 3. Busca em Largura Lexicográfica
11. Grafos Direcionados
12. Classes de Grafos

Avaliação Funções Geradoras

Notas Introdução
MP = P1 + P2 MF = OP + M2 Ferramenta utilizada em vários problemas de contagem (ver
2 2 [1]).
P1 = Prova 1 (Trabalhos 01 a 06) Como exemplo, de quantas maneiras podemos trocar uma nota
P2 = Prova 2 (Trabalhos 07 a 12) de um real em moedas de 1, 5, 10, 25 e 50 centavos?
MP = Média Parcial
Representação das possíveis escolhas:
M1 = Menor Nota dentre P1 e P2 0 1 1 1 1 1 1 …

M2 = Maior Nota dentre P1 e P2 0 5 5 5 5 5 5 …

OP = Prova Optativa (considerada apenas se a nota obtida for maior do 0 10 10 10 10 10 10 …

que a menor nota dentre P1 e P2) …

0 25 25 25 25 25 25
MF = Média Final
0 50 50 50 50 50 50 …

Funções Geradoras Funções Geradoras

Introdução Introdução

Ferramenta utilizada em vários problemas de contagem (ver Ferramenta utilizada em vários problemas de contagem (ver
[1]). [1]).
Como exemplo, de quantas maneiras podemos trocar uma nota Como exemplo, de quantas maneiras podemos trocar uma nota
de um real em moedas de 1, 5, 10, 25 e 50 centavos? de um real em moedas de 1, 5, 10, 25 e 50 centavos?
Representação das possíveis escolhas: Representação das possíveis escolhas:
0 1 1 1 1 1 1 … 0 1 1 1 1 1 1 …

0 5 5 5 5 5 5 … 0 5 5 5 5 5 5 …

0 10 10 10 10 10 10 … $ 0,25 0 10 10 10 10 10 10 … $ 0,25
0 25 25 25 25 25 25 … 0 25 25 25 25 25 25 …

0 50 50 50 50 50 50 … 0 50 50 50 50 50 50 …

2
Funções Geradoras Funções Geradoras

Introdução Iremos escrever cada uma das linhas como uma soma, e
introduzir uma variável x representando um centavo. Assim,
as 5 somas infinitas são:
Ferramenta utilizada em vários problemas de contagem (ver
[1]). (1 + x + x 2 + x 3 + K) ×
Como exemplo, de quantas maneiras podemos trocar uma nota (1 + x 5 + x10 + x15 + K) ×
de um real em moedas de 1, 5, 10, 25 e 50 centavos? (1 + x10 + x 20 + x 30 + K) ×
Representação das possíveis escolhas:
0 1 1 1 1 1 1 …
(1 + x 25 + x 50 + x 75 + K) ×
0 5 5 5 5 5 5 … (1 + x 50 + x100 + x150 + K) ×
0 10 10 10 10 10 10 … $ 0,25
0 25 25 25 25 25 25 …

0 50 50 50 50 50 50 …

Funções Geradoras Funções Geradoras

Iremos escrever cada uma das linhas como uma soma, e Iremos escrever cada uma das linhas como uma soma, e
introduzir uma variável x representando um centavo. Assim, introduzir uma variável x representando um centavo. Assim,
as 5 somas infinitas são: as 5 somas infinitas são:

(1 + x + x 2 + x 3 + K) × (1 + x + x 2 + x 3 + K) ×
(1 + x + x + x + K) ×
5 10 15
(1 + x 5 + x10 + x15 + K) ×
(1 + x + x + x + K) ×
10 20 30
x25 (1 + x10 + x 20 + x 30 + K) × x25
(1 + x + x + x + K) ×
25 50 75
(1 + x + x + x + K) ×
25 50 75

(1 + x + x
50 100
+x 150
+ K) × (1 + x 50 + x100 + x150 + K) ×

Funções Geradoras Funções Geradoras

Iremos escrever cada uma das linhas como uma soma, e Iremos escrever cada uma das linhas como uma soma, e
introduzir uma variável x representando um centavo. Assim, introduzir uma variável x representando um centavo. Assim,
as 5 somas infinitas são: as 5 somas infinitas são:

(1 + x + x 2 + x 3 + K) × (1 + x + x 2 + x 3 + K) ×
(1 + x + x + x + K) ×
5 10 15
(1 + x 5 + x10 + x15 + K) ×
(1 + x + x + x + K) ×
10 20 30
x25 (1 + x10 + x 20 + x 30 + K) ×
(1 + x + x + x + K) ×
25 50 75
(1 + x 25 + x 50 + x 75 + K) ×
(1 + x 50 + x100 + x150 + K) × (1 + x 50 + x100 + x150 + K) ×

que é a função geradora para a seqüência ( En ), onde Ei conta

o número de formas de se trocar i centavos usando estes tipos
de moedas.

3
Funções Geradoras Funções Geradoras
Combinando os termos com mesmo expoente, obtemos: Assim
1
S=
1 + E1 x + E2 x 2 + E3 x 3 + K + E100 x100 + K 1− x

E a solução do problema apresentado é dada por E100 . Similarmente,

1
Seja f (x) dada pela série = 1 + x 5 + x10 + x15 + K
1 − x5
f ( x) = 1 + x + x 2 + x 3 + K
1
Considerando = 1 + x10 + x 20 + x 30 + K
1 − x10
S = 1 + x + x 2 + x3 + K 1
temos = 1 + x 25 + x 50 + x 75 + K
1 − x 25
S (1 − x) = 1 + x + x 2 + x 3 + K 1
= 1 + x 50 + x100 + x150 + K
− x − x 2 − x3 − K = 1 1 − x 50

Funções Geradoras Funções Geradoras

E
∞ ∞
1 1
E x
n −0
n
n
=
(1 − x)(1 − x )(1 − x10 )(1 − x 25 )(1 − x 50 )
5
. =  Bn x n ,
(1 − x)(1 − x ) n =0
5
(2)

(Função geradora para a seqüência E0 , E1 , E2 , K .) ∞

1
=  Cn x n , (3)
(1 − x)(1 − x )(1 − x ) n =0
5 10
Para obtermos E100 , iremos usar uma seqüência de
problemas relacionados. ∞
1
=  Dn x n , e (4)
Sejam (1 − x)(1 − x 5 )(1 − x10 )(1 − x 25 ) n=0
∞
1 1 ∞
=  An x n , (1) =  En x n . (5)
1 − x n=0 (1 − x)(1 − x 5 )(1 − x10 )(1 − x 25 )(1 − x 50 ) n−0

Funções Geradoras Funções Geradoras

Temos An = 1 , para todo n ≥ 0 . Temos An = 1 , para todo n ≥ 0 .

Para obtermos Bn , multiplicamos ambos os lados da equação Para obtermos Bn , multiplicamos ambos os lados da equação
(2) por (1 − x 5 ) , obtendo (2) por (1 − x 5 ) , obtendo

∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

A x
n =0
n
n
= (1 − x 5 ) Bn x n =  Bn x n −  Bn x n +5 .
n =0 n=0 n =0
A x
n =0
n
n
= (1 − x 5 ) Bn x n =  Bn x n −  Bn x n +5 .
n =0 n=0 n =0

4
Funções Geradoras Funções Geradoras
Temos An = 1 , para todo n ≥ 0 . Assim,
An = Bn − Bn −5 .
Para obtermos Bn , multiplicamos ambos os lados da equação
(2) por (1 − x 5 ) , obtendo Ou
Bn = An + Bn −5 .
∞ ∞ ∞ ∞

A x
n =0
n
n
= (1 − x ) Bn x =  Bn x −  Bn x
5

n =0
n

n=0
n

n =0
n +5
. De forma análoga, podemos também obter

Cn = Bn + Cn −10
Os coeficientes de x n têm que ser iguais para todo n . Dn = Cn + Dn −25
No lado esquerdo da equação, temos apenas An . En = Dn + En −50
Nos somatórios do lado direito, o primeiro somatório contribui Sabemos que An = Bn = Cn = Dn = En = 0 , para n < 0 , e
com o termo Bn x n, e o segundo somatório contribui com o
A = 1 para todo n ≥ 0 .
termo Bn −5 x n (i.e. considerando cada um dos x n’s...). n

Funções Geradoras Funções Geradoras

Portanto, Prosseguindo com o procedimento, temos
B10 = 3
B0 = A0 + B−5 = 1 + 0 = 1
B15 = 4
B1 = A1 + B− 4 = 1 + 0 = 1
B20 = 5
M
M
B4 = A4 + B−1 = 1 + 0 = 1
B100 = 21

B5 = A5 + B0 = 1 + 1 = 2 Observamos que não é necessário calcularmos todos os termos

intermediários para obtermos E100 .
M
As seguintes tabelas mostram o mínimo de entradas necessárias
B9 = A9 + B4 = 1 + 1 = 2
para obtermos E100 .

Funções Geradoras Funções Geradoras

n 0 5 10 15 20 25 30 35 40 45 50 n 0 5 10 15 20 25 30 35 40 45 50
Bn 1 2 3 4 5 6 7 8 9 10 11 Bn 1 2 3 4 5 6 7 8 9 10 11
Cn 1 2 4 6 9 12 16 20 25 30 36 Cn 1 2 4 6 9 12 16 20 25 30 36
Dn 1 12 + 1 = 13 49 Dn 1 13 36 + 13 = 49
En 1 50 En 1 50

n 55 60 65 70 75 80 85 90 95 100 n 55 60 65 70 75 80 85 90 95 100
Bn 12 13 14 15 16 17 18 19 20 21 Bn 12 13 14 15 16 17 18 19 20 21
Cn 42 49 56 64 72 81 100 121 Cn 42 49 56 64 72 81 100 121
Dn 121 242 Dn 121 242
En 292 En 292

5
Funções Geradoras Funções Geradoras

n 0 5 10 15 20 25 30 35 40 45 50 n 0 5 10 15 20 25 30 35 40 45 50
Bn 1 2 3 4 5 6 7 8 9 10 11 Bn 1 2 3 4 5 6 7 8 9 10 11
Cn 1 2 4 6 9 12 16 20 25 30 36 Cn 1 2 4 6 9 12 16 20 25 30 36
Dn 1 13 49 Dn 1 13 49
En 1 50 En 1 50

n 55 60 65 70 75 80 85 90 95 100 n 55 60 65 70 75 80 85 90 95 100
Bn 12 13 14 15 16 17 18 19 20 21 Bn 12 13 14 15 16 17 18 19 20 21
Cn 42 49 56 64 72 81 100 121 Cn 42 49 56 64 72 81 100 121
Dn 72 + 49 = 121 242 Dn 121 121 + 121 = 242
En 292 En 292

Funções Geradoras Funções Geradoras

n 0 5 10 15 20 25 30 35 40 45 50 n 0 5 10 15 20 25 30 35 40 45 50
Bn 1 2 3 4 5 6 7 8 9 10 11 Bn 1 2 3 4 5 6 7 8 9 10 11
Cn 1 2 4 6 9 12 16 20 25 30 36 Cn 1 2 4 6 9 12 16 20 25 30 36
Dn 1 13 49 Dn 1 13 49
En 1 49 + 1 = 50 En 1 50

n 55 60 65 70 75 80 85 90 95 100 n 55 60 65 70 75 80 85 90 95 100
Bn 12 13 14 15 16 17 18 19 20 21 Bn 12 13 14 15 16 17 18 19 20 21
Cn 42 49 56 64 72 81 100 121 Cn 42 49 56 64 72 81 100 121
Dn 121 242 Dn 121 242
En 292 En 242 + 50 = 292

Funções Geradoras Funções Geradoras

Temos E100 = 292 . (Ver [1].) onde

a variável x1 pertence ao conjunto { 3 , 4 , 5 } e

Em disciplinas de Combinatória estudamos a resolução de
equações do tipo as variáveis x2 e x3 pertencem ao conjunto { 4 , 5 , 6 } .

x1 + x2 + L + xr = m Definimos três polinômios, um para cada variável xi , como

segue [2]:
em inteiros não-negativos, sem nenhuma restrição adicional às
variáveis xi , para 1 ≤ i ≤ r (ver [2, 3]).
p1 = x 3 + x 4 + x 5 ;
Considere o problema de encontrarmos o número de soluções
p2 = x 4 + x 5 + x 6 ;
inteiras da equação
p3 = x 4 + x 5 + x 6 .
x1 + x2 + x3 = 14 ,

6
Funções Geradoras Funções Geradoras
Os expoentes de xi em pi são os elementos do conjunto ao Temos
qual xi pertence.
p( x) = x11 + 3x12 + 6 x13 + 7 x14 + 6 x15 + 3x16 + x17 .
Buscamos números cuja soma seja 14 e que estejam, cada um,
num conjunto cujos elementos sejam os expoentes dos Assim, a equação x1 + x2 + x3 = 14 possui 7 soluções
polinômios acima. inteiras com as restrições dadas.

Seja p (x) o produto destes três polinômios

3 5 6
Um termo como x x x corresponde à solução x1 = 3 ,
p( x) = p1 ⋅ p2 ⋅ p3 = ( x + x + x )( x + x + x )( x + x + x ).
3 4 5 4 5 6 4 5 6 x2 = 5 e x3 = 6 .
4 6 4
Um termo como x x x corresponde à solução x1 = 4 ,
A resposta para o nosso problema será o coeficiente de x14 . x2 = 6 e x = 4 .
3

Funções Geradoras Funções Geradoras

O polinômio apresentado gera o número de soluções para todas onde ai é um número real, para i = 0 , 1 , 2 , 3 , K , e x é
as equações uma variável.

x1 + x2 + x3 = m Observamos que qualquer polinômio em x é uma série de

potências.
para
Se a0 + a1 x + a2 x 2 + L e b0 + b1 x + b2 x 2 + L são duas séries
m ∈{ 11, 12, 13, 14, 15, 16, 17 } de potências , então a soma destas duas séries é a série de
potências na qual o coeficiente de x r é dado por ar + br e o
com as restrições impostas às variáveis xi , para i = 1, 2, 3 . produto destas duas séries é a série de potências na qual o
coeficiente de x r é dado por a0br + a1br −1 + a2br − 2 + L + ar b0 .
Uma série de potências é uma série infinita da forma Se ar , para r = 0 , 1 , 2 , K , é o número de soluções de um
problema de combinatória, a função geradora ordinária para
a0 + a1 x + a2 x + a3 x + L
2 3
este problema é a série de potências

Funções Geradoras Funções Geradoras

a0 + a1 x + a2 x 2 + a3 x 3 + L (1 + x) n . (Ver [2].)
(6)
ou, de maneira geral, dada a sequência (ar ) , a função Como um segundo exemplo, considere o problema de
geradora ordinária para esta sequência é definida como a série determinarmos quantos são os modos de representarmos o
de potências (6). inteiro 10 como somas não ordenadas de inteiros distintos
pertencentes ao conjunto A = { 1, 2 , 3 , 4 , 5 , 6 } .
Como o número de maneiras de retirarmos r objetos de um
conjunto de n objetos distintos, r ≤ n , é Cnr , a função É fácil ver que a respota é 5.
geradora ordinária para este problema é 6+4
5 + 4 +1
f ( x) = Cn0 + Cn1 x + Cn2 x 2 + L + Cnn x n 6 + 3 +1
a qual, como sabemos, é igual a 5+3+ 2
4 + 3 + 2 +1

7
Funções Geradoras Funções Geradoras
i
Seja o segunte produto de polinômios: O termo 1 é interpretado como não escolher i , e x como a
escolha de i .
(1 + x)(1 + x2) (1 + x3) (1 + x4) (1 + x5) (1 + x6) =

= 1 + x + x 2 + 2 x 3 + 2 x 4 + 3x 5 + 4 x 6 + 4 x 7 + 4 x8 + Exemplos:

+ 5x + 5 x + 5x + 5 x + 4 x + 4 x + 4 x +
9 10 11 12 13 14 15
1) Considere uma caixa contendo quatro esferas: duas
amarelas, uma branca e uma cinza. Representaremos por a , b
+ 3x16 + 2 x17 + 2 x18 + x19 + x 20 + x 21. e c , as esferas de cor amarela, branca e cinza,
21
respectivamente. Podemos tirar uma ou mais esferas desta
O coeficiente de x10 é 5 , e o de x é 1. O coeficiente de x i caixa, não importando a ordem, como segue:
é o número de modos de representarmos i como somas de
elementos distintos do conjunto A . 1 Esfera: a , b ,c
2 Esferas: aa , ab , ac , bc
Podemos interpretar (1 + x ) como um polinômio controlador
i

da presença do elemento i ∈ A em uma soma. 3 Esferas: aab , aac , abc

4 Esferas: aabc

Funções Geradoras Funções Geradoras

Iremos associar os polinômios 1 + ax + a 2 x 2 , 1 + bx e 1 + cx Assim, sabemos que existem
às esferas de cor amarela, branca e cinza, respectivamente. 3 maneiras de retirarmos 1 esfera
O produto fica 4 maneiras de retirarmos 2 esferas
3 maneiras de retirarmos 3 esferas
(1 + ax + a 2 x 2 )(1 + bx)(1 + cx) = 1 + (a + b + c) x +
1 maneira de retirarmos 4 esferas
(a 2 + ab + ac + bc) x 2 + 1 maneiras de não retirarmos nenhuma esfera
(a 2b + a 2c + abc) x 3 + a 2bcx4

fornecendo a lista de possibilidades vista anteriormente.

2) Encontrar a função geradora para a seqüência
( ar ) = (0, 0, 1, 1, 1, 1, …).
Se queremos o número de diferentes seleções, podemos tomar
a = b = c = 1 , obtendo A série de potências procurada é
(1 + x + x )(1 + x)(1 + x) = 1 + 3 x + 4 x + 3 x + 1x .
2 2 3 4 f ( x) = 0 + 0 x + x 2 + x 3 + x 4 + x 5 + K

Funções Geradoras Funções Geradoras

Para apresentarmos a forma fechada, consideramos Teorema Sendo f ( x ) e g ( x ) as funções geradoras das
sequências (ar ) e (br ) respectivamente, temos:
f ( x) = x + x + x + x + K = x (1 + x + x + x + K)
2 3 4 5 2 2 3

(i) Af ( x ) + Bg ( x ) é a função geradora para a sequência

 1 
f ( x) = x 2   ( Aar + Bbr ) .
 1− x  ∞
 n
(ii) f ( x) g ( x) =    (a b ) x k n− k
n
.
3) Encontrar a seqüência cuja função geradora é dada por n =0 k =0

1 (iii) A função geradora para (a0 + a1 + L + ar ) é igual a

g ( x) = .
1 − x3 (1 + x + x 2
)
+ L f ( x) .
Temos
1
= 1 + x 3 + x 6 + x 9 + x12 + K (iv) A função geradora para (r ar ) é igual a xf ′( x ) , onde
1 − x3 f ′( x) é a derivada de f com respeito a x .
∞
Desta forma, g ( x) é a função geradora para
(1, 0, 0, 1, 0, 0, 1, 0, …).
(v)  f ( x)dx =  n =0
an
n +1 x n +1 .

8
Funções Geradoras Funções Geradoras
p
Teorema Temos Teorema O coeficiente de x na expansão de
u (u − 1) x u (u − 1) L (u − r + 1) x
2 r
(1 + x) u = 1 + ux + +L+ +L (1 + x + x 2 + x 3 + L) n
2! r!
Se considerarmos é igual a Cnp+ p −1 .

 u (u − 1) L (u − r + 1)
u   , se r > 0
  =  r!
  1
r (Ver [2].)
 , se r = 0,
∞
u 
teremos (1 + x) =    x .
u r

r =0 r
u 
O número   é chamado coeficiente binomial generalizado.
r
 

Referências

[1] G. Polya, R.E. Tarjan, D.R. Woods. “Notes on Introductory Combinatorics”.

Birkhäuser, 1983.

[2] J.P.O. Santos, M.P. Mello, I.T.C. Murari. “Introdução à Análise Combinatória”. 4a
Edição. Ciência Moderna, 2008.

[3] A.C. Morgado, J.B.P. de Carvalho, P.C.P. Carvalho, P. Fernandez. “Análise

Combinatória e Probabilidade”. SBM – Coleção do Professor de Matemática, 2020.