As 6 cadeiras de uma fi la são numeradas de 1 a 6 e devem ser ocupadas uma de cada vez de modo que,sempre que possível, é escolhida uma cadeira sem vizinhas ocupadas.
Por exemplo, é válida a ordem de ocupação 1 6 3 2 4 5, em que a primeira pessoa ocupa a cadeira 1, a segunda, a cadeira 6, a terceira, a cadeira 3, a quarta, a cadeira 2,
a quinta, a cadeira 4 e a última, a cadeira 5. Já a ordem
1 5 2 3 6 4 não é válida, pois a terceira pessoa sentou-se ao lado da primeira quando poderia ter se sentado em uma cadeira sem vizinhas ocupadas. Quantas ordens de ocupação válidas existem?