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

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^{*} \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^{*}$ , isto é, determinamos

# {Y \cup {x^{*}} : (Y \subseteq X ∖ {x^{*}}) \land (# Y = k - 1)} = : m_{1};

Contamos o número de subconjuntos de $X$ com $k$ elementos que não possuem $x^{*}$ , isto é, determinamos

# {Y : (Y \subseteq X ∖ {x^{*}}) \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 ∖ {x^{*}}) = # X - # {x^{*}} = 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}, \dots, k_{m}

tais que

m \geq 2

,

1 \leq k_{i} \leq n

para cada

i \in {1, 2, \dots, m}

e

k_{1} + k_{2} + \dots + k_{m} = n

(\binom{n - 1}{k_{1} - 1, k_{2}, \dots, k_{m}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, \dots, k_{m}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, \dots, k_{m} - 1}) = (\binom{n}{k_{1}, k_{2}, \dots, 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}, \dots, k_{m}$ naturais tais que $1 \leq k_{i} \leq n$ , para cada índice $1 \leq i \leq m$ , e $k_{1} + k_{2} + \dots + k_{m} = n$ . Então

(\binom{n - 1}{k_{1} - 1, k_{2}, \dots, k_{m}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, \dots, k_{m}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, \dots, k_{m} - 1})

= \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! \dots k_{m}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! \dots k_{m}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! \dots (k_{m} - 1)!}

= \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! \dots k_{m}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! \dots k_{m}!} + \dots + \frac{k_{m} (n - 1)!}{k_{1}! k_{2}! \dots k_{m}!} = \frac{(k_{1} + k_{2} + \dots + k_{m}) (n - 1)!}{k_{1}! k_{2}! \dots k_{m}!}

= \frac{n (n - 1)!}{k_{1}! k_{2}! \dots k_{m}!} = \frac{n!}{k_{1}! k_{2}! \dots k_{m}!} = (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) .

Ver também

Triângulo de Pascal

Notas

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

Referências

Predefinição:Citar livro

Ligações externas

Pascal's rule em PlanetMath Predefinição:En
Pascal's rule proof em PlanetMath Predefinição:En

Predefinição:Portal3

[1] referência a Michael Stifel (1487 — 1567), matemático alemão

[2] referência a Blaise Pascal (1623 — 1662), matemático francês

[1]

[2]

Relação de Stifel

Índice

Demonstração algébrica

Demonstração combinatória

Generalização para coeficientes multinomiais

Ver também

Notas

Referências

Ligações externas

Menu de navegação

Relação de Stifel

Demonstração algébrica

Demonstração combinatória

Generalização para coeficientes multinomiais

Ver também

Notas

Referências

Ligações externas

Menu de navegação

Pesquisa