COMBINATORIA

A combinatória é um ramo da matemática que estuda coleções finitas de objetos que satisfazem critérios específicos determinados, e se preocupa, em particular, com a "contagem" de objetos nessas coleções (combinatória enumerativa) e com a decisão de 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 × 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

  [esconder] 

• 1Princípios aditivo e multiplicativo
• 2Permutações simples
• 3Arranjos
  • 3.1Arranjo com repetição
  • 3.2Arranjo simples
• 4Combinação
  • 4.1Combinação simples
  • 4.2Combinação com repetição
• 5Funções enumerativas
• 6Programa de teste
• 7Resultados
• 8Bibliografia
• 9Ver também
• 10Ligações externas

Princípios aditivo e multiplicativo[editar | editar código-fonte]

Princípio aditivo: Dados os conjuntos ${\displaystyle A_{1},A_{2},...,A_{n}}$, dois a dois disjuntos, em que ${\displaystyle A_{i}}$ tem exatamente ${\displaystyle a_{i}}$ elementos, então o número de elementos da união ${\displaystyle A_{1}\cup A_{2}\cup A_{3}\cdots \cup A_{n}}$ é dado por ${\displaystyle a_{1}+a_{2}+a_{3}+...+a_{n}}$.

Princípio multiplicativo: Se um evento ${\displaystyle A_{i}}$ pode ocorrer de ${\displaystyle m_{i}}$ maneiras diferentes, então o número de maneiras de ocorrer os eventos ${\displaystyle A_{1},A_{2},...,A_{n}}$ de forma sucessiva é dado por ${\displaystyle m_{1}.m_{2}...m_{n}}$.

Permutações simples[editar | editar código-fonte]

Ver artigo principal: Permutação

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:

${\displaystyle P_{n}=n\cdot (n-1)\cdot (n-2)...2\cdot 1=n!}$

Arranjos[editar | editar código-fonte]

Em arranjos, a ordem dos objetos é importante.

Arranjo com repetição[editar | editar código-fonte]

Ver artigo principal: Sequência (Combinatória)

O arranjo com repetição é usado quando a ordem dos elementos importa e cada elemento pode ser contado mais de uma vez.

${\displaystyle AR_{r}^{n}=n^{r}}$

Onde ${\displaystyle n\,\!}$ é o total de elementos e ${\displaystyle r\,\!}$ o número de elementos escolhidos.

Arranjo simples[editar | editar código-fonte]

Arranjo simples de ${\displaystyle n}$ elementos tomados ${\displaystyle r}$ a ${\displaystyle r}$, onde ${\displaystyle n>=1}$ e ${\displaystyle r}$ é um número natural, é qualquer ordenação de ${\displaystyle r}$ elementos entre os ${\displaystyle n}$ 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:

${\displaystyle A_{r}^{n}={\frac {n!}{\left(n-r\right)!}}}$

Onde ${\displaystyle n\,\!}$ é o total de elementos e ${\displaystyle r\,\!}$ o número de elementos escolhidos.

Combinação[editar | editar código-fonte]

Na combinação, a ordem em que os elementos são tomados não é importante.

Combinação simples[editar | editar código-fonte]

Ver artigo principal: Combinação (matemática)

Quando a ordem não importa, mas cada elemento pode ser contado apenas uma vez, o número de combinações é o coeficiente binomial:

${\displaystyle C_{r}^{n}={n \choose r}={\frac {n!}{r!\cdot \left(n-r\right)!}}}$

Onde ${\displaystyle n\,\!}$ é o total de elementos e ${\displaystyle r\,\!}$ o número de elementos escolhidos.

Combinação com repetição[editar | editar código-fonte]

Ver artigo principal: Seleçã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 é

${\displaystyle CR_{r}^{n}={{n+r-1} \choose {r}}={{(n+r-1)!} \over {r!(n-1)!}}}$

Onde ${\displaystyle n\,\!}$ é o total de elementos e ${\displaystyle r\,\!}$ o número de elementos escolhidos.

Funções enumerativas[editar | editar código-fonte]

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 Stendo k elementos (onde a ordem em que são listados os elementos não são relevantes). 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 {S_i} 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_n 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_i 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 é:

${\displaystyle f(n)={\frac {\phi ^{n+2}}{\sqrt {5}}}-{\frac {(1-\phi )^{n+2}}{\sqrt {5}}}}$

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

${\displaystyle f(n)=f(n-1)+f(n-2)}$

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

${\displaystyle f(n)\sim {\frac {\phi ^{n+2}}{\sqrt {5}}}}$

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

${\displaystyle \sum f(n)x^{n}}$

como uma função geratriz exponencial

${\displaystyle \sum f(n){\frac {x^{n}}{n!}}}$

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.

Programa de teste[editar | editar código-fonte]

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;
    }

    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
*/

Resultados[editar | editar código-fonte]

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 - 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.

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.

Bibliografia[editar | editar código-fonte]

• 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. Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
• Análise Combinatória

Ver também[editar | editar código-fonte]

Outros projetos Wikimedia também contêm material sobre este tema:
	Livros e manuais no Wikilivros

• 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

Ligações externas[editar | editar código-fonte]

• "Material de Combinatória"do projeto PICME no IME-USP