Identidades combinatórias

A análise combinatória pode ser uma bastante divertida quando tentamos entender as identidades combinatórias através de situações problemas. A análise combinatória deixa de ser um jogo complicado de fórmulas complexas e passa ser um jogo de contagem interessante. Logo, a frase de Tales de Mileto passa a fazer todo o sentido:

“A questão primordial, não é o que sabemos, mas como sabemos”

Frase retirada do trabalho Demonstração de Identidades Combinatórias com Teoria de Contagem

Identidade 1

$\binom{n}{k}$ = $\binom{n}{n-k}$

Problema:

De quantas maneiras podemos formar uma comissão com k alunos para representar a turma com n alunos?

O lado esquerdo conta de quantas maneiras podemos formar uma comissão com k alunos em uma turma com n alunos.  Cada comissão com k alunos exclui n-k alunos. O lado direito conta de quantas maneiras diferentes podemos exclui n-k alunos para formar uma comissão com k alunos.

Identidade 2

$\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$

Problema: 

Novamente, o lado esquerdo representa o número de comissões com k alunos em uma turma com n alunos. Escolha um aluno qualquer da turma, este aluno pode pertencer ou não a comissão.
Caso 1: Se o aluno escolhido pertence a comissão então precisamos escolher k-1 alunos entre n-1 alunos restantes.
Caso 2: Se o aluno escolhido não pertence a comissão então precisamos escolher k alunos entre n-1 alunos restantes.

Identidade 3

$\sum_{i=0}^{n} \binom{n}{i}$ = $2^{n}$

Problema:

Precisamos formar uma comissão de alunos de qualquer tamanho em uma turma com n alunos?

O lado direito conta o número de subconjuntos possíveis em uma turma com n alunos. Cada subconjunto representa uma possível comissão formada. O lado esquerdo conta a mesma quantidade mas de uma maneira mais difícil. O lado esquerdo soma a quantidade de maneiras de formar uma comissão considerando todos os tamanhos possíveis.


Identidade 4

$k\binom{n}{k}$ = $n\binom{n-1}{k-1}$

Problema:

Queremos formar uma comissão com k alunos em uma turma com n alunos sendo que um deles é o presidente.

No lado direito, temos o seguinte raciocínio: temos n possibilidade para a escolha do presidente multiplicada pela quantidade de maneiras de escolher k-1 alunos entre n-1 alunos restantes. No lado esquerdo, contamos de quantas maneiras podemos formar uma comissão de k alunos entre n alunos multiplicada pela quantidade de maneiras que podemos escolher o presidente na comissão com k alunos.

Identidade 5

$\sum_{i=0}^{n} i\binom{n}{i}$ = $n2^{n-1}$

Problema:

Precisamos formar um time de futebol de qualquer tamanho com n jogadores sendo que um deles é o capitão.

Solução:

No lado direito, n representa de quantas maneiras podemos escolher o capitão entre n jogadores multiplicado pela quantidade de maneiras que podemos formar um time (subconjunto) entre n-1 jogadores (elementos). No lado esquerdo, realizamos o mesmo cálculo. Primeiramente, formamos um time com i jogadores multiplicamos pela quantidade maneiras que podemos escolher o capitão no time formado.


Exercício

Prove as seguintes identidades:

Identidade

$k(k-1)\binom{n}{k}$ = $n(n-1)\binom{n-2}{k-2}$

Pense em uma comissão com k membros de n possíveis sendo que cada comissão tem um presidente e um vice-presidente.

Identidade

$2\binom{2n-1}{n}$ = $\binom{2n}{n}$


Identidade

$\sum_{i=0}^{n} \binom{x}{i} \binom{y}{n-i}$ = $\binom{x+y}{n}$

Considere uma turma com x homens e y mulheres, precisamos formar uma comissão com n alunos.


Referências

Monografia Demonstração de Identidades Combinatórias com Teoria de Contagem

Bijections

More bijections

Combinatória Básica

Técnicas Básicas de Contagem

Regra do Produto Se um conjunto A tem |A| possibilidades e B tem |B| possibilidade então existe |A|*|B| formas de combiná-los. Por exemplo, se tenho 4 camisas e 3 calças logo tenho 12 maneiras de distintas de vestir-se. Considere o seguinte exemplo:

Seja a decomposição de um número n em fatores primos p₁, …, p_k

Cada divisor do número n pode ser escrito como  , onde   dessa maneira temos possibilidades para cada fator da multiplicação.Logo, o número de divisores de N dado por d(n) será dado pela seguinte fórmulas



Algoritmo

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 100

int p[MAX];
int e[MAX];

int cont;

void fatora(int n){
  int i;
  int num_divisores;
  i=2;
  cont = 0;
  while(n!=1){
    if(n%i==0){
      p[cont] = i;
      while(n%i==0){
        e[cont]++;
        n=n/i;
      }
      cont++;
    }
    i++;
  }
  num_divisores = e[0]+1;
  printf("n = %d^%d",p[0],e[0]);

  for(i=1;i<cont;i++){
    printf("+%d^%d",p[i],e[i]);
    num_divisores *= e[i]+1;
  }
  printf("\n");  
  printf("num divisores %d\n",num_divisores);
}
int main(){
  fatora(60);
  
} 

SAÍDA 

n = 2^2+3^1+5^1
num divisores 12

Lembrando que diminuindo qualquer um dos expoentes da 

decomposição de n em fatores primos gera um divisor de n. 

Por exemplo,

d = 2^1+3^1+5^0 = 6 é divisor 60 

d = 2^2+3^0+5^0 = 4 é divisor 60

Regra da Soma Se um conjunto tem |A| possibilidades e B tem |B| possibilidade então existe |A|+|B| maneiras de A ou B podem ocorrer.

Exemplo: Com quantos zeros termina N!?

Para o número N! ganhar um zero no final, ele precisa ter um fator 10 = 2*5. Para saber o número de zeros no final de N!, precisamos saber o mínimo entre o número de fatores 2 e 5. O número de fatores 5 é menor que o número de fatores 2. Logo, precisamos apenas saber o número de fatores 5.

Seja o número de múltiplos de k menores que n dado por M(k,n). 

Logo, o número de zeros no final de N! será dado por

zero(n!) = M(5,n) + M(5²,n) + M(5³,n)+…+M(5^k,n), onde 5^k < n

M(5,n) conta o número de múltiplos de 5 menores que n. Só que número 25 tem dois fatores 5. Logo, precisamos contar também o número de múltiplos de 25 menores que n para contabilizar o segundo fator 5 do número 25. E assim, procedemos com todas as potências de 5 possíveis.

 

Podemos desenvolver esta idéia de outra forma, vamos colocar todos os termos com fator 5 em evidência:

n! = 1.2.3.4.(5.1).6...9.(5.2).11...14.(5.3).16.....(5.m)..(n-1).(n)

Logo, podemos escrever n! da seguinte maneira:

n! = 5(1*2*3*…*m)*L₁, onde L₁ não contém múltiplos de 5 e m é o número de múltiplos de 5 menores que n.  O número de zeros no final de n! é igual a:

zero(n!) = m + zero(m!), onde m número de múltiplos de 5 menores que n

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int zeros(int n){
  int d=5;
  int num_zeros=0;
  while(d<=n){
    num_zeros += n/d;
    d *=5;
  }
  return num_zeros;
}

int zeros2(int n){
  if(n<5) return 0;
  else return n/5 + zeros2(n/5);
}

int main(){
  printf("25!=15511210043330985984000000\n");
  printf("numero de zeros: %d\n",zeros(25));
  printf("numero de zeros: %d\n",zeros2(25));
  
} 

OUTPUT 

25!=15511210043330985984000000
numero de zeros: 6
numero de zeros: 6