สามเหลี่ยมปาสคาล – สูตร รูปแบบ และตัวอย่าง
ซาราห์ เฉิน
สามเหลี่ยมปาสคาลคืออะไร?
สามเหลี่ยมปาสกาล (Pascal's Triangle) คือกลุ่มตัวเลขสามเหลี่ยมที่มีรูปแบบและการเชื่อมโยงเฉพาะกับแถวก่อนหน้า สามเหลี่ยมนี้ประดิษฐ์ขึ้นโดยเบลส ปาสกาล โดยสามเหลี่ยมนี้เริ่มต้นด้วยองค์ประกอบหนึ่งตัวในแถวแรก หลังจากนั้น แถวแต่ละแถวจะเริ่มต้นและลงท้ายด้วยเลข “1”
ประวัติสามเหลี่ยมปาสคาล
หนังสือจีนเรื่อง “The Nine Chapters on the Mathematical Art” มีตัวอย่างแรกๆ ของสามเหลี่ยมปาสคาล นอกจากนี้ ยังมีรูปแบบและคุณสมบัติบางอย่างแบบเดียวกับที่พบในรูปสามเหลี่ยมในปัจจุบัน
ปาสกาลเป็นหนึ่งในคนหลายคนในยุโรปที่ศึกษาเรื่องสามเหลี่ยม นักคณิตศาสตร์คนอื่นๆ ก็ได้ศึกษาเรื่องอาร์เรย์ของตัวเลขสามเหลี่ยมที่คล้ายคลึงกันมาก่อนเขา
การก่อสร้างสามเหลี่ยมปาสคาล
การสร้างสามเหลี่ยมปาสกาลนั้นง่ายมาก สิ่งเดียวที่คุณต้องจำไว้คือ แถวเริ่มต้นและสิ้นสุดด้วย 1 กฎสำหรับตัวเลขที่เหลือมีดังนี้:
สำหรับแถว r และคอลัมน์ c ใดๆ จำนวนจะเป็นผลรวมของคอลัมน์ c-1 และ c จากแถว r-1
ที่นี่
- ร = 3,4,5….
- n และ c = 2,3,4,…r-1
ต่อไปนี้เป็นขั้นตอนในการสร้าง Pascal's Triangle:
ขั้นตอน 1) เริ่มต้นด้วยการเติมสองแถว
ขั้นตอน 2) องค์ประกอบที่สองสำหรับบรรทัดที่สามคือผลรวมของตัวเลขแรกและตัวเลขที่สองในแถวที่สอง
ขั้นตอน 3) แถวที่สี่จะเริ่มต้นด้วย "1" ตัวเลขตัวที่สองคือ 3 ซึ่งเป็นผลรวมของ 1 และ 2 (เน้นด้วยสีน้ำเงิน)
รูปภาพด้านล่างแสดงวิธีการเติมแถวที่สี่:
ขั้นตอน 4) แถวที่ 5 จะประกอบด้วยตัวเลข 5 ตัว เรารู้รูปแบบการเติมข้อมูลในแถวจากขั้นตอนก่อนหน้านี้แล้ว
สูตรสามเหลี่ยมปาสคาล – สัมประสิทธิ์ทวินาม
ค่าสัมประสิทธิ์ทวินามคือตัวเลขที่แสดงวิธีการต่างๆ ในการเลือกเซตย่อยขององค์ประกอบ k จากชุดขององค์ประกอบ n ตัว บ่อยครั้งจะเขียนว่า “C(n,k)” หรือ “n choose k”
ค่าสัมประสิทธิ์ทวินามถูกกำหนดให้เป็น
“!” หมายถึง "แฟกทอเรียล"
มะ! = n.(n-1) (n-2)…3.2.1
ตัวอย่างเช่น
5! = 5.4.3.2.1
= 120
สมมุติว่า C(5,3) หรือ 5 เลือก 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
วิธีที่ 1: สร้างสามเหลี่ยมปาสคาลจากแถวก่อนหน้า
ขั้นตอนในกระบวนงานนี้เหมือนกับขั้นตอนในสามเหลี่ยมปาสคาล สมมติว่าเราต้องการสร้างสามเหลี่ยมปาสคาลสูงสุดเจ็ดแถว
ขั้นตอนในการทำให้สำเร็จมีดังนี้:
ขั้นตอน 1) เริ่มต้นแถวบนสุดด้วย "1"
ขั้นตอน 2) สำหรับแถว “r” รายการ “c” จะเป็นผลคูณของ “c-1” และ “c” ซึ่งเป็นหมายเลขของแถว “r-1”
ขั้นตอน 3) ตัวเลขแรกและตัวเลขสุดท้ายในแถวจะต้องเป็น “1” เสมอ
เราต้องปฏิบัติตามสามขั้นตอนง่ายๆ นี้เพื่อสร้างสามเหลี่ยมปาสคาล
C++ โค้ดสามเหลี่ยมปาสกาลจากแถวก่อนหน้า
#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
int numbers[n][n];
for (int row = 0; row < n; row++)
{
for (int col = 0; col <= row; col++)
{
if (col == 0 || col == row)
{
numbers[row][col] = 1;
}
else
{
numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
}
cout << numbers[row][col] << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printRow(n);
}
Output:
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Python โค้ดสูตรสามเหลี่ยมปาสกาลจากแถวก่อนหน้า
def printRow(n):
numbers = [[0 for row in range(n)]
for col in range(n)
]
for row in range(len(numbers)):
for col in range(0, row+1):
if row == col or col == 0:
numbers[row][col] = 1
else:
numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]
print(numbers[row][col],end="\t")
print("\n")
n = int(input("How many rows: "))
printRow(n)
ผลลัพธ์ตัวอย่างสามเหลี่ยมของปาสคาล:
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
การวิเคราะห์ความซับซ้อน
A อาร์เรย์สองมิติ ถูกนำมาใช้ในการดำเนินการ โดยที่ N คือจำนวนแถวในสามเหลี่ยมปาสคาล สิ่งนี้จะต้องใช้ N2 พื้นที่หน่วย ดังนั้น O จะเป็นความซับซ้อนของพื้นที่ (N2).
เรามีสองลูปในฟังก์ชัน และแต่ละลูปทำงานเป็นเวลา "N" ครั้ง ดังนั้นความซับซ้อนของเวลาจึงเหมือนกัน บน2) หรือความซับซ้อนของเวลาแบบกำลังสอง
วิธีที่ 2: การสร้างสามเหลี่ยมปาสกาลโดยการคำนวณสัมประสิทธิ์ทวินาม
เราสามารถหาค่าของสามเหลี่ยมปาสกาลได้ง่ายๆ โดยใช้ค่าสัมประสิทธิ์ทวินาม นี่คือแผนภาพ:
ต่อไปนี้เป็นขั้นตอนในการสร้างสามเหลี่ยมปาสกาลโดยการคำนวณทวินาม:
ขั้นตอน 1) แถวบนสุดจะเป็น C(0,0) ใช้สูตรด้านบนสำหรับค่าสัมประสิทธิ์ทวินาม C(0,0) = 1 เพราะ 0! = 1.
ขั้นตอน 2) สำหรับแถว “i” จะมีองค์ประกอบ “i” ทั้งหมด แต่ละรายการจะถูกคำนวณ C(n,r) โดยที่ n จะเป็น i-1
ขั้นตอน 3) ทำซ้ำขั้นตอนที่ 2 ตามจำนวนแถวที่คุณต้องการสร้างสามเหลี่ยมปาสคาล
C++ สามเหลี่ยมของรหัสปาสคาลโดยสัมประสิทธิ์ทวินาม
#include <iostream>
using namespace std;
int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}
int binomialCoefficient(int n, int r)
{
int result = 1;
if (r > n)
{
return -1;
}
result = factorial(n) / (factorial(r) * factorial(n - r));
return result;
}
void printPascalTriangle(int row)
{
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= i; j++)
{
cout << binomialCoefficient(i, j) << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "Enter row number: ";
cin >> n;
printPascalTriangle(n);
}
Output:
Enter row number: 9 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Python สามเหลี่ยมของรหัสปาสคาลโดยสัมประสิทธิ์ทวินาม
def factorial(n):
result = 1
for i in range(1,n+1):
result*=i
return result
def binomialCoefficient(n,r):
result =1
if r>n:
return None
result = factorial(n) / (factorial(r) * factorial(n - r))
return int(result)
def printPascalTriangle(row):
for i in range(row+1):
for j in range(i+1):
print(binomialCoefficient(i, j), end="\t")
print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)
ผลลัพธ์ตัวอย่างสามเหลี่ยมของปาสคาล:
Enter row number: 8 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1
การวิเคราะห์ความซับซ้อน
มีการใช้ลูปสามอันในการใช้งาน ลูปหนึ่งใช้สำหรับคำนวณค่าสัมประสิทธิ์ทวินาม และอีกสองลูปใช้สำหรับสร้างตัวเลขสำหรับทุกแถว สำหรับจำนวนแถว เรามีลูปสามอันที่ดำเนินการ "n" ครั้ง ดังนั้นความซับซ้อนของเวลาโดยรวมจะเท่ากับ 0(n)3).
ความซับซ้อนของพื้นที่ในตอนนี้คงที่เนื่องจากเราไม่ได้เก็บข้อมูลใดๆ ไว้ในหน่วยเก็บข้อมูล โปรแกรมจะคำนวณองค์ประกอบ และพิมพ์ออกมาเป็นแถว จากนั้นความซับซ้อนของพื้นที่จะลดลงเหลือ 0(1)
วิธีที่ 3: การสร้างสามเหลี่ยมปาสกาลโดยดัดแปลงค่าสัมประสิทธิ์ทวินาม
ในเทคนิคก่อนหน้านี้ เราได้เห็นวิธีใช้สัมประสิทธิ์ทวินามในการคำนวณแต่ละองค์ประกอบของสามเหลี่ยมปาสคาลแล้ว วิธีนี้จะกำหนด C(n,r) จาก C (n, r-1) มันจะทำให้สิ่งต่าง ๆ ง่ายขึ้นด้วยคำสั่งเดียว
ต่อไปนี้เป็นขั้นตอนในการสร้างสามเหลี่ยมปาสคาลด้วยค่าสัมประสิทธิ์ทวินามดัดแปลง:
ขั้นตอน 1) เริ่มต้นแถวแรกด้วย "1"
ขั้นตอน 2) คำนวณ C(n,r) โดยที่ “n” คือหมายเลขแถว และ “r” คือคอลัมน์หรือองค์ประกอบ กำหนดค่าในตัวแปร C
ขั้นตอน 3) ในการคำนวณ C(n,k) มันจะเป็น C*(nk)/k ตอนนี้กำหนดค่านี้ให้กับ C
ขั้นตอน 4) ทำขั้นตอนที่ 3 ต่อไปจนกระทั่ง “k” ไปถึงจุดสิ้นสุดของแถว หลังจากการวนซ้ำแต่ละครั้ง ให้เพิ่มค่า K ทีละหนึ่ง
C++ รหัสสำหรับสามเหลี่ยมปาสคาลโดยค่าสัมประสิทธิ์ทวินามที่แก้ไขแล้ว
#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
for (int row = 1; row <= n; row++)
{
int previous_coef = 1;
for (int col = 1; col <= row; col++)
{
cout << previous_coef << "\t";
previous_coef = previous_coef * (row - col) / col;
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printpascalTriangle(n);
}
Output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python รหัสสำหรับสามเหลี่ยมปาสคาลโดยค่าสัมประสิทธิ์ทวินามที่แก้ไขแล้ว
def printpascalTriangle(n):
for row in range(1, n+1):
previous_coef = 1
for col in range(1, row+1):
print(previous_coef, end="\t")
previous_coef = int(previous_coef*(row-col)/col)
print()
n = int(input("How many rows: "))
printpascalTriangle(n)
ผลลัพธ์ของรูปแบบสามเหลี่ยมของ Pascal:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
การวิเคราะห์ความซับซ้อน
การใช้งานมีสองลูป แต่ละลูปทำงานสูงสุด "n" ครั้ง โดย "n" หมายถึงจำนวนแถวในสามเหลี่ยมปาสกาล ดังนั้นความซับซ้อนของเวลาคือ บน2), เวลากำลังสอง
เมื่อพิจารณาถึงความซับซ้อนของพื้นที่ เราไม่จำเป็นต้องใช้อาร์เรย์ใดๆ ในการจัดเก็บ เราเพียงแค่ใช้ตัวแปรหนึ่งตัวเพื่อรักษาค่าสัมประสิทธิ์ทวินามก่อนหน้า ดังนั้น เราจึงต้องการพื้นที่เพิ่มเติมเพียงหนึ่งพื้นที่ ความซับซ้อนของพื้นที่จึงกลายเป็น O (1).
การประยุกต์สามเหลี่ยมปาสคาล
ต่อไปนี้คือตัวอย่างการใช้งานของ Pascal's Triangle:
การขยายทวินาม: เราสามารถหาค่าสัมประสิทธิ์ของการขยายทวินามจากสามเหลี่ยมปาสคาลได้ นี่คือตัวอย่าง:
| (x + ย)0 | 1 |
| (x + ย)1 | 1.x + 1.y |
| (x + ย)2 | 1x2 + 2xy+ 1y2 |
| (x + ย)3 | 1x3 + 3x2และ + 3xy2 + 1y3 |
| (x + ย)4 | 1x4 + 4x3และ + 6x2y2 + 4xy3 + 1y4 |
การคำนวณชุดค่าผสม: เราเคยเห็นองค์ประกอบของสามเหลี่ยมปาสคาลเทียบเท่ากับสัมประสิทธิ์ทวินาม ตัวอย่างเช่น ถ้าคุณมี 6 ลูกและถูกขอให้เลือก 3 ลูก ก็จะเป็นเช่นนั้น 6C3. หรือคุณสามารถหาตัวเลขในองค์ประกอบที่ 3 ของแถวที่ 6 จากสามเหลี่ยมปาสคาล
ข้อเท็จจริงที่น่าสนใจเกี่ยวกับสามเหลี่ยมปาสคาล
ต่อไปนี้เป็นข้อเท็จจริงบางส่วนที่คุณจะพบว่าน่าสนใจเกี่ยวกับสามเหลี่ยมปาสคาล:
- ผลรวมของสมาชิกทุกตัวในแถวจะมีกำลังเป็น 2 เสมอ
- ผลรวมขององค์ประกอบของแถวในแนวทแยงทำให้เกิดลำดับฟีโบนัชชี
สรุป
- สามเหลี่ยมของปาสกาลให้ค่าสัมประสิทธิ์สำหรับการขยายทวินาม
- แต่ละแถวของสามเหลี่ยมปาสกาลเริ่มต้นและสิ้นสุดด้วย “1” ค่ากลางคือผลรวมของสององค์ประกอบของแถวก่อนหน้า
- การบวกองค์ประกอบทั้งหมดในสามเหลี่ยมปาสกาลในแนวทแยงจะทำให้คุณได้ ลำดับ Fibonacci.
- สามเหลี่ยมของปาสกาลสามารถสร้างได้ด้วยสัมประสิทธิ์ทวินาม
