Combinatória
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, com decidir se certo objeto "ótimo" existe e com estruturas "algébricas" que esses objetos possam ter.
Imagem: Dnu72 · BY-SA · Openverse
Princípio aditivo: Dados os conjuntos A 1 , A 2 , . . . , A n {\displaystyle A_{1},A_{2},...,A_{n}} , dois a dois disjuntos, em que A i {\displaystyle A_{i}} tem exatamente a i {\displaystyle a_{i}} elementos, então o número de elementos da união A 1 ∪ A 2 ∪ A 3 ⋯ ∪ A n {\displaystyle A_{1}\cup A_{2}\cup A_{3}\cdots \cup A_{n}} é dado por a 1 + a 2 + a 3 + . . . + a n {\displaystyle a_{1}+a_{2}+a_{3}+...+a_{n}} . Princípio multiplicativo: Se um evento A i {\displaystyle A_{i}} pode ocorrer de m i {\displaystyle m_{i}} maneiras diferentes, então o número de maneiras de ocorrer os eventos A 1 , A 2 , . . . , A n {\displaystyle A_{1},A_{2},...,A_{n}} de forma sucessiva é dado por m 1 . m 2 . . . m n {\displaystyle m_{1}.m_{2}...m_{n}} .
Imagem: c-pyanelly · BY · Openverse
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 multiplicativo obtemos a seguinte equação para permutações simples:
Imagem: ENEMEX OFICIAL · BY-NC-SA · Openverse
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. A R n r = n r {\displaystyle AR_{n}^{r}=n^{r}} Em que n {\displaystyle n\,\!} é o total de elementos e r {\displaystyle r\,\!} o número de elementos escolhidos.
Arranjos sem repetição
Arranjo simples de n {\displaystyle n} elementos tomados r {\displaystyle r} a r {\displaystyle r} , onde n ≥ 1 {\displaystyle n\geq 1} e r {\displaystyle r} é um número natural, é qualquer ordenação de r {\displaystyle r} elementos entre os n {\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: A n r = n ! ( n − r ) ! {\displaystyle A_{n}^{r}={\frac {n!}{\left(n-r\right)!}}} Em que n {\displaystyle n\,\!} é o total de elementos, e r {\displaystyle r\,\!} é o número de elementos escolhidos.
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: C r n = ( n r ) = n ! r ! ⋅ ( n − r ) ! {\displaystyle C_{r}^{n}={n \choose r}={\frac {n!}{r!\cdot \left(n-r\right)!}}} Em que n {\displaystyle n\,\!} é o total de elementos e r {\displaystyle r\,\!} 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 é: C R n r = ( n + r − 1 r ) = ( n + r − 1 ) ! r ! ( n − 1 ) ! {\displaystyle CR_{n}^{r}={{n+r-1} \choose {r}}={{(n+r-1)!} \over {r!(n-1)!}}} Em que n {\displaystyle n\,\!} é o total de elementos e r {\displaystyle r\,\!} 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.
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.
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 conhece-se ou não se conhece. 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 demonstração disso é uma curta prova por contradição: suponha que há 3 pessoas que cumprem 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 conhecem (de contrário, teríamos 3 pessoas que não se conheceriam entre si). Com isso, essas pessoas e A se conhecem entre si. (Este é um caso especial do teorema de Ramsey.)
