Em matemática , a relação de Stifel [ 1] regra de Pascal [ 2] identidade envolvendo coeficientes binomiais :
Para quaisquer naturais
n
,
k
{\displaystyle n,k}
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
=
(
n
k
)
.
{\displaystyle {\binom {n-1}{k-1}}+{\binom {n-1}{k}}={\binom {n}{k}}.}
Não há segredos na relação de Stifel. É possível demonstrá-la recorrendo-se apenas a definição dos símbolos
(
n
k
)
{\displaystyle {\binom {n}{k}}}
manipulações algébricas :
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
=
(
n
−
1
)
!
(
n
−
k
)
!
(
k
−
1
)
!
+
(
n
−
1
)
!
(
n
−
k
−
1
)
!
k
!
{\displaystyle {\binom {n-1}{k-1}}+{\binom {n-1}{k}}={\frac {(n-1)!}{(n-k)!(k-1)!}}+{\frac {(n-1)!}{(n-k-1)!k!}}}
=
(
n
−
1
)
!
k
(
n
−
k
)
!
(
k
−
1
)
!
k
+
(
n
−
k
)
(
n
−
1
)
!
(
n
−
k
)
(
n
−
k
−
1
)
!
k
!
=
(
k
+
(
n
−
k
)
)
(
n
−
1
)
!
(
n
−
k
)
!
k
!
{\displaystyle ={\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!}}}
=
n
(
n
−
1
)
!
(
n
−
k
)
!
k
!
=
n
!
(
n
−
k
)
!
k
!
=
(
n
k
)
.
{\displaystyle ={\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:
Ilustra a prova combinatória:
(
4
1
)
+
(
4
2
)
=
(
5
2
)
.
{\displaystyle {\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
{\displaystyle X}
conjunto finito não-vazio com
n
{\displaystyle n}
X
{\displaystyle X}
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
(
n
k
)
{\displaystyle {\binom {n}{k}}}
#
{
Y
:
(
Y
⊆
X
)
∧
(
#
Y
=
k
)
}
=
(
n
k
)
.
{\displaystyle \#\{Y:(Y\subseteq X)\land (\#Y=k)\}={\binom {n}{k}}.}
Por outro lado, destacando um elemento
x
∗
∈
X
{\displaystyle x^{\ast }\in X}
cardinal
#
{
Y
:
(
Y
⊆
X
)
∧
(
#
Y
=
k
)
}
{\displaystyle \#\{Y:(Y\subseteq X)\land (\#Y=k)\}}
Contamos o número de subconjuntos de
X
{\displaystyle X}
k
{\displaystyle k}
possuem
x
∗
{\displaystyle x^{\ast }}
#
{
Y
∪
{
x
∗
}
:
(
Y
⊆
X
∖
{
x
∗
}
)
∧
(
#
Y
=
k
−
1
)
}
=:
m
1
;
{\displaystyle \#\{Y\cup \{x^{\ast }\}:(Y\subseteq X\setminus \{x^{\ast }\})\land (\#Y=k-1)\}=:m_{1};}
Contamos o número de subconjuntos de
X
{\displaystyle X}
k
{\displaystyle k}
não possuem
x
∗
{\displaystyle x^{\ast }}
#
{
Y
:
(
Y
⊆
X
∖
{
x
∗
}
)
∧
(
#
Y
=
k
)
}
=:
m
2
;
{\displaystyle \#\{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
⊆
X
)
∧
(
#
Y
=
k
)
}
=
(
n
k
)
.
{\displaystyle m_{1}+m_{2}=\#\{Y:(Y\subseteq X)\land (\#Y=k)\}={\binom {n}{k}}.}
Agora, como
#
(
X
∖
{
x
∗
}
)
=
#
X
−
#
{
x
∗
}
=
n
−
1
{\displaystyle \#(X\setminus \{x^{\ast }\})=\#X-\#\{x^{\ast }\}=n-1}
m
1
=
(
n
−
1
k
−
1
)
{\displaystyle m_{1}={\binom {n-1}{k-1}}}
e
m
2
=
(
n
−
1
k
)
,
{\displaystyle m_{2}={\binom {n-1}{k}},}
donde ganha-se a relação.
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
,
…
,
k
m
{\displaystyle n,m,k_{1},k_{2},\ldots ,k_{m}}
m
≥
2
{\displaystyle m\geq 2}
1
≤
k
i
≤
n
{\displaystyle 1\leq k_{i}\leq n}
i
∈
{
1
,
2
,
…
,
m
}
{\displaystyle i\in \{1,2,\ldots ,m\}}
k
1
+
k
2
+
⋯
+
k
m
=
n
{\displaystyle k_{1}+k_{2}+\cdots +k_{m}=n}
(
n
−
1
k
1
−
1
,
k
2
,
…
,
k
m
)
+
(
n
−
1
k
1
,
k
2
−
1
,
…
,
k
m
)
+
⋯
+
(
n
−
1
k
1
,
k
2
,
…
,
k
m
−
1
)
=
(
n
k
1
,
k
2
,
…
,
k
m
)
.
{\displaystyle {\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
{\displaystyle m=2}
k
1
:=
k
{\displaystyle k_{1}:=k}
k
1
+
k
2
=
n
{\displaystyle k_{1}+k_{2}=n}
k
2
=
n
−
k
{\displaystyle k_{2}=n-k}
(
n
−
1
k
1
−
1
,
k
2
)
=
(
n
−
1
k
−
1
,
n
−
k
)
:=
(
n
−
1
k
−
1
)
{\displaystyle {\binom {n-1}{k_{1}-1,k_{2}}}={\binom {n-1}{k-1,n-k}}:={\binom {n-1}{k-1}}}
e
(
n
−
1
k
1
,
k
2
−
1
)
=
(
n
−
1
k
,
n
−
k
−
1
)
:=
(
n
−
1
k
)
,
{\displaystyle {\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
≥
2
{\displaystyle m\geq 2}
n
,
k
1
,
k
2
,
…
,
k
m
{\displaystyle n,k_{1},k_{2},\ldots ,k_{m}}
1
≤
k
i
≤
n
{\displaystyle 1\leq k_{i}\leq n}
1
≤
i
≤
m
{\displaystyle 1\leq i\leq m}
k
1
+
k
2
+
⋯
+
k
m
=
n
{\displaystyle k_{1}+k_{2}+\cdots +k_{m}=n}
(
n
−
1
k
1
−
1
,
k
2
,
…
,
k
m
)
+
(
n
−
1
k
1
,
k
2
−
1
,
…
,
k
m
)
+
⋯
+
(
n
−
1
k
1
,
k
2
,
…
,
k
m
−
1
)
{\displaystyle {\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}}}
=
(
n
−
1
)
!
(
k
1
−
1
)
!
k
2
!
⋯
k
m
!
+
(
n
−
1
)
!
k
1
!
(
k
2
−
1
)
!
⋯
k
m
!
+
⋯
+
(
n
−
1
)
!
k
1
!
k
2
!
⋯
(
k
m
−
1
)
!
{\displaystyle ={\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)!}}}
=
k
1
(
n
−
1
)
!
k
1
!
k
2
!
⋯
k
m
!
+
k
2
(
n
−
1
)
!
k
1
!
k
2
!
⋯
k
m
!
+
⋯
+
k
m
(
n
−
1
)
!
k
1
!
k
2
!
⋯
k
m
!
=
(
k
1
+
k
2
+
⋯
+
k
m
)
(
n
−
1
)
!
k
1
!
k
2
!
⋯
k
m
!
{\displaystyle ={\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}!}}}
=
n
(
n
−
1
)
!
k
1
!
k
2
!
⋯
k
m
!
=
n
!
k
1
!
k
2
!
⋯
k
m
!
=
(
n
k
1
,
k
2
,
…
,
k
m
)
.
{\displaystyle ={\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}}}.}
