Pascal Üçgeni Formülü ve Örnekleri
Sarah Chen
⚡ Akıllı Özet
Pascal üçgeni, her değerin kendisinden hemen üstte bulunan iki sayının toplamına eşit olduğu üçgen bir sayı düzenlemesidir ve yüzyıllardır matematikçileri büyüleyen kombinatorik, binom açılımları ve olasılık alanlarındaki derin kalıpları ortaya koymaktadır.
Pascal Üçgeni Nedir?
Pascal Üçgeni, üstündeki satıra göre basit bir örüntüyü izleyen üçgen şeklinde bir sayı dizisidir. 17. yüzyılda Fransız matematikçi Blaise Pascal tarafından popülerleştirilmiştir. Üçgen, en üstte tek bir "1" ile başlar ve sonraki her satır da "1" ile başlar ve biter.
Zarif şeklinin ötesinde, Pascal üçgeni derin matematiksel ilişkileri barındırır. Binom teoremi, kombinatoryal sayma ve olasılıkla yakından bağlantılıdır; bu nedenle dünya çapında cebir, istatistik ve bilgisayar bilimleri dersliklerinde yer alır.
Pascal Üçgeninin Tarihi
Adını Blaise Pascal'dan almasına rağmen, üçgen ondan yüzyıllar öncesine dayanmaktadır. Çin matematik metni "Matematik Sanatı Üzerine Dokuz Bölüm", günümüzde kullandığımız birçok deseni sergileyen bilinen en eski örneklerden birini içermektedir.
İranlı matematikçi El-Karaji ve Hintli bilgin PingAla da benzer dizilimleri inceledi. Pascal, üçgenin özelliklerini 1654 tarihli "Traité du triangle arithmétique" adlı incelemesinde resmileştirdi ve bu da yapıya Batı matematiğindeki modern adını kazandırdı.
Pascal Üçgeninin İnşaatı
Pascal üçgenini oluşturmak oldukça basittir. Hatırlanması gereken tek kural, her satırın 1 ile başlayıp 1 ile bitmesi ve diğer tüm sayıların bir üst satırdaki sayıdan türetilmesidir.
Herhangi bir r satırı ve c sütunu için, değer, r-1 satırının c-1 ve c sütunlarındaki sayıların toplamına eşittir.
Burada,
- r = 3, 4, 5, …
- n ve c = 2, 3, 4, …, r-1.
İşte Pascal üçgenini oluşturmanın adımları:
) 1 Adım İlk iki satırı doldurarak başlayın.
) 2 Adım Üçüncü satırın ikinci elemanı, ikinci satırdaki birinci ve ikinci sayıların toplamıdır.
) 3 Adım Dördüncü satır "1" ile başlıyor. İkinci sayı 3'tür ve bu, 1 ve 2'nin toplamıdır (mavi renkle vurgulanmıştır).
Aşağıdaki görselde dördüncü satırın nasıl doldurulacağı gösterilmektedir:
) 4 Adım Beşinci satır beş sayıdan oluşmaktadır. Satırları doldurma modelini önceki adımlardan zaten biliyoruz.
Pascal Üçgen Formülü – Binom Katsayısı
Binom katsayısı, n elemanlı bir kümeden k elemanlı bir alt küme seçmenin kaç farklı yolu olduğunu sayar. Genellikle “C(n, k)” veya “n'nin k'lı kombinasyonu” şeklinde yazılır.
Binom katsayısı şu şekilde tanımlanır:
"!" sembolü bir sayının faktöriyelini gösterir.
n! = n.(n-1).(n-2)…3.2.1
Örneğin,
5! = 5.4.3.2.1
= 120
Yani, C(5, 3) veya “5’in 3’lü kombinasyonu” = 5! / 3!(5-3)!
= 120/12
= 10
Yöntem 1: Önceki Satırdan Pascal Üçgenini Oluşturma
Buradaki işlem, üçgeni elle nasıl çizdiğimize benzer. Diyelim ki Pascal üçgenini yedi satıra kadar oluşturmak istiyoruz.
Bunu yapmak için adımlar aşağıdaki gibidir:
) 1 Adım En üst satırı “1” ile başlatın.
) 2 Adım “r” satırı için, “c” elemanı, “r-1” sütunu ile “r-1” satırının “c” sütununun toplamı olacaktır.
) 3 Adım Her satırdaki ilk ve son rakamlar her zaman "1" olacaktır.
Bu üç basit adımı izleyerek üçgenin tamamını sistematik bir şekilde oluşturabiliriz.
C++ Code Önceki Satıra Göre Pascal Üçgeninin
#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); }
Çıktı:
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 Önceki Satıra Göre Pascal Üçgeni Formülü
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)
Pascal Üçgeni Örnek Çıktısı:
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
Karmaşıklık Analizi
A iki boyutlu dizi Bu uygulamada kullanılır. Pascal üçgenindeki satır sayısı N olduğuna göre, bu N gerektirir.2 birim uzaylar. Bu nedenle, uzay karmaşıklığı O(N)'dir.2).
Bu fonksiyon, her biri "N" defaya kadar çalışan iki iç içe döngü kullanır. Dolayısıyla, zaman karmaşıklığı da şöyledir: O (N2)veya karesel zaman karmaşıklığı.
Yöntem 2: Binom Katsayısını Hesaplayarak Pascal Üçgenini Oluşturma
Pascal üçgeninin sayılarını binom katsayılarını kullanarak doğrudan elde edebiliriz. Aşağıdaki diyagram bu ilişkiyi göstermektedir:
İşte binom katsayısını hesaplayarak Pascal üçgenini oluşturmanın adımları:
) 1 Adım En üstteki satır C(0, 0)'dır. Yukarıdaki formülü kullanarak, 0! = 1 olduğundan C(0, 0) = 1'dir.
) 2 Adım “i” numaralı satır için toplamda “i” eleman olacaktır. Her bir eleman C(n, r) olarak hesaplanır; burada n, i-1'dir.
) 3 Adım İstediğiniz kadar Pascal üçgeni satırı oluşturmak için 2. adımı tekrarlayın.
C++ Code Binom Katsayısıyla Pascal Üçgeni
#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); }
Çıktı:
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 Binom Katsayısıyla Pascal Üçgeni
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)
Pascal Üçgeni Örnek Çıktısı:
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
Karmaşıklık Analizi
Bu uygulamada üç döngü kullanılır: biri binom katsayısını hesaplamak için, diğer ikisi ise her satır ve sütunu yinelemek için. Satır sayısına bağlı olarak, üç döngünün tamamı "n" defaya kadar çalışır. Sonuç olarak, genel zaman karmaşıklığı O(n)'dir.3).
Ara sonuçları saklamadığımız için alan karmaşıklığı sabittir. Program her bir elemanı anında hesaplar ve bir satır içinde yazdırır, bu nedenle alan karmaşıklığı azalır. O (1).
Yöntem 3: Değiştirilmiş Binom Katsayısı ile Pascal Üçgenini Oluşturma
Önceki teknikte, her bir elemanı hesaplamak için binom katsayısı formülünü kullandık. Değiştirilmiş yaklaşım, C(n, r)'yi doğrudan C(n, r-1)'den türeterek iş yükünü bir mertebe azaltır.
İşte değiştirilmiş binom katsayısı kullanılarak Pascal üçgeninin oluşturulmasına ilişkin adımlar:
) 1 Adım İlk satırı “1” ile başlatın.
) 2 Adım “n” satır numarası ve “r” sütun indeksi olmak üzere C(n, r) değerini hesaplayın. Bu değeri C değişkenine atayın.
) 3 Adım Sonraki katsayıyı hesaplamak için C * (n – k) / k ifadesini kullanın. Bu yeni değeri tekrar C'ye atayın.
) 4 Adım “k” satırın sonuna ulaşana kadar 3. adımı tekrarlayın. Her yinelemeden sonra k'yı bir artırın.
C++ Code Pascal Üçgeni için Değiştirilmiş Binom Katsayısı
#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); }
Çıktı:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code Pascal Üçgeni için Değiştirilmiş Binom Katsayısı
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'ın Üçgen Desenleri Çıktısı:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Karmaşıklık Analizi
Uygulama, her biri en fazla "n" kez çalışan iki döngü kullanır; burada "n", üçgendeki satır sayısıdır. Dolayısıyla, zaman karmaşıklığı şöyledir: O (n2), zamanın karesi.
Alan karmaşıklığı açısından, depolama için herhangi bir diziye ihtiyacımız yok. Önceki binom katsayısını saklamak için yalnızca bir değişken kullanıyoruz, bu nedenle sadece bir ek alana ihtiyacımız var. Bu nedenle alan karmaşıklığı şu şekildedir: O (1).
Pascal Üçgeninin Uygulanması
İşte Pascal üçgeninin bazı pratik uygulamaları:
Binom Genişlemeleri: Herhangi bir binom açılımının katsayıları doğrudan Pascal üçgeninden okunabilir. İşte bir örnek:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2ve + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3ve + 6x2y2 + 4xy3 + 1y4 |
Kombinasyonların Hesaplanması: Pascal üçgeninin elemanları doğrudan binom katsayılarına karşılık gelir. Örneğin, 6 topunuz varsa ve 3 tanesini seçmek istiyorsanız, cevap şudur: 6C3Bu değeri Pascal üçgeninin 6. satırının 3. elemanında bulabilirsiniz.
Olasılık: Pascal üçgeni, madeni para atışlarında, zar problemlerinde ve her sonucun bir binom dağılımına karşılık geldiği diğer kombinasyonel olaylarda olasılıkları hesaplamak için yaygın olarak kullanılır.
Pascal Üçgeni Hakkında İlginç Gerçekler
Pascal üçgeni hakkında ilginç bulacağınız bazı gerçekler:
- Herhangi bir satırdaki tüm elemanların toplamı her zaman 2'nin bir kuvvetidir.
- Satırların çapraz toplamları Fibonacci dizisini oluşturur.
- Her satır, (a+b) açılımındaki katsayılara karşılık gelir.n.
- Sadece tek sayıları tararsanız, ortaya çıkan şekil Sierpinski üçgeni fraktalını oluşturur.
