Integer sequence

Integer Sequence

ในมุมมองทางคณิตศาสตร์ sequence คือรายการของ objects หรือ events ที่นำมาจัดเรียงกัน โดยสมาชิกจะมีความสัมพันธ์ต่อกันในเชิงเส้นตรง (linear relationship หรือ linear association) นั่นคือถ้าสามารถนำเอาความสัมพันธ์ระหว่างสมาชิกมา plot ลงแผนภาพได้ ก็จะได้รูปแบบของเส้นตรง ดังนั้น integer sequence จึงหมายถึง sequence ของ integer ตัวอย่างของ integer sequence ได้แก่

Fibonacci sequence จะต้องเริ่มต้นด้วยตัวเลข 0,1 ตั้งแต่ตัวที่ 3 เป็นต้นไปจะหาได้จากความสัมพันธ์ $X_n=X_{n-1}+X_{n-2}$ sequence ของ Fibonacci จะเป็น 0,1,1,2,3,5,8,13,21,34,55,... เราอาจเคยได้ยินเรื่อง Golden ratio หรือ Spiral leave growth นั้นคือตัวอย่างของ Fibonacci sequence ที่พบได้ในธรรมชาติ เช่น เปลือกหอย หรือ การงอกของใบพืช

ภาพที่ 1 รูปแบบของเปลือกหอยสอดคล้องกับ Fibonacci sequence

Linear recurrence relation

Linear recurrence relation คือ ความสัมพันธ์หรือสมการที่ใช้คำนวณค่าของสมาชิกตำแหน่งใดๆ จากสมาชิกตำแหน่งก่อนหน้าใน sequence โดยความสัมพันธ์จะแสดงในรูปแบบของ first degree polynomial (กำลังสูงสุดของตัวแปรมีค่าเป็น 1) รูปแบบทั่วไปคือ

$$\begin{array}{}\text{(1.0)}& X_n=C_1{X}_{n-1}+C_2{X}_{n-2}+C_3{X}_{n-3}+...\end{array}$$

โดย $C_i$ เป็นค่าคงที่

ตัวอย่าง

หา $X_5$ เมื่อกำหนดให้ $X_1=1$ และ $X_n=3X_{n-1}+2$

จากความสัมพันธ์ที่กำหนดให้จะได้ $$\begin{array}{rl}{X}_2& =3(1)+2=5\\ X_3& =3(5)+2=17\\ X_4& =3(17)+2=53\\ \therefore X_5& =3(53)+2=161\end{array}$$