A identidade de Vandermonde (ou convolução de Vandermonde) afirma que, para inteiros não negativos
,
a) Dê uma interpretação combinatória para a identidade e prove-a utilizando essa interpretação.
b) Prove a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de
em
.
c) Use a identidade para calcular
.
d) Explique brevemente como essa identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.
b) Prove a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de
c) Use a identidade para calcular
d) Explique brevemente como essa identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.
Passo 1
O enunciado dá a identidade de Vandermonde para inteiros não negativos
:
As perguntas são:
a) Dar uma interpretação combinatória e provar a identidade usando essa interpretação.
b) Provar a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de em
.
c) Calcular .
d) Explicar brevemente como a identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.
As informações relevantes fornecidas são a fórmula acima e que são inteiros não negativos; a soma no lado esquerdo é em
de
até
(valores fora do intervalo naturalmente produzem binomiais nulos).
a) Dar uma interpretação combinatória e provar a identidade usando essa interpretação.
b) Provar a identidade algébrica mostrando que ambos os lados são iguais ao coeficiente de
c) Calcular
d) Explicar brevemente como a identidade corresponde à convolução de sequências e onde isso aparece em problemas de contagem.
As informações relevantes fornecidas são a fórmula acima e que
Passo 2
Antes de provar, vale revisar o que significa
e por que aparece em contagem.
A definição concreta: é o número de maneiras de escolher
elementos de um conjunto com
elementos, sem ordem. Em notação:
A definição concreta:
quando
; se
ou
então
. Aqui
é o fatorial de
.
Exemplo rápido para fixar: conta os pares distintos escolhidos de um conjunto de 5 elementos.
Exemplo rápido para fixar:
Passo 3
Interpretação combinatória para a identidade (ideia central). Pense em um conjunto total com
elementos dividido em duas partes disjuntas: um bloco
com
elementos e um bloco
com
elementos. Queremos contar de duas maneiras o número de subconjuntos de tamanho
desse conjunto total. Essa contagem é o que a identidade relaciona.
Passo 4
Prova combinatória passo a passo.
- Contagem direta (lado direito): O número de maneiras de escolher um subconjunto de tamanho
dentre os elementos é exatamente
- Contagem por casos (lado esquerdo): Para cada subconjunto de tamanho
podemos olhar quantos elementos dele vêm do bloco . Seja o número de elementos escolhidos de . Então pode variar de até , mas também tem de obedecer e ; valores fora desses limites dão binomiais nulos automaticamente. Para um dado :
- Escolher
elementos de pode ser feito de maneiras. - Escolher os restantes
elementos de pode ser feito de maneiras.
Como as escolhas nos dois blocos são independentes, para aqueletotalizamos subconjuntos. Somando sobre todos os possíveis obtemos o número total de subconjuntos de tamanho :
- Concluímos que ambas as contagens contam exatamente o mesmo conjunto (subconjuntos de tamanho
do conjunto total), logo são iguais:
Essa é a prova combinatória. É simples, intuitiva e muito utilizada: partimos a escolha em “quantos tiro do primeiro grupo” e somamos sobre as possibilidades.
Passo 5
Agora a prova algébrica via coeficiente em polinômios. Primeiro revisamos o Teorema Binomial (lição rápida): para inteiro não negativo
,
Aqui o coeficiente de
em
é
. Isso decorre da definição do binômio e da expansão combinatória.
Passo 6
Multiplicação das séries e coeficiente (parte crucial). Considere
Expandindo cada fator com o teorema binomial:
O produto é, por produto de séries (ou produto de polinômios), dado por a soma cauchy:
Explicando o passo: ao multiplicar as séries, para obter o termo em
somamos todos os produtos de termos
do primeiro por
do segundo; os coeficientes multiplicam, daí a soma interior.
Mas também sabemos diretamente pelo teorema binomial que o coeficiente de em
é
. Como a escrita em série é única, igualamos coeficientes:
Mas também sabemos diretamente pelo teorema binomial que o coeficiente de
Isso dá a prova algébrica pedida: ambos os lados são o coeficiente de
em
.
Passo 7
Exemplo numérico (parte c). Vamos calcular
Pela identidade de Vandermonde, com
,
e
, o valor é simplesmente
. Mas vamos também expandir explicitamente para treinar:
Termos não nulos ocorrem quando e
, isto é
também funciona; computamos cada termo:
Termos não nulos ocorrem quando
Somando:
Também
, confirma.
Passo 8
Explicação sobre convolução e onde aparece (parte d).
Definimos duas sequências (iniciando em índice )
e
, com a convenção de que termos com índice fora do intervalo apropriado são zero. A convolução discreta dessas sequências é a sequência
dada por
Definimos duas sequências (iniciando em índice
A identidade de Vandermonde diz que
. Ou seja, a convolução de duas sequências de coeficientes binomiais dá os coeficientes binomiais do somatório dos expoentes. Isso aparece naturalmente quando multiplicamos polinômios (ou geradores formais): o coeficiente do produto é a convolução dos coeficientes, exatamente o que usamos na prova algébrica. Em problemas de contagem, essa propriedade surge sempre que repartimos uma escolha em duas partes independentes (como no argumento combinatório): o número total de modos de obter um resultado composto é a soma (convolução) de combinações de escolhas parciais. Aparece também em probabilidades (soma de variáveis binomiais independentes), em teoria de geradores funcionais e em combinatória enumerativa em geral.
Passo 9
Recapitulando de forma motivadora: a identidade é uma ferramenta poderosa porque une uma explicação clara (contar por casos) com uma identidade algébrica elegante (coeficientes em produto de polinômios). Se estiver nervoso para a prova, lembre: normalmente é suficiente lembrar “conte direto” vs “conte por casos (quantos peguei do primeiro grupo)” ou "coeficiente de
em
" — qualquer uma das duas vias resolve a prova rápida e seguramente.
Resposta
a) Contagem por casos: contar subconjuntos de tamanho
de um conjunto com
elementos dividido em dois blocos de tamanhos
e
. Para cada
escolhemos
de
e
de
, somando obtemos
.
b) Pelo Teorema Binomial, . Expandindo e igualando o coeficiente de
obtemos
.
c) .
d) A identidade é a convolução discreta dos coeficientes e
:
. Aparece ao multiplicar polinômios (coeficientes do produto), em problemas que dividem uma escolha em duas partes, e em somas de variáveis binomiais independentes.
b) Pelo Teorema Binomial,
c)
d) A identidade é a convolução discreta dos coeficientes