Fórum de Matemática
DÚVIDAS? Nós respondemos!

De quantas maneiras n estudantes podem ser divididos em 2 grupos, cada um contendo pelo menos um estudante?

Se n for par a resposta é

\(~^n C_1 + ~^n C_2 + \cdots + ~^n C_{n/2} = \sum_{i=1}^{n/2} ~^n C_i\)

já se n for impar,

\(~^n C_1 + ~^n C_2 + \cdots + ~^n C_{(n-1)/2} = \sum_{i=1}^{(n-1)/2} ~^n C_i\).

Não estou entendendo o raciocínio, o que seria Ci ?

Calculo que \(^nC_i\) seja o número de subconjuntos de i elementos de um conjunto de n elementos (que também é conhecido por combinações de \(n\), \(i\) a \(i\) e é usada muitas vezes a notação \({n \choose i}\)). O que o Sobolev está a fazer é identificar uma partição em dois grupo com o grupo mais pequeno, este terá entre 1 elemento e \(n/2\) elementos (caso n seja par) ou \((n-1)/2\) elementos (caso n seja ímpar). Como há \(^nC_i\) grupos de \(i\) elementos no conjunto de \(n\) alunos, segue-se que há \(^nC_i\) partições da turma em dois grupos em que o grupo mais pequeno tem i alunos, seja qual for o i entre 1 e (n-1)/2. No entanto se o i for n/2 (com n par) o número de partições é metade de \(^nC_i\) (pois cada partição pode ser identificada com qualquer dos dois grupos).
Logo a resposta é
\(~^n C_1 + ~^n C_2 + \cdots + \frac{~^n C_{n/2}}{2} = \sum_{i=1}^{n/2} ~^n C_i\) se n for par
\(~^n C_1 + ~^n C_2 + \cdots + ~^n C_{(n-1)/2} = \sum_{i=1}^{(n-1)/2} ~^n C_i\). se n for ímpar.
Outro método mais rápido é fixar um estudante e identificar uma partição do conjunto com o grupo a que o estudante pertence, o que equivale a identificar cada partição com um subconjunto dos restantes n-1 estudantes com excepção do conjunto de todos os n-1 alunos. Como num conjunto de n-1 elementos há \(2^{n-1}\) subconjuntos a resposta final será \(2^{n-1}-1\).