การหาจำนวนสับเซตโดยใช้ fibonacci
 

ผมอ่านเฉลยแล้วไม่เข้าใจ ช่วยทีครับ:please:

โจทย์ถามว่า
จงหาจำนวนสับเซตของ {1,2,...,17} ที่ไม่มีเลขสองตัวใดๆในสับเซต อยู่ติดกัน

ลองพิจารณา วิธีจัดเรียงจัตุรัส 1x1 และผืนผ้า 1x2 ลงบน สี่เหลี่ยมมุมฉาก 1xn

n = 1; จะมี 1 วิธี คือ 1x1 เลย
n = 2; จะมี 2 วิธี คือ 1x1: 2 รูป กับ 1x2: 1 รูป

n = 3; เราก็แยกกรณีเป็นช่องที่ 2 ใส่กับยังไม่ใส่
ถ้าช่องที่สองใส่แล้้ว คือช่องที่สามก็ต้องใส่เป็นจัตุรัส กรณีนี้จำนวนวิธีก็เท่ากับ กรณี n = 2
ถ้าช่องที่สองยังไม่ใส่ คือต้องรวบช่องที่สองและสามเป็น 1x2 กรณีนี้จำนวนวิธีก็เท่ากับ กรณี n = 1

ก็พบว่ากรณี n = 3 เท่ากับกรณี n = 1 รวมกับกรณี n = 2

ในทำนองเดียวกันกรณี n = 4 เท่ากับกรณี n = 2 รวมกับกรณี n = 3

จึงได้ว่ากรณีที่ n จะมีจำนวนวิธี = $f_{n+1}$ วิธี

เราก็นำมาประยุกต์ใช้กับโจทย์นี้โดยให้ตัวเลขแต่ละตัวในเซต S แทนตำแหน่งในสี่เหลี่ยม 1x18
จึงได้ว่ามี $f_{19}$ วิธี

ไม่เข้าใจว่าทำไมถึงเป็น 1x18 ครับ รอคนอื่นมาดูให้

มีโจทย์เพชรยอด 54 (ม.ต้น) ข้อนึงครับใช้เอกลักษณ์นี้

มีคน 10 คนนั่งบนเก้าอี้ 10 ตัวเรียงบนเส้นตรง ถ้าคน 10 คนลุกขึ้นแล้วนั่งใหม่จงหาจำนวนวิธีที่จะนั่งติดเก้าอี้ตัวเดิม

ขอบคุณมากครับ เข้าใจวีธีแล้ว แต่ว่าเราจะเอามาประยุกต์ยังไงเหรอครับ
แล้วอย่างข้อเพชรนั้นทำไงหรอครับ
14. ชาย 10 คนนั่งเก้าอี้ 10 ตัวเรียงในเส้นตรง จากนั้นทุกคนยืนขึ้นเพื่อจะนั่งที่นั่งใหม่
จงหาว่ามีกี่วิธีที่ชายทั้ง 10 คนจะเลือกนั่งเก้าอี้ 10 ตัวนั้นโดยชายเเต่ละคนนั่งเก้าอี้ตัวเดิมหรือนั่งติดกับเก้าอี้ที่เขาเคยนั่ง

ข้อเพชรยอดมงกุฎตอบ $f_{11}$ = 89 รึเปล่าครับ