Flashcard FC830914
Como calcular a soma das cardinalidades de todos os subconjuntos de um conjunto com n elementos?
Conjuntos
SELECON · 2023
Como calcular a soma das cardinalidades de todos os subconjuntos de um conjunto com n elementos?
Mostrar resposta e comentário
Resposta
\(n\cdot 2^{\,n-1}\)Explicação:
Cada um dos \(n\) elementos pertence a exatamente \(2^{\,n-1}\) subconjuntos, portanto cada elemento é contado \(2^{\,n-1}\) vezes na soma das cardinalidades, resultando em \(n\cdot 2^{\,n-1}\).
Alternativamente, usa-se a identidade \(\sum_{k=0}^{n} k\binom{n}{k}=n2^{\,n-1}\).
Exemplo:
Se \(n=4\), então a soma é \(4\cdot 2^{3}=4\cdot 8=32\).
Verificação: \(\sum_{k=0}^{4} k\binom{4}{k}=1\cdot\binom{4}{1}+2\cdot\binom{4}{2}+3\cdot\binom{4}{3}+4\cdot\binom{4}{4}=1\cdot4+2\cdot6+3\cdot4+4\cdot1=4+12+12+4=32\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/828400
Conteúdo do catálogo FC Concursos · Atualizado em