Pascals trekantformel med eksempler
Sarah Chen
⚡ Smart oppsummering
Pascals trekant er en trekantet tallordning der hver verdi er lik summen av de to tallene rett over den, og avslører dype mønstre innen kombinatorikk, binomiale utvidelser og sannsynlighet som har fascinert matematikere i århundrer.
Hva er Pascals trekant?
Pascals trekant er en trekantet tallrekke som følger et enkelt mønster basert på raden over. Den ble popularisert av den franske matematikeren Blaise Pascal på 17-tallet. Trekanten begynner med en enkelt «1» øverst, og hver påfølgende rad starter og slutter også med «1».
Utover sin elegante form, koder Pascals trekant for dype matematiske sammenhenger. Den er nært knyttet til binomialsetningen, kombinatorisk telling og sannsynlighet, og det er derfor den dukker opp i algebra-, statistikk- og informatikkklasserom over hele verden.
Pascals trekanthistorie
Selv om trekanten er oppkalt etter Blaise Pascal, er den århundrer eldre enn ham. Den kinesiske matematiske teksten «De ni kapitlene om matematisk kunst» inneholder et av de tidligste kjente eksemplene, og viser mange av de samme mønstrene vi bruker i dag.
Persisk matematiker Al-Karaji og indisk lærd Pingala utforsket også lignende matriser. Pascal formaliserte trekantens egenskaper i sin avhandling fra 1654 «Traité du triangle arithmétique», som ga strukturen sitt moderne navn i vestlig matematikk.
Konstruksjon av Pascals trekant
Det er enkelt å konstruere Pascals trekant. Den eneste regelen man må huske er at hver rad starter og slutter med 1, og alle andre tall bygges fra raden over.
For enhver rad r og kolonne c er verdien lik summen av tallene i kolonne c-1 og c i rad r-1.
Her
- r = 3, 4, 5, …
- n og c = 2, 3, 4, …, r⁻¹.
Her er trinnene for å bygge Pascals trekant:
Trinn 1) Begynn med å fylle ut de to første radene.
Trinn 2) Det andre elementet i den tredje raden er summen av det første og andre tallet i den andre raden.
Trinn 3) Den fjerde raden begynner med «1». Det andre tallet er 3, som er summen av 1 og 2 (uthevet i blått).
Bildet nedenfor viser hvordan du fyller den fjerde raden:
Trinn 4) Den femte raden består av fem tall. Vi kjenner allerede mønsteret for å fylle ut rader fra de tidligere trinnene.
Pascals trekantformel – binomial koeffisient
En binomial koeffisient teller antall måter å velge et delsett av k elementer fra en samling av n elementer. Den skrives vanligvis som «C(n, k)» eller «n velger k».
Den binomiale koeffisienten er definert som:
Symbolet «!» angir fakulteten til et tall.
n! = n.(n-1).(n-2)…3.2.1
For eksempel,
5! = 5.4.3.2.1
= 120
Så, C(5, 3) eller «5 velg 3» = 5! / 3!(5-3)!
= 120/12
= 10
Metode 1: Bygge Pascals trekant ved hjelp av forrige rad
Fremgangsmåten her speiler hvordan vi tegnet trekanten manuelt. Anta at vi vil generere Pascals trekant med opptil syv rader.
Fremgangsmåten for å gjøre det er som følger:
Trinn 1) Start den øverste raden med «1».
Trinn 2) For rad «r» vil elementet «c» være summen av kolonne «c-1» og kolonne «c» i rad «r-1».
Trinn 3) Det første og siste tallet i hver rad vil alltid være «1».
Ved å følge disse tre enkle trinnene kan vi systematisk konstruere hele trekanten.
C++ Code av Pascals trekant ved forrige rad
#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); }
Utgang:
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 av Pascal-trekantformelen ved forrige rad
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)
Pascals trekanteksempel:
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
Kompleksitetsanalyse
A todimensjonal matrise brukes i denne implementeringen. Gitt at N er antall rader i Pascals trekant, krever dette N2 enhetsrom. Derfor er romkompleksiteten O(N2).
Funksjonen bruker to nestede løkker, som hver kjører opptil «N» ganger. Så tidskompleksiteten er også PÅ2), eller kvadrert tidskompleksitet.
Metode 2: Bygge Pascals trekant ved å beregne binomialkoeffisienten
Vi kan utlede tallene i Pascals trekant direkte ved hjelp av binomiale koeffisienter. Diagrammet nedenfor illustrerer forholdet:
Her er trinnene for å bygge Pascals trekant ved å beregne binomialkoeffisienten:
Trinn 1) Den øverste raden er C(0, 0). Ved å bruke formelen ovenfor er C(0, 0) = 1, fordi 0! = 1.
Trinn 2) For rad «i» vil det være totalt «i»-elementer. Hvert element beregnes som C(n, r), der n er i-1.
Trinn 3) Gjenta trinn 2 for så mange rader av Pascals trekant som du vil generere.
C++ Code Pascals trekant ved hjelp av binomialkoeffisient
#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); }
Utgang:
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 Pascals trekant ved hjelp av binomialkoeffisient
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)
Pascals trekanteksempel:
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
Kompleksitetsanalyse
Tre løkker brukes i denne implementeringen: én for å beregne binomialkoeffisienten og to til for å iterere gjennom hver rad og kolonne. Med hensyn til antall rader, kjører alle tre løkkene opptil «n» ganger. Følgelig er den totale tidskompleksiteten O(n3).
Romkompleksiteten er konstant fordi vi ikke lagrer noen mellomresultater. Programmet beregner hvert element underveis og skriver det ut i en rad, slik at romkompleksiteten reduseres til O (1).
Metode 3: Bygg Pascals trekant med modifisert binomial koeffisient
I den forrige teknikken brukte vi formelen for binomialkoeffisient for å beregne hvert element. Den modifiserte tilnærmingen utleder C(n, r) direkte fra C(n, r-1), noe som reduserer arbeidet med én størrelsesorden.
Her er trinnene for å bygge Pascals trekant med den modifiserte binomiale koeffisienten:
Trinn 1) Start den første raden med «1».
Trinn 2) Beregn C(n, r), der «n» er radnummeret og «r» er kolonneindeksen. Tilordne denne verdien til en variabel C.
Trinn 3) For å beregne den neste koeffisienten, bruk C * (n – k) / k. Tildel denne nye verdien tilbake til C.
Trinn 4) Fortsett trinn 3 til «k» når slutten av raden. Øk k med én etter hver iterasjon.
C++ Code for Pascals trekant med modifisert binomialkoeffisient
#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); }
Utgang:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code for Pascals trekant med modifisert binomialkoeffisient
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)
Pascals trekantmønsterutgang:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Kompleksitetsanalyse
Implementeringen bruker to løkker, som hver kjører maksimalt «n» ganger, hvor «n» er antall rader i trekanten. Så tidskompleksiteten er På2), kvadratisk tid.
Når det gjelder romkompleksitet, trenger vi ikke noen array for lagring. Vi bruker bare én variabel for å beholde den forrige binomiale koeffisienten, så vi trenger bare ett ekstra rom. Romkompleksiteten er derfor O (1).
Anvendelse av Pascals trekant
Her er noen praktiske anvendelser av Pascals trekant:
Binomiale utvidelser: Koeffisientene til enhver binomial utvidelse kan leses direkte fra Pascals trekant. Her er et eksempel:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2og + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3og + 6x2y2 + 4xy3 + 1y4 |
Beregne kombinasjoner: Elementene i Pascals trekant korresponderer direkte med binomiale koeffisienter. Hvis du for eksempel har 6 baller og vil velge 3, er svaret 6C3Du finner den verdien i det tredje elementet i den sjette raden i Pascals trekant.
Sannsynlighet: Pascals trekant er mye brukt til å beregne sannsynligheter i myntkast, terningproblemer og andre kombinatoriske hendelser der hvert utfall tilsvarer en binomialfordeling.
Interessante fakta om Pascals trekant
Her er noen fakta du vil finne interessant om Pascals trekant:
- Summen av alle elementene i en hvilken som helst rad er alltid en potens av 2.
- De diagonale summene av radene genererer Fibonacci-sekvensen.
- Hver rad tilsvarer koeffisientene i utvidelsen av (a+b)n.
- Hvis du bare skyggelegger oddetallene, danner den resulterende figuren Sierpinski-trekantfraktalen.
