matemática discreta

Aula 7: Fun¸c˜ao geradora para os subconjuntos de
[n]
Bin´omio de Newton
N´umeros binomiais

mar¸co 4, 2014

Fun¸c˜ao geradora para os subconjuntos de [n]
Consideremos todos os subconjuntos de [2] := {1, 2}.
2[2] = {∅, {1}, {2}, {1, 2}}
Sejam x1 , x2 duas vari´aveis independentes,
(1 + x1 )(1 + x2 ) = 1 + x1 + x2 + x1 x2

Fun¸c˜ao geradora para os subconjuntos de [n]
Consideremos todos os subconjuntos de [2] := {1, 2}.
2[2] = {∅, {1}, {2}, {1, 2}}
Sejam x1 , x2 duas vari´aveis independentes,
(1 + x1 )(1 + x2 ) = 1 + x1 + x2 + x1 x2

xi = 1 i∈∅ xi = xj , j = 1, 2, i∈{j} xi = x1 x2 i∈{1,2} Fun¸c˜ao geradora para os subconjuntos de [n]
Consideremos todos os subconjuntos de [2] := {1, 2}.
2[2] = {∅, {1}, {2}, {1, 2}}
Sejam x1 , x2 duas vari´aveis independentes,
(1 + x1 )(1 + x2 ) = 1 + x1 + x2 + x1 x2

xi = 1 i∈∅ xi = xj , j = 1, 2, i∈{j} (1 + x1 )(1 + x2 ) =

i∈{1,2}

xi + i∈∅ xi = x1 x2

xi + i∈{1} xi + i∈{2} xi

xi = i∈{1,2} A⊆[2] i∈A

Fun¸c˜ao geradora dos subconjuntos de {1, 2, 3}

2[3] = {∅, {1}, {2}, {3, }, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

(1 + x1 )(1 + x2 )(1 + x3 )

=

1 + x1 + x2 + x3
+x1 x2 + x1 x3 + x2 x3
+x1 x2 x3

=

xi
A⊆[3] i∈A

Fun¸c˜ ao geradora dos subconjuntos de {1, . . . , n}

• Consideremos 2[n] = {todos os subconjuntos de [n]}, n ≥ 0.
A fun¸c˜ao geradora para os subconjuntos de [n] ´e
(1 + x1 )(1 + x2 ) · · · (1 + xn ) =

xi
A⊆[n] i∈A

Fa¸camos x1 = x2 = · · · = xn = x x |A|

(1 + x)n =
A⊆[n]

No segundo membro desta igualdade, agrupemos as parcelas da soma, segundo o cardinal de A, n x |A| =
A⊆[n]

x |A| k=0 A⊆[n]
|A|=k

Fun¸c˜ao geradora de subconjuntos de [n], teorema binomial e coeficientes binomiais
Quantos subconjuntos de [n] existem com cardinal k? Quantas
|A|
vezes ´e que o termo x k aparece na soma
?
A⊆[n] x n |A| x = k x |A| =
A⊆[n]
|A|=k

(1 + x)n

n k x k

x |A|

=
A⊆[n]
n

x |A|