Wzór trójkąta Pascala z przykładami
Sara Chen
⚡ Inteligentne podsumowanie
Trójkąt Pascala to trójkątny układ liczb, w którym każda wartość jest równa sumie dwóch liczb znajdujących się bezpośrednio nad nią. Ujawnia on głębokie wzorce w kombinatoryce, rozwinięciach dwumianowych i rachunku prawdopodobieństwa, które od wieków fascynują matematyków.
Co to jest Trójkąt Pascala?
Trójkąt Pascala to trójkątny układ liczb, który podąża za prostym wzorem opartym na wierszu powyżej. Został spopularyzowany przez francuskiego matematyka Blaise'a Pascala w XVII wieku. Trójkąt zaczyna się od pojedynczej „1” na górze, a każdy kolejny wiersz również zaczyna się i kończy cyfrą „1”.
Poza eleganckim kształtem, trójkąt Pascala kryje w sobie głębokie zależności matematyczne. Jest ściśle powiązany z twierdzeniem dwumianowym, liczeniem kombinatorycznym i prawdopodobieństwem, dlatego pojawia się na lekcjach algebry, statystyki i informatyki na całym świecie.
Historia trójkąta Pascala
Choć nazwany na cześć Blaise'a Pascala, trójkąt ten jest starszy od niego o wieki. Chiński tekst matematyczny „Dziewięć rozdziałów o sztuce matematycznej” zawiera jeden z najwcześniejszych znanych przykładów, ukazując wiele tych samych wzorów, z których korzystamy dzisiaj.
Perski matematyk Al-Karaji i indyjski uczony PingAla również badał podobne układy. Pascal sformalizował własności trójkąta w swoim traktacie z 1654 roku „Traité du triangle arithmétique”, który nadał tej strukturze współczesną nazwę w matematyce zachodniej.
Konstrukcja Trójkąta Pascala
Konstrukcja trójkąta Pascala jest prosta. Jedyną zasadą, o której należy pamiętać, jest to, że każdy wiersz zaczyna się i kończy cyfrą 1, a każda kolejna liczba jest budowana od wiersza powyżej.
Dla dowolnego wiersza r i kolumny c wartość jest równa sumie liczb w kolumnach c-1 i c wiersza r-1.
Tutaj,
- r = 3, 4, 5, …
- n i c = 2, 3, 4, …, r-1.
Oto kroki tworzenia trójkąta Pascala:
Krok 1) Zacznij od wypełnienia pierwszych dwóch rzędów.
Krok 2) Drugi element trzeciego wiersza jest sumą pierwszej i drugiej liczby w drugim wierszu.
Krok 3) Czwarty wiersz zaczyna się od „1”. Drugą liczbą jest 3, która jest sumą 1 i 2 (zaznaczona na niebiesko).
Poniższy obrazek pokazuje, jak wypełnić czwarty wiersz:
Krok 4) Piąty wiersz składa się z pięciu liczb. Znamy już schemat wypełniania wierszy z poprzednich kroków.
Wzór na trójkąt Pascala – współczynnik dwumianu
Współczynnik dwumianowy zlicza liczbę sposobów wyboru podzbioru k elementów ze zbioru n elementów. Jest on powszechnie zapisywany jako „C(n, k)” lub „n wybierz k”.
Współczynnik dwumianowy definiuje się jako:
Symbol „!” oznacza silnię liczby.
n! = n.(n-1).(n-2)…3.2.1
Na przykład,
5! = 5.4.3.2.1 XNUMX XNUMX
= 120
Zatem C(5, 3) lub „5 wybiera 3” = 5! / 3!(5-3)!
= 120 / 12
= 10
Metoda 1: Budowanie trójkąta Pascala na podstawie poprzedniego rzędu
Procedura tutaj odzwierciedla sposób, w jaki narysowaliśmy trójkąt ręcznie. Załóżmy, że chcemy wygenerować trójkąt Pascala o maksymalnie siedmiu wierszach.
Aby to zrobić, należy wykonać następujące kroki:
Krok 1) Rozpocznij najwyższy rząd od „1”.
Krok 2) W przypadku wiersza „r” element „c” będzie sumą kolumny „c-1” i kolumny „c” wiersza „r-1”.
Krok 3) Pierwsza i ostatnia liczba w każdym wierszu będzie zawsze wynosić „1”.
Postępując zgodnie z tymi trzema prostymi krokami, możemy systematycznie skonstruować cały trójkąt.
C++ Code trójkąta Pascala według poprzedniego rzędu
#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); }
Wyjście:
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 wzoru trójkąta Pascala według poprzedniego wiersza
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)
Przykładowy wynik trójkąta Pascala:
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
Analiza złożoności
A tablica dwuwymiarowa W tej implementacji użyto N. Biorąc pod uwagę, że N to liczba wierszy w trójkącie Pascala, wymaga to N2 przestrzenie jednostkowe. Dlatego złożoność przestrzenna wynosi O(N2).
Funkcja wykorzystuje dwie zagnieżdżone pętle, z których każda może wykonać do „N” razy. Zatem złożoność czasowa jest również NA2)lub kwadratowej złożoności czasowej.
Metoda 2: Budowanie trójkąta Pascala poprzez obliczenie współczynnika dwumianowego
Liczby trójkąta Pascala możemy wyznaczyć bezpośrednio, używając współczynników dwumianowych. Poniższy diagram ilustruje tę zależność:
Oto kroki pozwalające zbudować trójkąt Pascala poprzez obliczenie współczynnika dwumianowego:
Krok 1) Najwyższy wiersz to C(0, 0). Używając powyższego wzoru, C(0, 0) = 1, ponieważ 0! = 1.
Krok 2) W wierszu „i” będzie łącznie „i” elementów. Każdy element oblicza się jako C(n, r), gdzie n to i-1.
Krok 3) Powtórz krok 2 dla tylu wierszy trójkąta Pascala, ile chcesz wygenerować.
C++ Code Trójkąt Pascala według współczynnika dwumianowego
#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); }
Wyjście:
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 Trójkąt Pascala według współczynnika dwumianowego
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)
Przykładowy wynik trójkąta Pascala:
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
Analiza złożoności
W tej implementacji zastosowano trzy pętle: jedną do obliczenia współczynnika dwumianowego i dwie kolejne do iteracji po każdym wierszu i kolumnie. Biorąc pod uwagę liczbę wierszy, wszystkie trzy pętle działają do „n” razy. W związku z tym całkowita złożoność czasowa wynosi O(n).3).
Złożoność przestrzenna jest stała, ponieważ nie przechowujemy żadnych wyników pośrednich. Program oblicza każdy element na bieżąco i wyświetla go w wierszu, więc złożoność przestrzenna redukuje się do O (1).
Metoda 3: Budowanie trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianu
W poprzedniej technice do obliczenia każdego elementu wykorzystaliśmy wzór na współczynnik dwumianowy. Zmodyfikowane podejście wyprowadza C(n, r) bezpośrednio z C(n, r-1), zmniejszając pracę o rząd wielkości.
Oto kroki pozwalające zbudować trójkąt Pascala przy użyciu zmodyfikowanego współczynnika dwumianowego:
Krok 1) Rozpocznij pierwszy wiersz od „1”.
Krok 2) Oblicz C(n, r), gdzie „n” to numer wiersza, a „r” to indeks kolumny. Przypisz tę wartość zmiennej C.
Krok 3) Aby obliczyć kolejny współczynnik, użyj wzoru C * (n – k) / k. Przypisz tę nową wartość z powrotem do C.
Krok 4) Kontynuuj krok 3, aż „k” dojdzie do końca wiersza. Po każdej iteracji zwiększaj k o jeden.
C++ Code dla trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianowego
#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); }
Wyjście:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code dla trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianowego
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)
Dane wyjściowe wzorów trójkątów Pascala:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analiza złożoności
Implementacja wykorzystuje dwie pętle, z których każda wykonuje się maksymalnie „n” razy, gdzie „n” to liczba wierszy w trójkącie. Zatem złożoność czasowa wynosi Na2), czas do kwadratu.
Jeśli chodzi o złożoność przestrzenną, nie potrzebujemy żadnej tablicy do przechowywania. Używamy tylko jednej zmiennej, aby zachować poprzedni współczynnik dwumianowy, więc potrzebujemy tylko jednej dodatkowej przestrzeni. Złożoność przestrzenna wynosi zatem O (1).
Zastosowanie trójkąta Pascala
Oto kilka praktycznych zastosowań trójkąta Pascala:
Rozszerzenia dwumianowe: Współczynniki dowolnego rozwinięcia dwumianowego można odczytać bezpośrednio z trójkąta Pascala. Oto przykład:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2i + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3i + 6x2y2 + 4xy3 + 1y4 |
Obliczanie kombinacji: Elementy trójkąta Pascala odpowiadają bezpośrednio współczynnikom dwumianowym. Na przykład, jeśli masz 6 piłek i chcesz wybrać 3, odpowiedź brzmi: 6C3Wartość tę można znaleźć w trzecim elemencie szóstego wiersza trójkąta Pascala.
Prawdopodobieństwo: Trójkąt Pascala jest powszechnie stosowany do obliczania prawdopodobieństw w rzutach monetą, zadaniach z kostką i innych zdarzeniach kombinatorycznych, w których każdy wynik odpowiada rozkładowi dwumianowemu.
Interesujące fakty na temat trójkąta Pascala
Oto kilka interesujących faktów na temat trójkąta Pascala:
- Suma wszystkich elementów w dowolnym wierszu jest zawsze potęgą liczby 2.
- Sumy przekątnych wierszy generują ciąg Fibonacciego.
- Każdy wiersz odpowiada współczynnikom w rozwinięciu (a+b)n.
- Jeżeli zacieniujesz tylko liczby nieparzyste, otrzymana figura utworzy fraktal trójkąta Sierpińskiego.
