Trójkąt Pascala – formuła, wzory i przykłady
Sara Chen
Co to jest Trójkąt Pascala?
Trójkąt Pascala to trójkątna tablica liczb, po której następuje określony wzór i połączenie z poprzednim wierszem. Został wynaleziony przez Blaise’a Pascala. Ten trójkąt zaczyna się od jednego elementu w pierwszym wierszu. Następnie każdy wiersz zaczyna się i kończy na „1”.
Historia trójkąta Pascala
Chińska książka „Dziewięć rozdziałów o sztuce matematycznej” zawiera jeden z pierwszych przykładów Trójkąta Pascala. Ponadto zawiera niektóre z tych samych wzorów i cech, które można znaleźć w dzisiejszych trójkątach.
Pascal był jedną z kilku osób w Europie, które badały trójkąt. Inni matematycy badali podobne trójkątne układy liczb przed nim.
Konstrukcja Trójkąta Pascala
Konstrukcja trójkąta Pascala jest prosta. Jedyne, o czym musisz pamiętać, to to, że wiersz zaczyna się i kończy na 1. Reguła dla pozostałych liczb jest następująca:
Dla dowolnego wiersza r i kolumny c liczba będzie sumą kolumn c-1 i c z wiersza r-1.
Tutaj,
- r = 3,4,5….
- n i c = 2,3,4,…r-1.
Oto kroki, jak zbudować Trójkąt Pascala:
Krok 1) Zacznijmy od wypełnienia dwóch wierszy.
Krok 2) Drugim elementem trzeciego wiersza jest suma pierwszej i drugiej liczby w drugim wierszu.
Krok 3) Czwarty rząd zacznie się od „1.”. Druga liczba to 3, która jest sumą 1 i 2 (podświetlona na niebiesko).
Poniższy obrazek pokazuje, jak wypełnić czwarty wiersz:
Krok 4) Piąty wiersz będzie składał się z pięciu liczb. Znamy już wzór wypełniania wierszy z poprzednich kroków.
Wzór na trójkąt Pascala – współczynnik dwumianu
Współczynnik dwumianowy to liczba wyrażająca różne metody wyboru podzbioru k elementów ze zbioru n elementów. Często zapisuje się go jako „C(n,k)” lub „n wybierz k”.
Współczynnik dwumianu definiuje się jako
„!” oznacza „silnię”.
N! = n. (n-1). (n-2)…3.2.1
Na przykład,
5! = 5.4.3.2.1 XNUMX XNUMX
= 120
Powiedzmy, że C(5,3) lub 5 wybierz 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metoda 1: Budowanie trójkąta Pascala na podstawie poprzedniego wiersza
Kroki tej procedury są takie same, jak w trójkącie Pascala. Powiedzmy, że chcemy utworzyć trójkąt Pascala składający się z maksymalnie siedmiu wierszy.
Kroki, aby to osiągnąć, są następujące:
Krok 1) Rozpocznij najwyższy rząd od „1”.
Krok 2) Dla wiersza „r” pozycja „c” będzie iloczynem „c-1”, a „c” numerem wiersza „r-1”.
Krok 3) Pierwsza i ostatnia liczba w rzędzie zawsze będzie wynosić „1”.
Musimy przestrzegać tych trzech prostych kroków, aby utworzyć trójkąt Pascala.
C++ Kod trójkąta Pascala według poprzedniego wiersza
#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 Kod 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 został wykorzystany w realizacji. Biorąc pod uwagę, że N jest liczbą wierszy w trójkącie Pascala. Będzie to wymagało N2 przestrzenie jednostkowe. Dlatego O będzie złożonością przestrzenną (N2).
Mamy dwie pętle w funkcji, a każda pętla działa przez „N” razy. Zatem złożoność czasowa jest również NA2) lub kwadratu złożoności czasowej.
Metoda 2: Budowanie trójkąta Pascala poprzez obliczenie współczynnika dwumianu
Możemy po prostu wyprowadzić liczby trójkąta Pascala, używając współczynnika dwumianowego. Oto diagram:
Oto kroki, jak zbudować Trójkąt Pascala poprzez obliczenie dwumianu:
Krok 1) Najwyższym wierszem będzie C(0,0). Korzystając z powyższego wzoru na współczynnik dwumianu, C(0,0) = 1. Ponieważ 0! = 1.
Krok 2) Dla wiersza „i” będą łącznie elementy „i”. Każdy element zostanie obliczony C(n,r), gdzie n będzie i-1.
Krok 3) Powtórz krok 2 dla liczby wierszy, które chcesz utworzyć w trójkącie Pascala.
C++ Zakoduj trójkąt Pascala za pomocą współczynnika dwumianu
#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 Zakoduj trójkąt Pascala za pomocą współczynnika dwumianu
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 implementacji zastosowano trzy pętle. Jedna pętla służy do obliczania współczynnika dwumianowego, a pozostałe dwie do tworzenia liczb dla wszystkich wierszy. Jeśli chodzi o liczbę wierszy, mamy trzy pętle, które wykonują się „n” razy. W konsekwencji całkowita złożoność czasowa wyniesie 0(n3).
Złożoność przestrzenna jest teraz stała, ponieważ nie przechowujemy żadnych danych w pamięci masowej. Program oblicza element i jest on drukowany w wierszu. Złożoność przestrzenna zmniejsza się następnie do 0(1).
Metoda 3: Budowanie trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianu
W poprzedniej technice widzieliśmy już, jak użyć współczynnika dwumianu do obliczenia każdego elementu trójkąta Pascala. Podejście to określi C(n,r) z C. (n, r-1). Uprości to sprawę o jedno zamówienie.
Oto kroki prowadzące do zbudowania Trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianu:
Krok 1) Zainicjuj pierwszy wiersz za pomocą „1”
Krok 2) Oblicz C(n,r), gdzie „n” to numer wiersza, a „r” to kolumna lub element. Przypisz wartość do zmiennej C.
Krok 3) Do obliczenia C(n,k) będzie to C*(nk)/k. Teraz przypisz tę wartość do C.
Krok 4) Kontynuuj krok 3, aż „k” dotrze do końca rzędu. Po każdej iteracji zwiększ wartość K o jeden.
C++ Kod trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianu
#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 kod Trójkąta Pascala za pomocą zmodyfikowanego współczynnika dwumianu
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 ma dwie pętle. Każda pętla działa maksymalnie „n” czasu, gdzie „n” oznacza liczbę wierszy w trójkącie Pascala. Zatem złożoność czasowa wynosi Na2), czas do kwadratu.
Jeśli chodzi o złożoność przestrzenną, nie potrzebowaliśmy żadnej tablicy do przechowywania. Użyliśmy tylko jednej zmiennej, aby zachować poprzedni współczynnik dwumianowy. Potrzebowaliśmy więc tylko jednej dodatkowej przestrzeni. Złożoność przestrzenna stała się O (1).
Zastosowanie trójkąta Pascala
Oto kilka zastosowań Trójkąta Pascala:
Rozszerzenia dwumianowe: Współczynnik rozwinięć dwumianowych możemy wyznaczyć 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: Widzieliśmy, że elementy trójkąta Pascala są równoważne współczynnikom dwumianowym. Na przykład, jeśli masz 6 piłek i zostałeś poproszony o wybranie 3 piłek, tak się stanie 6C3. Możesz też znaleźć liczbę w trzecim elemencie szóstego rzędu trójkąta Pascala.
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 rzędzie jest zawsze potęgą 2.
- Suma ukośna elementów wierszy generuje ciąg Fibonacciego.
Podsumowanie
- Trójkąt Pascala podaje współczynniki rozwinięć dwumianowych.
- Każdy rząd trójkąta Pascala zaczyna się i kończy na „1”. Wartości pośrednie są sumą dwóch elementów poprzedniego wiersza.
- Dodanie ukośne wszystkich elementów trójkąta Pascala da ci ciąg Fibonacciego.
- Trójkąt Pascala można również wygenerować za pomocą współczynników dwumianowych.
