Coeficiente binomial
Considere que Cn,k é o número de maneiras de escolher k objetos de uma coleção de n objetos, onde n e k são números inteiros positivos. Por exemplo, numa turma de 9 alunos: João, Pedro, Lucas, Maria, … e Rafaela, de quantas maneiras diferentes posso montar um grupo de 3 alunos? Uma maneira é João, Pedro e Lucas; outra, Maria, Pedro e João. O número total de maneiras é dado por
C9,3
Ainda não sabemos que número é C9,3. O símbolo C9,3 apenas indica este número. Mas, temos alguns casos cuja resposta é simples, por exemplo, o que seria C9,9? De quantas maneiras posso escolher 9 objetos de um grupo de 9? Para este a resposta é fácil, C9,9=1! E, o que seria C9,0? Faz sentido? Posso dizer que sim, e que de 9 objetos eu tenho uma única maneira de não escolher nada, então Cn,0=1,para qualquer n. E C9,10 faz sentido? Posso dizer que sim, e que de 9 objetos não tem como eu montar um grupo de 10, logo C9,10=0, ou seja Cn,k=0 para todo k>n. Resumindo,
Cn,0=1
Cn,n=1
Cn,k=0, para todo k>n
Agora, imagine que quero montar escolher numa turma de 9 alunos até 3 alunos para me ajudar. De quantas maneiras posso fazer isto?Se admitirmos que eu posso não escolher ninguém, então o número total de maneiras é dado por
C9,0 + C9,1 + C9,2 + C9,3
Agora, imagine que quero montar escolher numa turma de 9 alunos até 9 alunos para me ajudar, teremos
C9,0 + C9,1 + C9,2 + … + C9,9 = 9k=0 C9,k
A expressão acima me dá o número de possibilidades de escolher numa turma de 9 alunos até 9 alunos para me ajudar. Mas no lugar de escolher os alunos, vou perguntar a cada um se quer ou não me ajudar? Como cada aluno de duas opções, sim ou não; e são no total 9 alunos, o número de possibilidades de escolher numa turma de 9 alunos até 9 alunos é 29. Portanto,
9k=0 C9,k = 29 ou de maneira geral nk=0 Cn,k = 2n
Outro resultado interessante é que escolher k objetos num grupo de n é a mesma coisa que não escolher n-k objetos em um grupo de n, então
Cn,k = Cn,n-k
Vamos agora imaginar que eu queria escolher k pessoas em um grupo de n pessoas, em seguida indicar 1 dos k escolhidos como capitão. O número de maneiras de fazer isto é
kCn,k
Mas, podemos seguir um caminho diferente, comece escolhendo o capitão do grupo de n pessoas, depois dos que sobraram escolha k-1 pessoas para junto com o capitão fechar o time de k pessoas. Pensando assim, o número de maneiras de fazer isto é
nCn-1,k-1
mas, os dois caminhos de levam ao mesmo resultado final, então,
kCn,k=nCn-1,k-1 (*)
O fato curioso é que existe um outro caminho de escolher. Primeiro vamos escolher k-1 pessoas do grupo de n e depois escolho o capitão das pessoas restantes, n-(k-1). Assim, o número de maneiras de fazer isto é
(n-k+1)Cn,k-1
mas, este caminho leva ao mesmo resultado que antes, então,
kCn,k=nCn-1,k-1=(n-k+1)Cn,k-1
Vamos a outra relação importante. Considere que queremos escolher k pessoas de um grupo de n pessoas. Mas, suponha que eu pergunte ao João que é umas das n pessoas: você quer ser escolhido? O joão tem duas respostas possíveis: sim ou não. Se ele diz não, eu tenho que escolher k pessoas de um grupo de n-1 pessoas; se ele diz sim, eu tenho que escolher k-1 pessoas de um grupo de n-1 pessoas. Neste caso, juntando as duas alternativas, temos
Cn,k = Cn-1,k-1 + Cn-1,k
Agora, para finalizar, considere a expressão (*) na formando
Cn,k=(n/k)Cn-1,k-1
neste caso,
Cn-1,k-1=(n-1/(k-1))Cn-2,k-2
portanto,
Cn,k=(n/k)(n-1/(k-1))Cn-2,k-2
e, assim, sucessivamente teremos
Cn,k=(n/k)(n-1/(k-1))(n-2/(k-2))…((n-(k-1))/(k-(k-1)))Cn-k,0
Cn,k=(n/k)(n-1/(k-1))((n-2)/(k-2))…((n-k+1)/1)Cn-k,0
como Cn,0=1 e n!=n(n-1)…1, teremos
Cn,k=(n!/k!(n-k)!)
a conhecida fórmula de combinação!
