ANÁLISE COMBINATÓRIA


  Análise combinatória é um ramo da matemática que estuda como calcular o total de diferentes combinações possíveis entre elementos finitos da natureza.
  Por meio desta ciência, podemos calcular, por exemplo, quantos carros a mais podem ser emplacados aumentando-se uma letra da placa, saber qual é a chance de se ganhar um prêmio na loteria, etc.
  São as principais divisões em Análise Combinatória:

  Permutação

  Permutação busca analisar de quantas maneiras podemos organizar um grupo de n elementos, usando todos os elementos.

  Por exemplo, imaginemos três poltronas vazias no cinema. De quantas maneiras três pessoas podem se sentar?
  Seja o conjunto pessoas = {A, B, C}.
  Combinações possíveis:
  1. A,B,C
  2. A,C,B
  3. B,A,C
  4. B,C,A
  5. C,A,B
  6. C,B,A
  São 6 cominações possíveis.

  Observamos no exemplo anterior que:   Assim, a permutação é calculada simplesmente pelo número fatorial do total de elementos. No caso anterior, seria 3! = 6.

  A fórmula para permutação é:
P(n) = n!
  ou
P(n) = n x (n-1) x (n-2) x ... x 1


  Arranjo

  O arranjo são as combinações possíveis de um sub-grupo de dado grupo, onde a ordem dos elementos é levada em conta.

  Exemplo: seja uma corrida com 5 competidores. De quantas maneiras podemos ter os 3 primeiros colocados?
  Temos 5 possibilidades para o primeiro colocado, 4 possibilidades para o segundo e 3 possibilidades para o terceiro.
  Assim, a resposta é 5x4x3 = 60.

  Ilustração:
  1   2   3  - Colocação
 --- --- ---
  5   4   3  - Corredores possíveis

  A fórmula do arranjo é:
A(n,p) = n! / (n-p)!

  Onde n é o total de elementos do conjunto e p o total de elementos do sub-conjunto. Podemos simplificar:
 A(n,p) = n x (n-1) x (n-2)
          |               |
          +---------------+
                  |
          Com "p" operadores
  Exemplos:

  Arranjo(6,2) = 6x5 = 30
  Arranjo(8,4) = 8x7x6x5 = 1680

  A utilização desta simplificação é importante, pois conforme cresce o valor de n, o valor de seu fatorial é enorme. Por exemplo, 10! = 3628800.


  Combinação

  A combinação é quase a mesma coisa que o arranjo. A diferença é que na combinação, a ordem dos elementos do sub-grupo não é importante. Basta que ocorra exatamente uma vez!

  Por exemplo, em um grupo de 10 pessoas, se desejarmos saber quantos abraços entre 2 pessoas haverão no total, o abraço de João com Márcia é o mesmo que o abraço de Márcia com João. Os dois serão computados como um só.

  A fórmula para a combinação é:
C(n,p) = n! / (p! x (n-p)!)

  Simplificando, temos:
C(n,p) = A(n,p) / p!




  Códigos em C

  A seguir, um programa em C que faz o cálculo da quantidade de permutações, arranjos e combinações.
#include <stdio.h>

int fatorial(int n)
{
   if (n>0)
      return n*fatorial(n-1);
   else
      return 1;
}

int permutacao(int n)
{
  return fatorial(n);
}

int arranjo(int n, int p)
{
  if (p>1)
      return n*arranjo(n-1,p-1);
   else
      return n;
}

int combinacao(int n, int p)
{
   return arranjo(n,p)/fatorial(p);
}

main()
{
   printf("Permutação de 6 é %d\n",permutacao(6));
   printf("Arranjo de 6,2 é %d\n",arranjo(6,2));
   printf("Combinação de 6,2 é %d\n",combinacao(6,2));
   return 0;
}
  Saída:
  Permutação de 6 é 720
  Arranjo de 6,2 é 30
  Combinação de 6,2 é 15


  O programa a seguir lista todas as permutações de um dado conjunto[1].
#include <stdio.h>
#include <string.h>

typedef char * string;

void troca_char(string str, int p1, int p2)
{
  char tmp;
  tmp = str[p1]; 
  str[p1] = str[p2]; 
  str[p2] = tmp;
}

void permutacao_recursiva(string str, int k)
{
  int i, len;
  len = strlen(str);

  if (k == len) 
    printf( "%s\n", str);
  else 
  {
    for (i = k; i < len; i++) 
    {
      troca_char(str, k, i);
      permutacao_recursiva(str, k + 1);
      troca_char(str, i, k);
    }
  }
}

void lista_permutacoes(string str)
{
  permutacao_recursiva(str, 0);
}

void main(void)
{
  char lista[] = "ABC";
  lista_permutacoes(lista);
}
  [1]- https://www.ime.usp.br/~pf/mac0122-2003/aulas/permut.html

  Saída:
  ABC
  ACB
  BAC
  BCA
  CBA
  CAB


  O programa a seguir lista todas as combinações possíveis de um dado conjunto[2].
#include <stdio.h>

void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
{
  int i, j;

  if (index == r)
  {
    for (j=0; j<r; j++)
      printf("%d ", data[j]);
    printf("\n");
    return;
  }
 
  for (i=start; i<=end && end-i+1 >= r-index; i++)
  {
    data[index] = arr[i];
    combinationUtil(arr, data, i+1, end, index+1, r);
  }
}

void printCombination(int arr[], int n, int r)
{
  int data[r];
 
  combinationUtil(arr, data, 0, n-1, 0, r);
}
 
int main()
{
  int arr[] = {1, 2, 3, 4, 5};
  int r = 3;
  int n = sizeof(arr)/sizeof(arr[0]);
  printCombination(arr, n, r);
}
  [2]- http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

  Saída:
  1 2 3
  1 2 4
  1 2 5
  1 3 4
  1 3 5
  1 4 5
  2 3 4
  2 3 5
  2 4 5
  3 4 5



  Exercícios

1) Quantas automóveis  a mais podem ser emplacados, mudando-se o número de letras de 2 para 3?
Como há repetições de letra, não podemos resolver por arranjo. Usaremos os conceitos vistos para resolver:
Placa com 2 letras e 4 números: 26 x 26 x 10 x 10 x 10 x 10 = 6.760.000
Placa com 3 letras e 4 números: 26 x 26 x 26 x 10 x 10 x 10 x 10 = 175.760.000
Total = 175760000 - 6760000 = 169.000.000 veículos

2) Quantos abraços entre duas pessoas podemos ter em uma confraternização de ano novo, em um lugar com 10 pessoas?
printf("Total de abraços = %d\n", combinacao(10,2));
3) Quantos times podemos ter classificados para a Taça Libertadores da América, se o campeonato tem 24 clubes e 4 vagas?
printf("Libertadores = %d\n", combinacao(20,4));
4) Quantas maneiras distintas podemos ter um pódio de uma competição de nado de costas em uma olimpíada, sendo 32 competidores?
printf("Pódio = %d\n", arranjo(32,3));
5) Quantas maneiras podemos escrever a palavra ARARA?
Como há repetições, não podemos resolver por permutação simples. Fazemos a repetição normal e depois dividimos pelas repetições: 5!/(3!*2!) = 120/(6*4) = 5.
6) Uma prova de Matemática consta de 10 questões do tipo V ou F. De quantas maneiras distintas ela pode ser resolvida?
Repetição, pois podemos usar V ou F quantas vezes quiser. Logo = 2x2x2x2x2x2x2x2x2x2 = 1024.
7) Qual a chance de um apostador ganhar a Mega-Sena, apostando 6 números, sendo 6 sorteados e 60 no total?
printf("Chances = 1 entre %d\n", combinacao(60,6)); 1 entre 50.063.860 possibilidades!!!!!!!!
8) Qual a chance de um apostador ganhar a Mega-Sena, se a aposta fosse com 15 números, 15 sorteados e 60 no total?
printf("Chances = 1 entre %d\n", combinacao(60,15)); 1 entre 53.194.089.192.720 possibilidades .......
9) Qual a chance de um apostador ganhar a Mega-Sena, apostando 15 números, sendo 6 sorteados e 60 no total?
printf("Chances = 1 entre %d\n", combinacao(60,6)/combinacao(15,6)); 1 entre 10.003 possibilidades!! Note que a caixa cobra R$ 1,50 pela aposta por 6 números e R$ 7.507,50 pelos 15, ou seja, 5005 vezes mais caro. 5005 é o valor de combinacao(15,6).
10) Uma turma tem 15 alunos, sendo 9 meninos e 6 meninas. Em um grupo de 4, quantos tem pelo menos 1 menino?
printf("Meninos = %d\n", combinacao(15,4)-combinacao(6,4));
11) Quantos jogos haverão em um torneio com 12 participantes, onde cada time joga com outro em turno e returno?
printf("Jogos = %d\n", combinacao(12,2)*2);

MARMSX/CURSOS/C--