Como calcular o número de sequências de n posições com exatamente k símbolos A sem dois A adjacentes?

\(\displaystyle \binom{n-k+1}{k}\)

Coloque os k A nas lacunas formadas por os restantes (n−k) símbolos P (incluindo as extremidades); há \(n-k+1\) lacunas e escolhem-se k delas, daí \( \displaystyle \binom{n-k+1}{k}\).
Se desejar todas as configurações com qualquer número de A, some para \(k=0,\dots,\lfloor (n+1)/2\rfloor\): \( \displaystyle \sum_{k=0}^{\lfloor (n+1)/2\rfloor}\binom{n-k+1}{k}\).

Exemplo:
Para \(n=6\) e \(k=3\): \(\displaystyle \binom{6-3+1}{3}=\binom{4}{3}=4\).
Total para \(n=6\) somando \(k=0\) a \(3\): \(1+6+10+4=21\).