ANÁLISE COMBINATÓRIA – Parte 3

Número de arranjos com repetição

Seja C um conjunto com m elementos distintos e considere p elementos escolhidos neste conjunto em uma ordem determinada. Cada uma de tais escolhas é denominada um arranjo com repetição de m elementos tomados p a p. Acontece que existem m possibilidades para a colocação de cada elemento, logo, o número total de arranjos com repetição de m elementos escolhidos p a p é dado por mp. Indicamos isto por:

Arep(m,p) = mp

Número de permutações com repetição

Consideremos 3 bolas vermelhas, 2 bolas azuis e 5 bolas amarelas. Coloque estas bolas em uma ordem determinada. Iremos obter o número de permutações com repetição dessas bolas. Tomemos 10 compartimentos numerados onde serão colocadas as bolas. Primeiro coloque as 3 bolas vermelhas em 3 compartimentos, o que dá C(10,3) possibilidades. Agora coloque as 2 bolas azuis nos compartimentos restantes para obter C(10-3,2) possibilidades e finalmente coloque as 5 bolas amarelas. As possibilidades são C(10-3-2,5).

Tal metodologia pode ser generalizada.

Número de combinações com repetição

Considere m elementos distintos e ordenados. Escolha p elementos um após o outro e ordene estes elementos na mesma ordem que os elementos dados. O resultado é chamado uma combinação com repetição de m elementos tomados p a p. Denotamos o número destas combinações por Crep(m,p). Aqui a taxa p poderá ser maior do que o número m de elementos.

Seja o conjunto A=(a,b,c,d,e) e p=6. As coleções (a,a,b,d,d,d), (b,b,b,c,d,e) e (c,c,c,c,c,c) são exemplos de combinações com repetição de 5 elementos escolhidos 6 a 6.

Podemos representar tais combinações por meio de símbolos # e vazios Ø onde cada ponto # é repetido (e colocado junto) tantas vezes quantas vezes aparece uma escolha do mesmo tipo, enquanto o vazio Ø serve para separar os objetos em função das suas diferenças

(a,a,b,d,d,d) equivale a ##Ø#ØØ###Ø

(b,b,b,c,d,e) equivale a Ø###Ø#Ø#Ø#

(c,c,c,c,c,c) equivale a ØØ######ØØ

Cada símbolo possui 10 lugares com exatamente 6# e 4Ø. Para cada combinação existe uma correspondência biunívoca com um símbolo e reciprocamente. Podemos construir um símbolo pondo exatamente 6 pontos em 10 lugares. Após isto, os espaços vazios são prenchidos com barras. Isto pode ser feito de C(10,6) modos. Assim:

Crep(5,6) = C(5+6-1,6)

Generalizando isto, podemos mostrar que:

Crep(m,p) = C(m+p-1,p)

Propriedades das combinações

O segundo número, indicado logo acima por p é conhecido como a taxa que define a quantidade de elementos de cada escolha.

Taxas complementares

C(m,p)=C(m,m-p)

Exemplo: C(12,10) = C(12,2)=66.

Relação do triângulo de Pascal

C(m,p)=C(m-1,p)+C(m-1,p-1)

Exemplo: C(12,10)=C(11,10)+C(11,9)=605

Número Binomial

O número de combinações de m elementos tomados p a p, indicado antes por C(m,p) é chamado Coeficiente Binomial ou número binomial, denotado na literatura científica como

Exemplo: C(8,2)=28.

Extensão: Existe uma importante extensão do conceito de número binomial ao conjunto dos números reais e podemos calcular o número binomial de qualquer número real r que seja diferente de um número inteiro negativo, tomado a uma taxa inteira p, somente que, neste caso, não podemos mais utilizar a notação de combinação C(m,p) pois esta somente tem sentido quando m e p são números inteiros não negativos. Como Pi=3,1415926535…, então:

A função envolvida com este contexto é a função gama. Tais cálculos são úteis em Probabilidade e Estatística.

Teorema Binomial

Se m é um número natural, para simplificar um pouco as notações, escreveremos mp no lugar de C(m,p). Então:

(a+b)m = am+m1am-1b+m2am-2b2+m3am-3b3+…+mmbm

Alguns casos particulares com m=2, 3, 4 e 5, são:

(a+b)2 = a2 + 2ab + b2

(a+b)3 = a3 + 3 a2b + 3 ab2 + b3

(a+b)4 = a4 + 4 a3b + 6 a2b2 + 4 ab3 + b4

(a+b)5 = a5 + 5 a4b + 10 a3b2 + 10 a2b3 + 5 ab4 + b5

A demonstração segue pelo Princípio da Indução Matemática.

Iremos considerar a Proposição P(m) de ordem m, dada por:

P(m): (a+b)m=am+m1am-1b+m2am-2b2+m3am-3b3+…+mmbm

P(1) é verdadeira pois (a+b)1 = a + b

Vamos considerar verdadeira a proposição P(k), com k>1:

P(k): (a+b)k=ak+k1ak-1b+k2ak-2b2+k3ak-3b3+…+kkbk

para provar a propriedade P(k+1).

Para que a proposição P(k+1) seja verdadeira, deveremos chegar à conclusão que:

(a+b)k+1=ak+1+(k+1)1akb+(k+1)2ak-1b2+…+(k+1)(k+1)bk+1

Pelas propriedades das combinações, temos:

k1+k0=C(k,1)+C(k,0)=C(k+1,1)=(k+1)1

k2+k1=C(k,2)+C(k,1)=C(k+1,2)=(k+1)2

k3+k2=C(k,3)+C(k,2)=C(k+1,3)=(k+1)3

k4+k3=C(k,4)+C(k,3)=C(k+1,4)=(k+1)4

… … … …

kk-1+kk-2=C(k,k-1)+C(k,k-2)=C(k+1,k-1)=(k+1)k-1

kk+kk-1=C(k,k)+C(k,k-1)=C(k+1,k)=(k+1)k

E assim podemos escrever:

que é o resultado desejado.

Colaboração: Matemática Essencial