Republicação da demonstração combinatória (ou combinatorial) da convolução de Vandermonde e de outra soma binomial

Publicado em 25 de Junho de 2011 por Américo Tavares

(Inicialmente publicada nesta entrada.)

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

Proposição: 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 e que repito.

Demonstração:

Comecemos por reparar que poderíamos ter escolhido para limite inferior do somatório 0 , em vez de k, porque para i<k, \binom{i}{k}=0, por convenção usual.

O segundo membro (lado direito) conta o número de maneiras diferentes de escolher k elementos dum conjunto, tal como S=\left\{ s_{1},s_{2},\cdots,s_{n}\right\} com n elementos e, ao mesmo tempo, n elementos doutro conjunto, por exemplo X=\left\{ x_{1},x_{2},\ldots,x_{n},x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos.

Quanto ao primeiro membro, considerem-se dois subconjuntos de X disjuntos (sem elementos comuns), um X_{1}=\left\{x_{1},x_{2},\ldots,x_{n}\right\} com n elementos, e outro X_{2}=\left\{x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos, tais que X_{1}\cup X_{2}=X.

Escolhamos agora n elementos de X pertencendo i deles a X_{1} e n-i a X_{2}, com 0\leq i\leq n.

(a) Há \dbinom{n}{i} maneiras diferentes de escolher i elementos entre os n de X_{1};

(b) há \dbinom{n-k}{n-i}=\dbinom{n-k}{i-k} maneiras diferentes de escolher n-i elementos entre os n-k de X_{2};

(c) daqui decorre que, para um dado i, há \dbinom{n}{i}\dbinom{n-k}{i-k} maneiras distintas de seleccionar esses n elementos de X. Assim, cada parcela, \dbinom{n}{i}\dbinom{n-k}{i-k}\dbinom{n}{k} conta o número de maneiras diferentes de escolher n elementos de X (dos quais i\in X_{1} ) e, simultaneamente, k de S. Somando, para todos os possíveis valores de i , estas parcelas, obtemos o número total

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

A primeira igualdade é justificada por

\dbinom{n}{k}\dbinom{n-k}{i-k}=\dbinom{n}{i}\dbinom{i}{k}

e a segunda pela observação inicial.

É claro que as duas contagens, a directa representada pelo produto do segundo membro e a indirecta, pela soma do primeiro (lado esquerdo) hão-de ser iguais, o que mostra

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

como pretendíamos. \blacksquare

Nota: o leitor poderá ver várias demonstrações algébricas e analíticas no blogue Fatos Matemáticos do Prof. Paulo Sérgio, na entrada   Algumas Demonstrações da Convolução de Vandermonde-Euler.

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, Matemática Discreta, Teorema, Teorema / Teoria com as etiquetas , , . ligação permanente.

Deixe uma Resposta

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

Gravatar
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 )

Cancelar

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.