Convolução de Vandermonde

Proposição:  É válida a seguinte identidade combinatória

\dbinom{n+m}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{m}{r-j}

que é a chamada convolução de Vandermonde.

Pondo n=m, obtém-se

\dbinom{2n}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\binom{n}{r-j}

e para r=n, finalmente,

\dbinom{2n}{n}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{n}{n-j}=\displaystyle\sum_{j=0}^{n}\dbinom{n}{j}^{2}=\sum_{i=0}^{n}\dbinom{n}{i}^{2}.

\bigskip

Demonstração:

Existe uma demonstração meramente combinatória da convolução de Vandermonde:

Dado o conjunto C = \left\{ c_{1,}c_{2},\ldots,c_{n},c_{n+1},c_{n+2},\ldots ,c_{n+m}\right\}, considerem-se dois subconjuntos de C disjuntos, isto é, sem elementos comuns, um C_{1}=\left\{ c_{1,}c_{2},\ldots ,c_{n}\right\} com n elementos e outro com m, C_{2}=\left\{ c_{n+1,}c_{n+2},\ldots ,c_{n+m}\right\}, tais que C=C_{1}\cup C_{2}.

O segundo membro conta o número de maneiras distintas de escolher r elementos de entre os n+m de C.

Quanto ao primeiro membro, comecemos por reparar que

(a) há \dbinom{n}{j} maneiras distintas de escolher j elementos entre os n de C_{1};

(b) há \dbinom{m}{r-j} maneiras distintas de escolher r-j elementos  entre os m de C_{2};

(c) pelo que há \dbinom{n}{j}\dbinom{m}{r-j} maneiras distintas de seleccionar j elementos de C_{1} e simultaneamente r-j de C_{2}.

Ora, se somarmos todas estas parcelas \dbinom{n}{j}\dbinom{m}{r-j} para os possíveis valores que j pode tomar, desde j=0 até j=n, obtemos evidentemente o mesmo número \dbinom{n+m}{r}. Como mostrámos a igualdade dos dois membros da identidade da convolução de Vandermonde, concluímos a justificação. \blacksquare

Os casos particulares referidos obtêm-se imediatamente. A última identidade é também um caso particular de

Quaisquer que sejam os inteiros  k  e n tais que 0\leq k \leq n,  tem-se

\displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n}

que foi demonstrada aqui .

Sobre Américo Tavares

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

3 respostas a Convolução de Vandermonde

  1. Bruno Madeira diz:

    calcule o determinante abaixo pela matriz de vandermonde

    1 1 1
    2 3 4
    4 9 16

  2. Muito interessante esta forma de provar esta identidade. Veja neste link outras formas de prová-la http://fatosmatematicos.blogspot.com/2011/06/algumas-demonstracoes-da-convolucao-de.html

    PS: Estamos todos muito felizes com a filiação do seu blog a UBM. Seja bem-vindo!

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