7 - Combinatória Wikipédia, a enciclopédia livre

Prévia do material em texto

29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 1/6
Combinatória
Origem: Wikipédia, a enciclopédia livre.
A combinatória é um ramo da matemática que estuda coleções finitas de elementos que satisfazem
critérios específicos determinados e se preocupa, em particular, com a "contagem" de elementos
nessas coleções (combinatória enumerativa), com decidir 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. E, o engenhoso Paul Erdős 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 × 1067. Comparando este número com alguns outros números grandes, ele é maior
que o quadrado do Número de Avogadro, 6,022 × 1023, quantidade equivalente a um mol".
Princípios aditivo e multiplicativo
Permutações simples
Arranjos
Arranjo com repetição
Arranjos sem repetição
Combinação
Combinação simples
Combinação com repetição
Funções enumerativas
Programa de teste
Resultados
Bibliografia
Ver também
Ligações externas
Índice
Princípios aditivo e multiplicativo
https://pt.wikipedia.org/wiki/Matem%C3%A1tica
https://pt.wikipedia.org/wiki/Princ%C3%ADpio_fundamental_da_contagem
https://pt.wikipedia.org/wiki/Percy_Alexander_MacMahon
https://pt.wikipedia.org/wiki/Gian-Carlo_Rota
https://pt.wikipedia.org/wiki/D%C3%A9cada_de_1960
https://pt.wikipedia.org/wiki/Paul_Erd%C5%91s
https://pt.wikipedia.org/wiki/Enumera%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Fatorial
https://pt.wikipedia.org/wiki/N%C3%BAmero_de_Avogadro
https://pt.wikipedia.org/wiki/Mol
29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 2/6
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 
.
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:
Em arranjos, a ordem dos objetos é importante.
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 de elementos tomados a , onde e é um número natural, é qualquer
ordenação de elementos entre 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.
Na combinação, a ordem em que os elementos são tomados não é importante.
Quando a ordem não importa, mas cada elemento pode ser contado apenas uma vez, o número de
combinações é o coeficiente binomial:
Permutações simples
Arranjos
Arranjo com repetição
Arranjos sem repetição
Combinação
Combinação simples
29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 3/6
Onde é o total de elementos e o número de elementos escolhidos.
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.
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 é
relevante). Permutações de k elementos do conjunto S são sequências de k diferentes elementos de S
(onde duas subsequê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 {Si} 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 Sn 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 Si 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 φ = (1 + √5) / 2, é a razão áurea. Porém, dado que estamos olhando para um conjunto de
inteiros, a presença de √5 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
Combinação com repetição
Funções enumerativas
https://pt.wikipedia.org/wiki/Conjunto
https://pt.wikipedia.org/wiki/Combina%C3%A7%C3%A3o_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/Permuta%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/N%C3%BAmero_natural
https://pt.wikipedia.org/w/index.php?title=F%C3%B3rmula_fechada&action=edit&redlink=1
https://pt.wikipedia.org/wiki/N%C3%BAmero_de_Fibonacci
https://pt.wikipedia.org/wiki/Raz%C3%A3o_%C3%A1urea
https://pt.wikipedia.org/w/index.php?title=Repeti%C3%A7%C3%A3o&action=edit&redlink=1
29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 4/6
que pode ser mais satisfatória (do ponto de vista puramente combinatório), visto que isto mostra
mais 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.O programa abaixo, escrito na linguagem Java, demonstra as tabelas de teste para uma formação de
Arranjo e Combinação para um conjunto de 4 elementos, {a, b, c, d}, em pares.
public class TestTable { 
 public static void main(String args[]) { 
 //Arrangement of Set[A to D] with 2 elements 
 testTable(true); 
 
 //Combination of Set[A to D] with 2 elements 
 testTable(false); 
 } 
 
 
 public static void testTable(boolean arrangement) { 
 int counter = 0; 
 java.util.Set<String> set = new java.util.TreeSet<String>(); 
 String s; 
 
 System.out.println(arrangement ? "Arrangement" : "Combination"); 
 
 for (char i = 'A'; i <= 'D'; i++) { 
 for (char j = 'A'; j <= 'D'; j++) { 
 if (i == j) continue; 
 
 if (!arrangement) { 
 s = j + ";" + i; 
 if (set.contains(s)) continue; 
 } 
Programa de teste
https://pt.wikipedia.org/w/index.php?title=F%C3%B3rmula_assint%C3%B3tica&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=S%C3%A9rie_de_pot%C3%AAncias_formal&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_geratriz
29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 5/6
 
 s = i + ";" + j; 
 if (set.contains(s)) continue; 
 
 if (set.add(s)) counter++; 
 } 
 } 
 
 for (String i : set) System.out.println(i); 
 
 System.out.println(String.format("Counter: %s\n", counter)); 
 } 
} 
 
//Output
/*
Arrangement
A;B
A;C
A;D
B;A
B;C
B;D
C;A
C;B
C;D
D;A
D;B
D;C
Hits: 12 
 
Combination
A;B
A;C
A;D
B;C
B;D
C;D
Hits: 6
*/
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 encontrem-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
qualquer uma que não conheça os outros dois.
A prova é uma curta prova por contradição: suponha que há 3 pessoas que cumpram 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 - A
deve ser uma das k pessoas que ele conhece. C deve ser uma das (5-k) pessoas que ele não conhece).
Portanto, é a pessoa B de 0*5=0, 1*4=4 ou 2*3=6 triplos. Como há 6 pessoas, e cada uma é o B de no
máximo 6 triplos, há no máximo 36 triplos.
Resultados
https://pt.wikipedia.org/wiki/Teorema
https://pt.wikipedia.org/wiki/Frank_P._Ramsey
https://pt.wikipedia.org/wiki/Prova_por_contradi%C3%A7%C3%A3o
https://pt.wikipedia.org/w/index.php?title=Sem_perda_da_generalidade&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teorema_Finito_de_Ramsey
https://pt.wikipedia.org/w/index.php?title=Contagem_dupla&action=edit&redlink=1
29/08/2020 Combinatória – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Combinatória 6/6
Agora considere um triplo das pessoas onde exatamente duas pessoas se conhecem. Está claro que
nós podemos formar com elas dois triplos distintos: deixando C a que é desconhecida, e colocando as
outras no lugar de A e B. Da mesma forma se exatamente 2 pares se conhecem, também se pode
organizar em um triplo de duas formas distintas: deixe A ser a pessoa que conhece ambos os outros, e
ainda B e C (em alguma ordem) que são dois que não se conhecem. Então, há 36/2=18 triplos no
máximo onde qualquer um exatamente 1 par ou exatamente 2 pares que se conhecem. Como há 20
triplos, deve haver no máximo 2 triplos qualquer que conhecem todos ou que não se conhecem entre
si.
A ideia de achar ordem em configurações aleatórias dá origem a teoria de Ramsey. Essencialmente
esta teoria diz que qualquer configuração suficientemente grande conterá, pelo menos, um caso de
qualquer outro tipo de configuração. Deve-se notar que as possibilidades combinatórias costumam
gerar números grandes, por exemplo, o maior número que foi usado (seriamente) pela matemática, o
número de Graham, aparece na solução de um problema da teoria de Ramsey.
GRAHAM, R. L.; GROETSCHEL, M.; LOVÁSZ, L. (eds.). Handbook of Combinatorics, Volumes 1
and 2. MIT Press, 1996. ISBN 0-262-07169-X
STANLEY, Richard P. Enumerative Combinatorics, Volumes 1 and 2 (http://www-math.mit.edu/~rs
tan/ec/). Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
Análise Combinatória (https://web.archive.org/web/20070210012901/http://pessoal.sercomtel.co
m.br/matematica/medio/combinat/combinat.htm)
Princípios combinatórios
Regra da soma
Regra do produto
Demonstração por bijeção
Princípio da inclusão-exclusão
Método de elementos distintos
Teoria musical dos conjuntos
Combinatória Infinita
Número sequencial combinatório
"Material de Combinatória" (http://www.ime.usp.br/%7Emota/PICME/combinatoria/)do projeto
PICME no IME-USP
Obtida de "https://pt.wikipedia.org/w/index.php?title=Combinatória&oldid=58041008"
Esta página foi editada pela última vez às 02h19min de 15 de abril de 2020.
Este texto é disponibilizado nos termos da licença Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC BY-SA 3.0) da
Creative Commons; pode estar sujeito a condições adicionais. Para mais detalhes, consulte as condições de utilização.
Bibliografia
Ver também
Ligações externas
https://pt.wikipedia.org/wiki/Teoria_de_Ramsey
https://pt.wikipedia.org/wiki/N%C3%BAmero_de_Graham
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/026207169X
http://www-math.mit.edu/~rstan/ec/
https://web.archive.org/web/20070210012901/http://pessoal.sercomtel.com.br/matematica/medio/combinat/combinat.htm
https://pt.wikipedia.org/wiki/Princ%C3%ADpios_combinat%C3%B3rios
https://pt.wikipedia.org/wiki/Regra_da_soma
https://pt.wikipedia.org/wiki/Regra_do_produto_(combinat%C3%B3ria)
https://pt.wikipedia.org/w/index.php?title=Demonstra%C3%A7%C3%A3o_por_bije%C3%A7%C3%A3o&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Princ%C3%ADpio_da_inclus%C3%A3o-exclus%C3%A3o
https://pt.wikipedia.org/w/index.php?title=M%C3%A9todo_de_elementos_distintos&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Teoria_musical_dos_conjuntos&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Combinat%C3%B3ria_Infinita&action=edit&redlink=1
https://pt.wikipedia.org/wiki/N%C3%BAmero_sequencial_combinat%C3%B3rio
http://www.ime.usp.br/~mota/PICME/combinatoria/
https://pt.wikipedia.org/w/index.php?title=Combinat%C3%B3ria&oldid=58041008
https://creativecommons.org/licenses/by-sa/3.0/deed.pt
https://foundation.wikimedia.org/wiki/Condi%C3%A7%C3%B5es_de_Uso