O
PRINCÍPIO DA INCLUSÃO-EXCLUSÃO
O
Principio da Inclusão-Exclusão é uma fórmula para se calcular o número de
elementos que pertencem à união de vários conjuntos não necessariamente
disjuntos. Na sua versão mais simples: (A
U B) = A + B - (A ∩ B): (A U B) é o número de elementos que
pertencem à pelo menos um dos conjuntos A
ou B. Assim, contamos os
elementos de A e os elementos
de B: A + B. Quando
fazemos isto, contamos os elementos de A
∩ B duas vezes.
Para
três conjuntos o Principio diz que:
(A
U B U C) = A + B + C – (A ∩ B) – (A ∩ C) – (B ∩ C) – (A ∩ B ∩ C)
Em suma o Princípio da Inclusão-Exclusão (PIE) é uma generalização de um dos princípios básico de contagem, o
princípio aditivo. Este princípio está interessado na obtenção de uma fórmula
para contar o número de elementos que pertencem a união de vários conjuntos não
necessariamente excludentes ou disjuntos. Na sua forma mais simples calcula a
cardinalidade da união de dois conjuntos A e B, no qual a intersecção entre A e
B dá-se um conjunto vazio.
LEMAS DE
KAPLANSKY
Primeiro
Lema de Kaplansky: O número de
p-subconjuntos de {1, 2
,..., n} nos quais não há dois números
consecutivos, considerando-se 1 e
n como consecutivos é:
f (n,p) = CPn-p+1
Segundo Lema de Kaplansky: O número de p-subconjuntos de {1, 2 ,..., n} nos quais não há dois números consecutivos, considerando-se 1 e n como consecutivos é:
f
(n,p) = (n / n – p)Cpn-p
PRINCÍPIO DAS GAVETAS DE DIRICHLET
Princípio das gavetas de
Dirichlet: Se n objetos
forem colocados em no máximo n-1 gavetas, então pelo
menos uma delas conterá no mínimo dois objetos.
Demonstração.
Suponha
que cada gaveta contém no máximo um objeto. Então o número total de objetos é
no máximo n - 1. Absurdo!
O Princípio de
Dirichlet pode ser reformulado como se segue:
Se m objetos são
colocados em n gavetas, então pelo menos uma gaveta contem [(m-1) / m] + 1 objetos.
Demonstração: Suponha que cada
gaveta tem no máximo [(m-1) / m] + 1 objetos. Então o número total de objetos
seria no máximo
[n (m-1) / m] ≤ [n(m-1)/m] = m – 1 <
m. Absurdo!
PRINCÍPIO
DA REFLEXÃO
Uma
partícula, estando no ponto (x; y)
pode se movimentar para o ponto (x + 1; y + 1) ou para o ponto (x
+ 1; y - 1) (subidas e
descidas). Pergunta-se:
a)
Quantos
são os trajetos possíveis de (0; 0)
a (8; 6)?
Vamos
representar um movimento do tipo (x+1; y+1) por S(subida) e do tipo (x+1; y-1) por D(descida).
Para ir de (0; 0) a (8; 6) devemos ter S + D = 8, pois em cada movimento, a abcissa da partícula avança uma
unidade. Também devemos ter S - D =
6, pois em cada movimento de subida a ordenada aumenta uma unidade e em cada
movimento de descida a ordenada diminui uma unidade. Assim, obtemos S = 7 e D = 1. O número de trajetos é
8C7,1
= 8
RELAÇÃO DE RECORRÊNCIA
Relação de recorrência (ou passo recorrente) é uma parte de uma Definição Recorrente
(definição onde o item sendo definido é parte dela mesma). É onde, após a
condição básica (caso simples, no qual o item sendo definido é especificado,
que nos dá condições de iniciar a Definição), novos casos do item sendo
definido são obtidos a partir de casos anteriores, formando uma sequência, um conjunto, uma
operação ou até mesmo um algoritmo.
Uma equação de diferenças é qualquer
problema onde deve-se determinar uma função (desconhecida) a partir de uma
relação de recorrência envolvendo o operador diferença.
PERMUTAÇÕES
CAÓTICAS
Uma permutação dos números (1, 2 ,..., n) é dita caótica quando
nenhum número está no seu lugar primitivo. Por exemplo, 2143 e 2341 são caóticas,
mas 1342 não é caótica. Seja Dn
o número de permutações caóticas de (1, 2 ,..., n) e defina
Ai = conjunto das
permutações de (1, 2 ,..., n) em que o número i ocupa o i-ésimo lugar, ou seja, está
em seu lugar primitivo. Assim, Dn
é o número de elementos do
conjunto Ω das permutações de (1, 2
,..., n) que pertencem a
exatamente zero dos subconjuntos A1,
A2 ,..., An.
Para Saber Mais:
BIANCHINI, Edwaldo.
PACCOLA, Herval. Matemática volume 2, em 3 volumes. Editora Moderna, 1995.
Enviado por Pedlazcar
Nenhum comentário:
Postar um comentário