美國數學競賽12年級- 有12個女生坐在一排椅子上(共12張椅子)。每個人都站起來，再重新入坐，但每個人只能選擇原座位或鄰座入坐。試問：有多少種入坐方式？

2022精選B (原 AMC S01E11)：AMC12 年級
有12個女生坐在一排椅子上(共12張椅子)。每個人都站起來，再重新入坐，但每個人只能選擇原座位或鄰座入坐。試問：有多少種入坐方式？
看到曾經做過的題目，可以試著想想看還有沒有其他的作法。
看到沒做過的題目，就自己先想想看，想不通再看答案，接著弄懂每一個步驟的為什麼。