Lema de Kaplansky
Conta subconjuntos de $p$ elementos, entre $1,\dots,n$ dispostos em fila ou em círculo, sem dois elementos consecutivos. Ferramenta pouco lembrada mas cobrada em ITA/IME em problemas de "sem vizinhos" — resolve sem enumerar caso a caso.
Aprofundar ▾
O Lema de Kaplansky resolve o problema de contar quantos subconjuntos de $p$ elementos podemos escolher de $\{1,2,\dots,n\}$ sem tomar dois números consecutivos, e sua força está em generalizar esse raciocínio para arranjos circulares, que costumam aparecer disfarçados em problemas de fichas, cadeiras ou pontos numa circunferência. No caso linear, a ideia é imaginar que, ao escolher os $p$ elementos, sobram $n-p$ elementos não escolhidos que funcionam como "separadores": distribuímos os $p$ escolhidos nos $n-p+1$ espaços criados por esses separadores, o que leva à fórmula $\binom{n-p+1}{p}$. No caso circular, o número cai para $\frac{n}{n-p}\binom{n-p}{p}$, obtido fixando se um elemento entra ou não e reduzindo ao caso linear.
Para fixar, suponha $n=8$ e $p=3$ em fila: queremos ternos sem consecutivos, como $\{1,4,7\}$ ou $\{2,5,8\}$, mas não $\{1,2,5\}$. Aplicando a fórmula, $\binom{8-3+1}{3}=\binom{6}{3}=20$. Em círculo, com os mesmos $8$ e $3$, o resultado é $\frac{8}{5}\binom{5}{3}=16$, refletindo as simetrias que eliminam configurações equivalentes por rotação.