Identidade de Pascal

Apresente um argumento combinatório justificativo da identidade de Pascal.

\displaystyle\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}.

Resolução

Pensemos em dois conjuntos, um A=\left\{ a_{1},a_{2},\ldots ,a_{n}\right\} com n elementos e outro, B arbitrário mas contido em A e com n-1 elementos: B=\left\{ b_{1},b_{2},\ldots ,b_{n-1}\right\} \subset A. Escolhamos agora k elementos de entre os n de A. A contagem do número de maneiras distintas de escolher esses k elementos pode fazer-se de duas formas:

– uma, directa, expressa por \dbinom{n}{k};

– outra, indirecta, baseada no seguinte raciocínio: os k elementos escolhidos ou pertencem todos ao conjunto B (caso 1) ou todos menos um, ou seja, k-1 pertencem a B e o que não faz parte de B pertence a A (caso 2).

Existem \dbinom{n-1}{k} escolhas distintas no caso 1 e \dbinom{n-1}{k-1} no 2. Somando \dbinom{n-1}{k} com \dbinom{n-1}{k-1} obtém-se o número total de escolhas associadas aos  dois casos.

Mostrámos assim que os dois lados da identidade de Pascal são iguais. \qquad\blacktriangleleft

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Combinatória, Exercícios Matemáticos, Identidade matemática, Matemática, Problemas com as etiquetas , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s