Relação de Stifel

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

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

Ilustra a prova combinatória:

{\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.

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