MathNet 2013 Câu hỏi 51

Có $n\ge2$ ngôi nhà ở phía bắc một con phố. Theo chiều từ tây sang đông, các nhà được đánh số từ $1$ tới $n$, mỗi số ghi trên một biển. Một ngày nọ, người dân trêu người đưa thư bằng cách đổi biển như sau: với mỗi cặp nhà kề nhau, hai biển hiện thời được đổi chỗ đúng một lần trong ngày.
Có bao nhiêu dãy biển số khác nhau có thể xuất hiện vào cuối ngày?