Rumus Segitiga Pascal Beserta Contohnya

Apa itu Segitiga Pascal?

Segitiga Pascal adalah susunan angka berbentuk segitiga yang mengikuti pola sederhana berdasarkan baris di atasnya. Segitiga ini dipopulerkan oleh matematikawan Prancis Blaise Pascal pada abad ke-17. Segitiga ini dimulai dengan angka "1" tunggal di bagian atas, dan setiap baris berikutnya juga dimulai dan diakhiri dengan angka "1".

Di balik bentuknya yang elegan, Segitiga Pascal mengandung hubungan matematis yang mendalam. Segitiga ini terkait erat dengan teorema binomial, penghitungan kombinatorial, dan probabilitas, itulah sebabnya segitiga ini muncul di kelas aljabar, statistika, dan ilmu komputer di seluruh dunia.

Sejarah Segitiga Pascal

Meskipun dinamai menurut nama Blaise Pascal, segitiga sebenarnya sudah ada berabad-abad sebelum dia. Teks matematika Tiongkok "Sembilan Bab tentang Seni Matematika" memuat salah satu contoh paling awal yang diketahui, yang menampilkan banyak pola yang sama dengan yang kita gunakan saat ini.

Matematikawan Persia Al-Karaji dan cendekiawan India PingAla juga mengeksplorasi susunan serupa. Pascal memformalkan sifat-sifat segitiga dalam risalahnya tahun 1654 "Traité du triangle arithmétique," yang memberikan struktur tersebut nama modernnya dalam matematika Barat.

Konstruksi Segitiga Pascal

Membangun Segitiga Pascal itu mudah. ​​Satu-satunya aturan yang perlu diingat adalah setiap baris dimulai dan diakhiri dengan angka 1, dan setiap angka lainnya dibangun dari baris di atasnya.

Untuk setiap baris r dan kolom c, nilainya sama dengan jumlah angka di kolom c-1 dan c pada baris r-1.

Di sini,

• r = 3, 4, 5, …
• n dan c = 2, 3, 4, …, r-1.

Berikut langkah-langkah untuk membangun Segitiga Pascal:

Langkah 1) Mulailah dengan mengisi dua baris pertama.

Langkah 2) Elemen kedua pada baris ketiga adalah jumlah dari angka pertama dan kedua pada baris kedua.

Langkah 3) Baris keempat dimulai dengan angka “1”. Angka kedua adalah 3, yang merupakan jumlah dari 1 dan 2 (ditandai dengan warna biru).

Gambar di bawah ini menunjukkan cara mengisi baris keempat:

Langkah 4) Baris kelima terdiri dari lima angka. Kita sudah mengetahui pola pengisian baris dari langkah-langkah sebelumnya.

Rumus Segitiga Pascal – Koefisien Binomial

Koefisien binomial menghitung jumlah cara untuk memilih subset k elemen dari kumpulan n elemen. Koefisien ini umumnya ditulis sebagai “C(n, k)” atau “n pilih k.”

Koefisien binomial didefinisikan sebagai:

Simbol “!” menunjukkan faktorial dari suatu bilangan.

n! = n.(n-1).(n-2)…3.2.1

Sebagai contoh,

5! = 5.4.3.2.1

= 120

Jadi, C(5, 3) atau “5 pilih 3” = 5! / 3!(5-3)!

= 120 / 12

= 10

Metode 1: Membangun Segitiga Pascal dengan Baris Sebelumnya

Prosedur di sini mencerminkan cara kita menggambar segitiga secara manual. Misalkan kita ingin menghasilkan segitiga Pascal hingga tujuh baris.

Langkah-langkah untuk melakukannya adalah sebagai berikut:

Langkah 1) Awali baris paling atas dengan angka “1”.

Langkah 2) Untuk baris “r”, elemen “c” akan menjadi jumlah kolom “c-1” dan kolom “c” dari baris “r-1”.

Langkah 3) Angka pertama dan terakhir di setiap baris akan selalu “1”.

Dengan mengikuti tiga langkah sederhana ini, kita dapat secara sistematis membangun seluruh segitiga.

C++ Code Segitiga Pascal berdasarkan Baris Sebelumnya

#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);
}

Keluaran:

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 Rumus Segitiga Pascal berdasarkan Baris Sebelumnya

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)

Keluaran Contoh Segitiga Pascal:

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

Analisis Kompleksitas

A array dua dimensi digunakan dalam implementasi ini. Mengingat N adalah jumlah baris dalam segitiga Pascal, ini membutuhkan N.² ruang satuan. Oleh karena itu, kompleksitas ruangnya adalah O(N).²).

Fungsi tersebut menggunakan dua loop bersarang, masing-masing berjalan hingga "N" kali. Jadi, kompleksitas waktunya juga adalah DI²)atau kompleksitas waktu kuadrat.

Metode 2: Membangun Segitiga Pascal dengan Menghitung Koefisien Binomial

Kita dapat menurunkan angka-angka segitiga Pascal secara langsung menggunakan koefisien binomial. Diagram di bawah ini mengilustrasikan hubungan tersebut:

Berikut langkah-langkah untuk membangun Segitiga Pascal dengan menghitung koefisien binomial:

Langkah 1) Baris paling atas adalah C(0, 0). Dengan menggunakan rumus di atas, C(0, 0) = 1, karena 0! = 1.

Langkah 2) Untuk baris “i”, akan ada total “i” elemen. Setiap item dihitung sebagai C(n, r), di mana n adalah i-1.

Langkah 3) Ulangi langkah 2 untuk sebanyak baris segitiga Pascal yang ingin Anda hasilkan.

C++ Code Segitiga Pascal dengan Koefisien Binomial

#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);
}

Keluaran:

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 Segitiga Pascal dengan Koefisien Binomial

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)

Keluaran Contoh Segitiga Pascal:

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

Analisis Kompleksitas

Dalam implementasi ini digunakan tiga loop: satu untuk menghitung koefisien binomial dan dua lagi untuk mengulangi setiap baris dan kolom. Sehubungan dengan jumlah baris, ketiga loop tersebut berjalan hingga "n" kali. Akibatnya, kompleksitas waktu keseluruhan adalah O(n).³).

Kompleksitas ruangnya konstan karena kita tidak menyimpan hasil sementara apa pun. Program menghitung setiap elemen secara langsung dan mencetaknya dalam satu baris, sehingga kompleksitas ruangnya berkurang menjadi O (1).

Metode 3: Membangun Segitiga Pascal dengan Koefisien Binomial yang Dimodifikasi

Pada teknik sebelumnya, kami menggunakan rumus koefisien binomial untuk menghitung setiap elemen. Pendekatan yang dimodifikasi ini menurunkan C(n, r) langsung dari C(n, r-1), sehingga mengurangi pekerjaan hingga satu orde besarnya.

Berikut langkah-langkah untuk membangun Segitiga Pascal dengan menggunakan koefisien binomial yang dimodifikasi:

Langkah 1) Awali baris pertama dengan angka “1”.

Langkah 2) Hitung C(n, r), di mana “n” adalah nomor baris dan “r” adalah indeks kolom. Tetapkan nilai tersebut ke variabel C.

Langkah 3) Untuk menghitung koefisien berikutnya, gunakan C * (n – k) / k. Tetapkan nilai baru ini kembali ke C.

Langkah 4) Lanjutkan langkah 3 hingga “k” mencapai ujung baris. Setelah setiap iterasi, tambahkan satu pada nilai k.

C++ Code untuk Segitiga Pascal dengan Koefisien Binomial yang Dimodifikasi

#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);
}

Keluaran:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Python Code untuk Segitiga Pascal dengan Koefisien Binomial yang Dimodifikasi

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)

Keluaran Pola Segitiga Pascal:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Analisis Kompleksitas

Implementasi ini menggunakan dua loop, masing-masing berjalan maksimal “n” kali, di mana “n” adalah jumlah baris dalam segitiga. Jadi, kompleksitas waktunya adalah Di²), waktu kuadrat.

Mengenai kompleksitas ruang, kita tidak memerlukan array untuk penyimpanan. Kita hanya menggunakan satu variabel untuk menyimpan koefisien binomial sebelumnya, sehingga kita hanya membutuhkan satu ruang tambahan. Oleh karena itu, kompleksitas ruangnya adalah O (1).

Penerapan Segitiga Pascal

Berikut beberapa aplikasi praktis dari Segitiga Pascal:

Ekspansi Binomial: Koefisien dari ekspansi binomial apa pun dapat dibaca langsung dari segitiga Pascal. Berikut contohnya:

Menghitung Kombinasi: Elemen-elemen segitiga Pascal berhubungan langsung dengan koefisien binomial. Misalnya, jika Anda memiliki 6 bola dan ingin memilih 3, jawabannya adalah ⁶C₃Anda dapat menemukan nilai tersebut pada elemen ke-3 dari baris ke-6 segitiga Pascal.

Kemungkinan: Segitiga Pascal banyak digunakan untuk menghitung probabilitas dalam pelemparan koin, soal dadu, dan peristiwa kombinatorial lainnya di mana setiap hasil sesuai dengan distribusi binomial.

Fakta Menarik Tentang Segitiga Pascal

Berikut beberapa fakta menarik tentang segitiga Pascal:

• Jumlah semua elemen dalam setiap baris selalu merupakan pangkat 2.

• Jumlah diagonal dari setiap baris menghasilkan deret Fibonacci.

• Setiap baris sesuai dengan koefisien dalam ekspansi (a+b)ⁿ.
• Jika Anda hanya mengarsir angka-angka ganjil, maka gambar yang dihasilkan akan membentuk fraktal segitiga Sierpinski.

Pertanyaan Umum Demo Slot