Combinatória - (cerimônia)

Uma cerimônia será realizada em um auditório e as dez cadeiras da primeira fila serão ocupadas por dez autoridades convidadas que confirmaram suas presenças. Por ordem de chegada, o primeiro convidado poderá ocupar qualquer uma das dez cadeiras e cada um dos outros, ao sentar-se, deverá ocupar uma cadeira ao lado de algum convidado já sentado. Nessa situação, o número de modos possíveis de esses convidados ocuparem os dez lugares na primeirafila é igual a
A) 512.
B) 1.024.
C) 2.400.
D) 4.800.
E )5.120

O total sempre será dado por 2^(N-1). Faça o exemplo para apenas 3 cadeiras, veja as possibilidades das autoridades (A1, A2 e A3) se sentarem, a começar pelo assentamento da autoridade A1, depois A2 e então A3.
A1-A2- A3; A2-A1-A3, A3-A1-A2, A3-A2-A1 => 4 = 2^(3-1) possibilidades.
Para 4 cadeiras e 4 autoridades teríamos:
A1-A2-A3-A4, A2-A1-A3-A4, A3-A1-A2-A4, A4-A1-A2-A3,
A4-A3-A2-A1, A4-A3-A1-A2, A4-A2-A1-A3, A3-A2-A1-A4 =>
=> 8 = 2^(4-1) possibilidades
Passei a tarde de 3a-feira toda tentando resolver este problema, e realmente a solução dá 2^(N-1) possibilidades para sentar N autoridades em N cadeira seguindo esta restrição de sentar sempre ao lado de alguém que já está sentando.
Eu já fui professor de Matemática e digo que este não é um problema trivial. Talvez haja uma outra maneira mais fácil de chegar na resposta 2^9 = 512 = 2^(10-1), porém eu a desconheço.
Resolvi o problema e achei a lei de formação usando as propriedades binomiais do triângulo de Pascal (soma de linhas e colunas), porém achei um problema difícil para uma prova de Concurso Público (se fosse Vestibular do ITA, IME, ainda vá lá...)
Eu adoro Combinatória, pena que a Área da ANAC que vou prestar (Especialista área 4) não vai cair Raciocínio Lógico, pelo menos eu me garanto no resto da Matemática, heh, heh!

Autor: Mmsilva100