สูตรสามเหลี่ยมปาสคาลพร้อมตัวอย่าง

สามเหลี่ยมปาสคาลคืออะไร?

สามเหลี่ยมปาสคาล คืออาร์เรย์ของตัวเลขรูปสามเหลี่ยมที่ปฏิบัติตามรูปแบบง่ายๆ โดยอิงจากแถวด้านบน นักคณิตศาสตร์ชาวฝรั่งเศส บлезал ปาสคาล เป็นผู้ทำให้สามเหลี่ยมนี้เป็นที่รู้จักอย่างแพร่หลายในศตวรรษที่ 17 สามเหลี่ยมนี้เริ่มต้นด้วยเลข "1" เพียงตัวเดียวที่ด้านบนสุด และทุกแถวถัดไปก็เริ่มต้นและสิ้นสุดด้วยเลข "1" เช่นกัน

นอกเหนือจากรูปทรงที่สวยงามแล้ว สามเหลี่ยมปาสคาลยังแฝงความสัมพันธ์ทางคณิตศาสตร์ที่ลึกซึ้งเอาไว้ มันมีความเกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีบททวินาม การนับเชิงการจัดเรียง และความน่าจะเป็น ซึ่งเป็นเหตุผลว่าทำไมมันจึงปรากฏอยู่ในห้องเรียนพีชคณิต สถิติ และวิทยาการคอมพิวเตอร์ทั่วโลก

ประวัติสามเหลี่ยมปาสคาล

แม้ว่าชื่อรูปสามเหลี่ยมจะตั้งตามชื่อของแบลส์ ปาสคาล แต่รูปสามเหลี่ยมนี้มีมาก่อนเขาหลายศตวรรษ ตำราคณิตศาสตร์ของจีน “เก้าบทว่าด้วยศิลปะทางคณิตศาสตร์” มีตัวอย่างที่เก่าแก่ที่สุดชิ้นหนึ่ง ซึ่งแสดงให้เห็นรูปแบบหลายอย่างที่คล้ายคลึงกับที่เราใช้ในปัจจุบัน

นักคณิตศาสตร์ชาวเปอร์เซีย อัล-คาราจี และนักวิชาการชาวอินเดีย Pingนอกจากนี้ ปาสคาลยังได้สำรวจอาร์เรย์ที่คล้ายกันอีกด้วย ปาสคาลได้วางกรอบคุณสมบัติของสามเหลี่ยมอย่างเป็นทางการในตำรา "Traité du triangle arithmétique" ที่เขียนขึ้นในปี ค.ศ. 1654 ซึ่งเป็นที่มาของชื่อเรียกสมัยใหม่ในคณิตศาสตร์ตะวันตกสำหรับโครงสร้างนี้

การก่อสร้างสามเหลี่ยมปาสคาล

การสร้างสามเหลี่ยมปาสคาลนั้นไม่ซับซ้อน กฎข้อเดียวที่ต้องจำคือแต่ละแถวเริ่มต้นและสิ้นสุดด้วยเลข 1 และตัวเลขอื่นๆ จะสร้างขึ้นจากแถวด้านบน

สำหรับแถว r และคอลัมน์ c ใดๆ ค่าที่ได้จะเท่ากับผลรวมของตัวเลขในคอลัมน์ c-1 และ c ของแถว r-1

ที่นี่

• r = 3, 4, 5, …
• n และ c = 2, 3, 4, …, r-1

ต่อไปนี้คือขั้นตอนในการสร้างสามเหลี่ยมปาสคาล:

ขั้นตอน 1) เริ่มจากการกรอกข้อมูลในสองแถวแรกก่อน

ขั้นตอน 2) องค์ประกอบที่สองของแถวที่สามคือผลรวมของตัวเลขแรกและตัวเลขที่สองในแถวที่สอง

ขั้นตอน 3) แถวที่สี่เริ่มต้นด้วยเลข “1” ตัวเลขที่สองคือ 3 ซึ่งเป็นผลรวมของ 1 และ 2 (ไฮไลต์ด้วยสีน้ำเงิน)

ภาพด้านล่างแสดงวิธีการกรอกข้อมูลในแถวที่สี่:

ขั้นตอน 4) แถวที่ห้าประกอบด้วยตัวเลขห้าตัว เราทราบรูปแบบการเติมตัวเลขลงในแต่ละแถวจากขั้นตอนก่อนหน้านี้แล้ว

สูตรสามเหลี่ยมปาสคาล – สัมประสิทธิ์ทวินาม

สัมประสิทธิ์ทวินามนับจำนวนวิธีในการเลือกเซตย่อยที่มี k องค์ประกอบจากเซตที่มี n องค์ประกอบ โดยทั่วไปจะเขียนในรูป “C(n, k)” หรือ “n เลือก k”

สัมประสิทธิ์ทวินามถูกกำหนดดังนี้:

เครื่องหมาย “!” แสดงถึงแฟกทอเรียลของจำนวนนั้น

n! = 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++ Code ของสามเหลี่ยมปาสคาลโดยแถวก่อนหน้า

#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 Code ของสูตรสามเหลี่ยมปาสคาลโดยแถวก่อนหน้า

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 คือจำนวนแถวในสามเหลี่ยมปาสคาล จึงต้องใช้ N² พื้นที่หน่วย ดังนั้น ความซับซ้อนของพื้นที่จึงเป็น O(N)²).

ฟังก์ชันนี้ใช้ลูปซ้อนกันสองลูป โดยแต่ละลูปทำงานซ้ำได้สูงสุด “N” ครั้ง ดังนั้น ความซับซ้อนของเวลาจึงเป็น เช่นกัน บน²)หรือความซับซ้อนของเวลาแบบยกกำลังสอง

วิธีที่ 2: การสร้างสามเหลี่ยมปาสคาลโดยการคำนวณสัมประสิทธิ์ทวินาม

เราสามารถหาค่าของสามเหลี่ยมปาสคาลได้โดยตรงโดยใช้สัมประสิทธิ์ทวินาม แผนภาพด้านล่างแสดงให้เห็นถึงความสัมพันธ์ดังกล่าว:

ต่อไปนี้คือขั้นตอนในการสร้างสามเหลี่ยมปาสคาลโดยการคำนวณสัมประสิทธิ์ทวินาม:

ขั้นตอน 1) แถวบนสุดคือ C(0, 0) โดยใช้สูตรข้างต้น C(0, 0) = 1 เพราะ 0! = 1

ขั้นตอน 2) สำหรับแถว “i” จะมีองค์ประกอบทั้งหมด “i” รายการ โดยแต่ละรายการจะคำนวณเป็น C(n, r) โดยที่ n คือ i-1

ขั้นตอน 3) ทำซ้ำขั้นตอนที่ 2 สำหรับจำนวนแถวของสามเหลี่ยมปาสคาลที่คุณต้องการสร้าง

C++ Code สามเหลี่ยมปาสคาลโดยใช้สัมประสิทธิ์ทวินาม

#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 Code สามเหลี่ยมปาสคาลโดยใช้สัมประสิทธิ์ทวินาม

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” ครั้ง ดังนั้น ความซับซ้อนของเวลาโดยรวมคือ O(n)³).

ความซับซ้อนของพื้นที่จัดเก็บคงที่ เนื่องจากเราไม่ได้จัดเก็บผลลัพธ์ระหว่างกลางใดๆ โปรแกรมคำนวณแต่ละองค์ประกอบแบบเรียลไทม์และพิมพ์ออกมาในแต่ละแถว ดังนั้นความซับซ้อนของพื้นที่จัดเก็บจึงลดลงเหลือ O (1).

วิธีที่ 3: การสร้างสามเหลี่ยมปาสกาลโดยดัดแปลงค่าสัมประสิทธิ์ทวินาม

ในเทคนิคก่อนหน้านี้ เราใช้สูตรสัมประสิทธิ์ทวินามในการคำนวณแต่ละองค์ประกอบ วิธีการที่ปรับปรุงใหม่นี้ได้มาจาก C(n, r) โดยตรงจาก C(n, r-1) ซึ่งช่วยลดขั้นตอนการทำงานลงได้ถึงหนึ่งลำดับ

ต่อไปนี้คือขั้นตอนในการสร้างสามเหลี่ยมปาสคาลโดยใช้สัมประสิทธิ์ทวินามที่ปรับเปลี่ยนแล้ว:

ขั้นตอน 1) เริ่มต้นแถวแรกด้วยเลข “1”

ขั้นตอน 2) คำนวณค่า C(n, r) โดยที่ “n” คือหมายเลขแถว และ “r” คือดัชนีคอลัมน์ กำหนดค่าที่ได้ให้กับตัวแปร C

ขั้นตอน 3) ในการคำนวณสัมประสิทธิ์ตัวถัดไป ให้ใช้ C * (n – k) / k กำหนดค่าใหม่นี้กลับเข้าไปใน C

ขั้นตอน 4) ดำเนินการขั้นตอนที่ 3 ต่อไปจนกว่า “k” จะถึงปลายแถว หลังจากแต่ละรอบ ให้เพิ่มค่า k ขึ้นหนึ่ง

C++ Code สำหรับสามเหลี่ยมปาสคาลโดยใช้สัมประสิทธิ์ทวินามที่ปรับปรุงแล้ว

#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 Code สำหรับสามเหลี่ยมปาสคาลโดยใช้สัมประสิทธิ์ทวินามที่ปรับปรุงแล้ว

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” คือจำนวนแถวในรูปสามเหลี่ยม ดังนั้น ความซับซ้อนของเวลาคือ บน²), เวลากำลังสอง

ในส่วนของความซับซ้อนด้านพื้นที่จัดเก็บ เราไม่จำเป็นต้องใช้อาร์เรย์ในการจัดเก็บข้อมูล เราใช้เพียงตัวแปรเดียวเพื่อเก็บค่าสัมประสิทธิ์ทวินามก่อนหน้า ดังนั้นเราจึงต้องการพื้นที่เพิ่มเพียงหนึ่งหน่วยเท่านั้น ความซับซ้อนด้านพื้นที่จัดเก็บจึงเป็นดังนี้ O (1).

การประยุกต์สามเหลี่ยมปาสคาล

ต่อไปนี้คือตัวอย่างการประยุกต์ใช้สามเหลี่ยมปาสคาลในทางปฏิบัติ:

การขยายทวินาม: สัมประสิทธิ์ของการกระจายทวินามใดๆ สามารถอ่านได้โดยตรงจากสามเหลี่ยมปาสคาล นี่คือตัวอย่าง:

การคำนวณชุดค่าผสม: องค์ประกอบของสามเหลี่ยมปาสคาลสอดคล้องโดยตรงกับสัมประสิทธิ์ทวินาม ตัวอย่างเช่น ถ้าคุณมีลูกบอล 6 ลูกและต้องการเลือก 3 ลูก คำตอบคือ ⁶C₃คุณสามารถหาค่าดังกล่าวได้จากองค์ประกอบที่ 3 ของแถวที่ 6 ในสามเหลี่ยมปาสคาล

ความน่าจะเป็น: สามเหลี่ยมของปาสคาลถูกนำมาใช้กันอย่างแพร่หลายในการคำนวณความน่าจะเป็นในการโยนเหรียญ ปัญหาลูกเต๋า และเหตุการณ์เชิงการจัดเรียงอื่นๆ ที่ผลลัพธ์แต่ละอย่างสอดคล้องกับการแจกแจงแบบทวินาม

ข้อเท็จจริงที่น่าสนใจเกี่ยวกับสามเหลี่ยมปาสคาล

ต่อไปนี้เป็นข้อเท็จจริงบางส่วนที่คุณจะพบว่าน่าสนใจเกี่ยวกับสามเหลี่ยมปาสคาล:

• ผลรวมของทุกองค์ประกอบในแต่ละแถวจะเป็นกำลังของ 2 เสมอ

• ผลรวมตามแนวทแยงมุมของแถวต่างๆ จะสร้างลำดับฟิโบนาชชีขึ้นมา

• แต่ละแถวสอดคล้องกับสัมประสิทธิ์ในการกระจายของ (a+b)ⁿ.
• หากคุณระบายสีเฉพาะตัวเลขคี่ รูปทรงที่ได้จะมีลักษณะเป็นแฟร็กทัลสามเหลี่ยมเซียร์ปินสกี

คำถามที่พบบ่อย