Combinatória – Wikipédia  a enciclopédia livre
6 pág.

Combinatória – Wikipédia a enciclopédia livre


DisciplinaAlgoritmos16.038 materiais200.099 seguidores
Pré-visualização2 páginas
O triângulo de Pascal, intimamente relacionado
como o teorema binomial.
Combinatória
Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Análise combinatória)
A combinatória é um ramo da matemática que estuda
coleções finitas de objetos que satisfaçam certos
critérios específicos, e se preocupa, em particular, com
a "contagem" de objetos nessas coleções
(combinatória enumerativa) e com a decisão se certo
objeto "ótimo" existe (combinatória extremal) e com
estruturas "algébricas" que esses objetos possam ter
(combinatória algébrica).
O assunto ganhou notoriedade após a publicação de
"Análise Combinatória" por Percy Alexander
MacMahon em 1915. Um dos destacados combinatorialistas foi Gian-Carlo Rota, que ajudou a formalizar o
assunto a partir da década de 1960. O engenhoso Paul Erd\u151s trabalhou principalmente em problemas
extremais. O estudo de como contar os objetos é algumas vezes considerado separadamente como um campo
da enumeração.
Um exemplo de problema combinatório é o seguinte: Quantas ordenações é possível fazer com um baralho de
52 cartas? O número é igual a 52! (ou seja, "cinquenta e dois fatorial"), que é o produto de todos os números
naturais de 1 até 52. Pode parecer surpreendente o quão enorme é esse número, cerca de 8,065817517094 ×
10 . Comparando este número com alguns outros números grandes, ele é maior que o quadrado do Número
de Avogadro, 6,022 × 10 , quantidade equivalente a um mol".
Índice
1 Princípios aditivo e multiplicativo
2 Permutações simples
3 Arranjos
3.1 Arranjo com repetição
3.2 Arranjo simples
4 Combinação
4.1 Combinação simples
4.2 Combinação com repetição
5 Funções enumerativas
6 Resultados
7 Bibliografia
8 Ligações externas
9 Ver também
Princípios aditivo e multiplicativo
67
23
Princípio aditivo: Dados os conjuntos , dois a dois disjuntos, em que tem exatamente 
elementos, então o número de elementos da união é dado por 
.
Princípio multiplicativo: Se um evento pode ocorrer de maneiras diferentes, então o número de
maneiras de ocorrer os eventos de forma sucessiva é dado por .
Permutações simples
Definimos permutações simples como sendo o número de maneiras de arrumar n elementos em n posições
em que cada maneira se diferencia pela ordem em que os elementos aparecem. Aplicando o princípio da
multiplicação obtemos a seguinte equação para permutações simples:
Arranjos
Em arranjos, a ordem dos objetos é importante.
Arranjo com repetição
O arranjo com repetição é usado quando a ordem dos elementos importa e cada elemento pode ser contado
mais de uma vez.
Onde é o total de elementos e o número de elementos escolhidos.
Arranjo simples
Arranjo simples de elementos tomados a , onde e é um número natural, é qualquer
ordenação de elementos dentre os elementos, em que cada maneira de tomar os elementos se diferenciam
pela ordem e natureza dos elementos.
A fórmula para cálculo de arranjo simples é dada por:
Onde é o total de elementos e o número de elementos escolhidos.
Combinação
Na combinação, a ordem em que os elementos são tomados não é importante.
Combinação simples
Quando a ordem não importa, mas cada elemento pode ser contado apenas uma vez, o número de
combinações é o coeficiente binomial:
Onde é o total de elementos e o número de elementos escolhidos.
Combinação com repetição
Quando a ordem não importa, mas cada objeto pode ser escolhido mais de uma vez, o número de
combinações é
Onde é o total de elementos e o número de elementos escolhidos.
Funções enumerativas
Calcular o número de maneiras que certos arranjos podem ser formados é o princípio da combinatória.
Considerando S um conjunto com n elementos. As combinações de k elementos de S são subconjuntos de S
tendo k elementos (onde a ordem em que são listados os elementos não são irrelevantes). Permutações de k
elementos do conjunto S são seqüências de k diferentes elementos de S (onde duas subseqüências são
consideradas diferentes se contêm o mesmo elemento, mas em ordens diferentes). Fórmulas para o número de
permutações e combinações são bem conhecidas e importantes para a combinatória.
De modo geral, dada uma coleção infinita de finitos conjuntos {S } cujo índice tipicamente recorre aos números
naturais, combinatória enumerativa estuda as diversas formas de descrever uma função enumerativa, f(n), que
conte o número de elementos em S para qualquer n. Ainda que contar o número de elementos seja um
problema onipresente na matemática, em um problema combinatório os elementos S geralmente terão uma
descrição combinatorial relativamente simples, e pouca estrutura adicional.
As funções mais simples são, deste modo, fórmulas fechadas, que podem ser expressas como uma
composição de funções elementares tais como fatoriais, potências, etc. Como foi dito anteriormente, o número
de ordenações distintas possíveis de um maço de baralho de n cartas é f(n) = n!.
Este método nem sempre pode ser totalmente satisfatória (ou prática) para qualquer problema combinatório.
Por exemplo, considerando que f(n) seja o número de subconjuntos distintos formados a partir dos inteiros no
intervalo [1,n] que não contenha dois números inteiros consecutivos; assim, com n = 4, teremos {}, {1}, {2},
{3}, {4}, {1,3}, {1,4}, {2,4}, logo f(4) = 8. Verifica-se que f(n) resulta no chamado número de Fibonacci de
ordem n+2, cuja expressão em uma fórmula fechada é:
onde \u3c6 = (1 + \u221a5) / 2, é a razão áurea. Porém, dado que estamos olhando para um conjunto de inteiros, a
presença de \u221a5 no resultado deve ser considerado como "antiestética" do ponto de vista combinatório. De
modo alternativo, f(n) pode ser expressa como a repetição
que pode ser mais satisfatória (do ponto de vista puramente combinatório), visto que isto mostra mais
i
n
i
claramente porque o resultado é como ele é.
Outro método é encontrar uma fórmula assintótica
f(n) ~ g(n)
onde g(n) é uma função "familiar", e onde f(n) se aproxima a g(n) como n tende ao infinito. Em alguns casos
uma simples função assintótica pode ser preferível do que uma terrível e complicada fórmula fechada que não
proporciona nenhum critério de comportamento de objetos contados. No exemplo abaixo, uma fórmula
assintótica seria
quando n é muito grande.
Finalmente, e mais prático, f(n) pode ser expressa por uma série de potências formal, chamada função
geratriz, que pode ser tanto a função geratriz ordinária
como uma função geratriz exponencial
Uma vez determinada, a função geratriz permite extrair todas as formas anteriores de expressar f(n). Na
demais, as várias operações naturais com funções geratrizes como a adição, multiplicação, diferenciação, etc.,
tem um significado combinatório; e isso permite estender resultados de um problema combinatório com a
finalidade de resolver outros.
Resultados
Algumas configurações muito sutis podem ser desenvolvidas e alguns teoremas surpreendentes podem ser
provados. Um exemplo de tais teoremas se deve a Frank P. Ramsey:
Suponha que 6 pessoas encontrarem-se em uma festa. Cada par qualquer conhecem-se ou não se conhecem.
Em todo caso, sempre se pode encontrar 3 dessas 6 pessoas que se conhecem entre si, ou que nenhuma não
conheça os outros dois.
A prova é uma curta prova por contradição: suponha que há 3 pessoas cumpra o que afirma o teorema.
Considerando uma pessoa qualquer das 6 que está na festa chamada de pessoa A: das 5 pessoas restantes, há
pelo menos três que ou conhecem A (e A os conhece), ou não a conhecem. Sem perda da generalidade,
assuma que três pessoas conheçam A. Então, entre essas três pessoas deve haver pelo menos duas que se
conheçam (ao contrário, teríamos 3 pessoas que não se conhecem entre si). Com isso, essas pessoas e A se
conhecem entre si. (Este é um caso especial do Teorema de Ramsey.
Pode-se conseguir demonstração alternativa mediante contagem dupla: contam-se o número de triplos
ordenados de pessoas (A, B, C) onde as pessoas A e B se conhecem, mas B não conhece C. Suponhamos
que a pessoa K conheça k dos outros 5. Então a pessoa B é exatamente k(5-k) triplos