Relação de Stifel

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática, a relação de Stifel[1] , também conhecida como regra de Pascal[2] , é uma identidade envolvendo coeficientes binomiais:

Para quaisquer naturais n, k tais que 1 \leq k \leq n
\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}.

Demonstração algébrica[editar | editar código-fonte]

Não há segredos na relação de Stifel. É possível demonstrá-la recorrendo-se apenas a definição dos símbolos \binom{n}{k}, que denotam os coeficientes binomiais, e efetuando umas poucas manipulações algébricas:

\binom{n-1}{k - 1} + \binom{n - 1}{k} = \frac{(n - 1)!}{(n - k)!(k - 1)!} + \frac{(n - 1)!}{(n - k - 1)!k!}
= \frac{(n - 1)!k}{(n - k)!(k - 1)!k} + \frac{(n - k)(n - 1)!}{(n - k)(n - k - 1)!k!} = \frac{(k + (n - k))(n - 1)!}{(n-k)!k!}
= \frac{n(n-1)!}{(n - k)!k!} = \frac{n!}{(n - k)!k!} = \binom{n}{k}.

Contudo, mesmo sendo esta demonstração algébrica elementar, há uma outra demonstração que, do ponto de vista da elegância, é certamente mais atraente:

Demonstração combinatória[editar | editar código-fonte]

Alternativamente a demonstração algébrica oferecida, a relação de Stifel possui uma conhecida demonstração combinatória:

Seja X um conjunto finito não-vazio com n elementos. O número de subconjuntos de X que possuem 1 \leq k \leq n elementos é justamente \binom{n}{k}, isto é,

\#\{Y : (Y \subseteq X) \land (\#Y = k)\} = \binom{n}{k}.

Por outro lado, destacando um elemento x^\ast \in X, podemos determinar o cardinal \#\{Y : (Y \subseteq X) \land (\#Y = k)\} de uma maneira alternativa, procedendo como segue:

  • Contamos o número de subconjuntos de X com k elementos que possuem x^\ast, isto é, determinamos
\#\{Y \cup \{x^\ast\} : (Y \subseteq X \setminus \{x^\ast\}) \land (\#Y = k - 1)\} =: m_1;
  • Contamos o número de subconjuntos de X com k elementos que não possuem x^\ast, isto é, determinamos
\#\{Y : (Y \subseteq X \setminus \{x^\ast\}) \land (\#Y = k)\} =: m_2;
  • Somamos os dois números. Seguirá então, pelo argumento de dupla contagem, que
m_1 + m_2 = \#\{Y : (Y \subseteq X) \land (\#Y = k)\} = \binom{n}{k}.

Agora, como \#(X \setminus \{x^\ast\}) = \#X - \#\{x^\ast\} = n - 1, segue que

m_1 = \binom{n - 1}{k - 1}

e

m_2 = \binom{n - 1}{k},

donde ganha-se a relação.

Generalização para coeficientes multinomiais[editar | editar código-fonte]

A relação de Stiefel, que é uma afirmação sobre coeficientes binomiais, pode ser estendida para coeficientes multinomiais:

Para quaisquer naturais n, m, k_1, k_2, \ldots, k_m tais que m \geq 2, 1 \leq k_i \leq n para cada i \in \{1, 2, \ldots, m\} e k_1 + k_2 + \cdots + k_m = n
\binom{n - 1}{k_1 - 1, k_2, \ldots, k_m} + \binom{n - 1}{k_1, k_2 - 1, \ldots, k_m} + \cdots + \binom{n - 1}{k_1, k_2, \ldots, k_m - 1} = \binom{n}{k_1, k_2, \ldots, k_m}.

No caso em que m = 2, fazendo a identificação k_1 := k temos que k_1 + k_2 = n implica k_2 = n - k. Assim, usando as identificações

\binom{n - 1}{k_1 - 1, k_2} = \binom{n - 1}{k - 1, n - k} := \binom{n - 1}{k - 1}

e

\binom{n - 1}{k_1, k_2 - 1} = \binom{n - 1}{k, n - k - 1} := \binom{n - 1}{k},

recupera-se imediatamente a relação de Stifel para coeficientes binomiais.

Demonstração: Sejam m \geq 2 um natural e n, k_1, k_2, \ldots, k_m naturais tais que 1 \leq k_i \leq n, para cada índice 1 \leq i \leq m, e k_1 + k_2 + \cdots + k_m = n. Então

\binom{n - 1}{k_1 -1, k_2, \ldots, k_m} + \binom{n - 1}{k_1, k_2 - 1, \ldots, k_m} + \cdots + \binom{n - 1}{k_1, k_2, \ldots, k_m - 1}
= \frac{(n - 1)!}{(k_1 - 1)!k_2! \cdots k_m!} + \frac{(n - 1)!}{k_1!(k_2 - 1)! \cdots k_m!} + \cdots + \frac{(n - 1)!}{k_1!k_2! \cdots (k_m - 1)!}
= \frac{k_1(n - 1)!}{k_1!k_2! \cdots k_m!} + \frac{k_2(n - 1)!}{k_1!k_2! \cdots k_m!} + \cdots + \frac{k_m(n - 1)!}{k_1!k_2! \cdots k_m!} = \frac{(k_1 + k_2 + \cdots + k_m)(n - 1)!}{k_1!k_2! \cdots k_m!}
= \frac{n(n - 1)!}{k_1!k_2! \cdots k_m!} = \frac{n!}{k_1!k_2! \cdots k_m!} = \binom{n}{k_1, k_2, \ldots, k_m}.

Ver também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. em referência a Michael Stifel (1487 — 1567), matemático alemão
  2. em referência a Blaise Pascal (1623 — 1662), matemático francês

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]