analise combinatoria - Numeros de Catalan

Prévia do material em texto

MAT047: Ana´lise combinato´ria
Professor John MacQuarrie
Os nu´meros de Catalan
Uma outra sequeˆncia de nu´meros que aparece como a soluc¸a˜o de problemas
combinato´rios diversos e´ a sequeˆncia dos nu´meros de Catalan Cn.
Considere uma rede n× n assim (no desenho, n = 8):
(0, 0)
(n, n)
Primeira questa˜o (fa´cil): quantos caminhos de (0, 0) a (n, n) existem na
rede em quais podemos mudar ou para cima ou pra direita? Por exemplo, um
caminho poss´ıvel na rede acima e´:
(0, 0)
(n, n)
R: Para ir de (0, 0) a (n, n), temos que fazer exatamente n passos para cima e
n passos pra direita, enta˜o temos que fazer 2n passos em total. Vamos marcar
os passos com ∗’s:
∗ ∗ ∗ ∗ . . . ∗ ∗︸ ︷︷ ︸
2n
Para escolher um caminho, temos que escolher exatamente n das ∗’s para ser
os passos para cima (C). As outras sera˜o os passos pra direita (D). No exemplo
acima, o caminho corresponde a` escolha
D C C D D C D D D C C C C C D D
1
Enta˜o, em total, existem exatamente(
2n
n
)
caminhos.
Mas agora, vamos colocar a condic¸a˜o extra que nossos caminhos nunca po-
deriam passar em cima da diagonal x = y. O caminho acima na˜o satisfaz esta
condic¸a˜o:
(0, 0)
(n, n)
Seja Cn o nu´mero de caminhos que nunca passam em cima da diagonal. Este
nu´mero Cn e´ o n-e´simo nu´mero de Catalan. A demonstrac¸a˜o do valor de Cn
usa um truque engenhoso chamado “o princ´ıpio da reflexa˜o”.
Se lembre um fato ba´sico de conjuntos:
Lema. A func¸a˜o α : Ω → Θ e´ bijetiva se, e somente se, existe uma func¸a˜o
β : Θ→ Ω (a inversa de α) tal que as composic¸o˜es
βα : Ω→ Ω , αβ : Θ→ Θ
sa˜o as func¸o˜es identidades.
Demonstrac¸a˜o. Vamos so´ mostrar uma direc¸a˜o: que se α possui inversa, enta˜o
α e´ uma bijec¸a˜o.
α injetiva: Suponha que α(x) = α(y) (x, y ∈ Ω). Enta˜o
x = βα(x) = βα(y) = y
logo α e´ injetiva.
α sobrejetiva: Pegue z ∈ Θ qualquer. Enta˜o
z = αβ(z) = α(β(z))
enta˜o α manda um elemento de Ω (nomeadamente β(z)) para z, logo α e´
sobrejetiva.
Ja´ que α e´ injetiva e sobrejetiva, segue que α e´ bijetiva.
Exerc´ıcio: mostre a outra direc¸a˜o – que se α e´ bijetiva, enta˜o existe uma inversa
de α.
2
O princ´ıpio da reflexa˜o se manifeste na pro´xima demonstrac¸a˜o:
Teorema. Temos
Cn =
(
2n
n
)
−
(
2n
n− 1
)
.
Demonstrac¸a˜o. Ja´ observamos que existem exatamente
(
2n
n
)
caminhos de (0, 0)
a (n, n) sem restric¸o˜es. Vamos contar quantos “caminhos maus”CMn existem,
que passam em cima da linha y = x. Teremos Cn =
(
2n
n
)− CMn.
Vamos mostrar que existe uma bijec¸a˜o entre os conjuntos
{Caminhos maus de (0, 0) a (n, n)} ←→ {Caminhos de (0, 0) a (n− 1, n+ 1)}
Funciona assim: pegue um caminho mau de (0, 0) a (n, n). Ja´ que ele passa em
cima da linha y = x, marca o ponto a onde ele cruza para cima pra primeira
vez:
(0, 0)
(n, n)
• a
primeira vez
em cima
Agora o truque: fazemos uma reflexa˜o na linha y = x + 1 de toda parte do
caminho a partir deste ponto:
(0, 0)
(n, n)
•
a
primeira vez
em cima
•(n− 1, n+ 1)
3
Observe que o caminho total
(normal ate´ a)− (refletida a partir de a)
e´, de fato, um caminho de (0, 0) a (n− 1, n+ 1), pois (n− 1, n+ 1) e´ a reflexa˜o
de (n, n) na linha y = x+ 1. Defina a func¸a˜o
α : {Caminhos maus de (0, 0) a (n, n)} → {Caminhos de (0, 0) a (n− 1, n+ 1)}
por mandar o caminho mau pro caminho definido assim.
Noutra direc¸a˜o, pegue um caminho de (0, 0) a (n− 1, n+ 1). Ja´ que o ponto
(n− 1, n+ 1) fica em cima da linha y = x, ele tem que passar em cima da linha
y = x. Seja a o primeiro ponto onde ele passa para cima. Podemos de novo
fazer uma reflexa˜o da parte deste caminho saindo de a, para obter um caminho
de (0, 0) a (n, n):
(0, 0)
(n, n)
•
a
•(n− 1, n+ 1)
Ja´ que o caminho refletido passa por a, que fica em cima da linha y = x, o
caminho obtido e´ um caminho mau. Obtemos assim uma func¸a˜o
β : {Caminhos de (0, 0) a (n− 1, n+ 1)} → {Caminhos maus de (0, 0) a (n, n)} .
E´ fa´cil confirmar que a func¸a˜o β e´ a func¸a˜o inversa de α, pois βα e αβ sa˜o as
func¸o˜es identidades (β “desfaz”o que α faz e α “desfaz”o que β faz). Logo α e´
uma bijec¸a˜o. Isto e´, o nu´mero CMn dos caminhos maus igual ao nu´mero dos
caminhos de (0, 0) a (n− 1, n+ 1).
Quantos caminhos de (0, 0) a (n− 1, n+ 1) existem? Ainda temos que fazer
(n− 1) + (n+ 1) = 2n passos em total. Para escolher um caminho, temos que
escolher as posic¸o˜es dos n− 1 passos a` direita. Enta˜o, existem ( 2nn−1) caminhos.
Concluindo enta˜o,
Cn =
(
2n
n
)
− CMn =
(
2n
n
)
−
(
2n
n− 1
)
.
4
Podemos simplificar a fo´rmula um pouco:
Corola´rio. Temos
Cn =
1
n+ 1
(
2n
n
)
.
Demonstrac¸a˜o. E´ so´ manipular a fo´rmula do teorema.
Cn =
(
2n
n
)
−
(
2n
n− 1
)
=
(
2n
n
)
− (2n)!
(n− 1)!(n+ 1)!
=
(
2n
n
)
− n · (2n)!
n!(n+ 1)!
=
(
2n
n
)
− n
n+ 1
· (2n)!
n!n!
=
(
2n
n
)
− n
n+ 1
·
(
2n
n
)
=
(
1− n
n+ 1
)(
2n
n
)
=
1
n+ 1
(
2n
n
)
.
Exemplo. Temos
C4 =
1
5
(
8
4
)
=
1
5
· 70 = 14.
Os caminhos sa˜o:
Mais um problema cuja soluc¸a˜o e´ os nu´meros de Catalan (tera´ outros na
lista):
5
Exemplo. No dia de “super-promoc¸a˜o”do cineˆma, o filme custa so´ (!) 10 reais.
Uns 10 pessoas querem formar uma fila para pagar. Daquelas pessoas, 5 esta˜o
com uma nota de 10 reais, e as outras 5 esta˜o com uma nota de 20 reais. A
caixa na˜o tem troco nenhum. Quantas filas as pessoas poderiam formar em
quais todo mundo que precisar de troco vai recebe´-lo na hora de pagar?
R: Denotam as pessoas com nota de dez por “D”e as pessoas com nota de vinte
por “V ”. A fila
1 2 3 4 5 6 7 8 9 10
D V D V V D D V D V
na˜o serve: pessoa 2 vai receber o troco de pessoa 1, e pessoa 4 vai receber o
troco de pessoa 3. Mas depois de pessoa 4 o troco acabou, enta˜o pessoa 5 na˜o
vai poder receber o seu troco de 20 na hora de pagar.
A condic¸a˜o da fila e´ que em nenhum subintervalo 1, . . . , s (1 6 s 6 10) temos
estritamente mais V do que D (a fila acima na˜o serve pois no intervalo 1 a 5
tem 3 pessoas V e somente 2 pessoas D).
Agora, troque perspectiva: se pensamos em V sendo “mudar para cima”e D
sendo “mudar pra direita”, enta˜o uma fila corresponde a um caminho de (0, 0)
a (5, 5). O caminho correspondente a` fila dada sera´:
D
V
A condic¸a˜o dada e´ equivalente a` condic¸a˜o que o caminho nunca pode passar
em cima da linha y = x. Logo o nu´mero das filas poss´ıveis (de V e D) e´ igual a
C5 =
1
6
(
10
5
)
= 42.
Para cada escolha de fila das V ’s e D’s, as pessoas V podem se permutar a
vontade e as pessoas D podem se permutar a vontade, enta˜o o nu´mero das filas
poss´ıveis e´:
42 · 5! · 5! = 604.800.
6