# Relação de Stifel

Em matemática, a relação de Stifel, também conhecida como regra de Pascal, é 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

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

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

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}}}.$