Pascals trekant – formel, mønstre og eksempler
Sarah Chen
Hva er Pascals trekant?
Pascals trekant er en trekantet rekke tall etterfulgt av et bestemt mønster og forbindelse til raden før den. Den ble oppfunnet av Blaise Pascal. Denne trekanten starter med ett element i den første raden. Etter det starter og slutter hver rad med "1".
Pascals trekanthistorie
Den kinesiske boken "The Nine Chapters on the Mathematical Art" inneholder et av de første eksemplene på Pascals trekant. I tillegg inneholder den noen av de samme mønstrene og egenskapene som finnes i trekanter i dag.
Pascal var en av flere personer i Europa som studerte trekanten. Andre matematikere hadde undersøkt lignende trekantede tallserier før ham.
Konstruksjon av Pascals trekant
Det er enkelt å konstruere Pascals trekant. Det eneste du trenger å huske er at raden starter og slutter med 1. Regelen for resten av tallene er som følger:
For enhver rad r og kolonne c vil tallet være summen av kolonnene c-1 og c fra rad r-1.
Her
- r = 3,4,5….
- n og c = 2,3,4,…r-1.
Her er trinnene for å bygge Pascals trekant:
Trinn 1) La oss begynne med å fylle opp to rader.
Trinn 2) Det andre elementet for den tredje linjen 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 vil bestå av fem tall. Vi kjenner allerede mønsteret for å fylle radene fra de tidligere trinnene.
Pascals trekantformel – binomial koeffisient
En binomial koeffisient er et tall som uttrykker forskjellige metoder for å velge en delmengde av k elementer fra en samling av n elementer. Ofte skrives det som "C(n,k)" eller "n velg k."
Den binomiale koeffisienten er definert som
"!" betegner "faktoren".
n! = n.(n-1). (n-2)...3.2.1
For eksempel,
5! = 5.4.3.2.1
= 120
Så, la oss si C(5,3) eller 5 velg 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metode 1: Bygg Pascals trekant etter forrige rad
Trinnene i denne prosedyren er de samme som i Pascals trekant. La oss si at vi vil lage Pascals trekant opp til syv rader.
Trinnene for å oppnå dette er som følger:
Trinn 1) Start den øverste raden med "1".
Trinn 2) For raden «r» vil «c»-elementet være produktet av «c-1» og «c» nummeret på «r-1»-raden.
Trinn 3) Det første og siste tallet på rad vil alltid være «1».
Vi må følge disse tre enkle trinnene for å lage Pascals trekant.
C++ Kode for Pascals trekant etter 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 Kode for Pascal Triangle Formula etter 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 ble brukt i implementeringen. Gitt at N er antall rader i Pascals trekant. Dette vil kreve N2 enhetsplasser. Derfor vil O være romkompleksiteten (N2).
Vi har to sløyfer i funksjonen, og hver sløyfe går "N" ganger. Så tidskompleksiteten er også PÅ2) eller kvadratisk tidskompleksitet.
Metode 2: Bygg Pascals trekant ved å beregne binomial koeffisient
Vi kan ganske enkelt utlede tallene til pascals trekant ved å bruke den binomiale koeffisienten. Her er diagrammet:
Her er trinnene for å bygge Pascals trekant ved å beregne binomialet:
Trinn 1) Den øverste raden vil være C(0,0). Ved å bruke formelen ovenfor for binomial koeffisient, C(0,0) = 1. Fordi 0! = 1.
Trinn 2) For rad "i" vil det være totalt "i"-elementer. Hvert element vil bli beregnet C(n,r) hvor n vil være i-1.
Trinn 3) Gjenta trinn 2 for antall rader du ønsker for pascals trekant.
C++ Kode Pascals trekant av binomial koeffisient
#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 Kode Pascals trekant av binomial koeffisient
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 ble brukt i implementeringen. En løkke er for å beregne binomial koeffisient, og de to andre er for å lage tall for alle rader. Når det gjelder antall rader, har vi tre løkker som utfører "n" ganger. Følgelig vil den totale tidskompleksiteten være 0(n3).
Plasskompleksiteten er nå konstant fordi vi ikke lagrer noen data. Programmet beregner elementet, og det skrives ut på rad. Romkompleksiteten avtar da til 0(1).
Metode 3: Bygg Pascals trekant med modifisert binomial koeffisient
I den forrige teknikken har vi allerede sett hvordan man bruker en binomial koeffisient for å beregne hvert element i Pascals trekant. Denne tilnærmingen vil bestemme C(n,r) fra C. (n, r-1). Det vil forenkle ting med én ordre.
Her er trinnene for å bygge Pascal's Triangle by Modified Binomial Coefficient:
Trinn 1) Start den første raden med "1"
Trinn 2) Beregn C(n,r), der "n" er radnummeret og "r" er kolonnen eller elementet. Tilordne verdien i en variabel C.
Trinn 3) For å beregne C(n,k), vil det være C*(nk)/k. Nå, tilordne denne verdien til C.
Trinn 4) Fortsett trinn 3 til "k" når slutten av raden. Etter hver iterasjon øker du verdien av K med én.
C++ Kode for Pascals trekant av modifisert binomial koeffisient
#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 kode for Pascals trekant av modifisert binomial koeffisient
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 har to løkker. Hver sløyfe kjører maksimalt "n" tid, der "n" betyr antall rader i pascaltrekanten. Så tidskompleksiteten er På2), kvadratisk tid.
Når det gjelder plasskompleksitet, trengte vi ingen matrise å lagre. Vi brukte bare én variabel for å beholde den forrige binomiale koeffisienten. Så vi trengte bare en ekstra plass. Romkompleksiteten ble O (1).
Anvendelse av Pascals trekant
Her er noen bruksområder for Pascals trekant:
Binomiale utvidelser: Vi kan bestemme koeffisienten til de binomiale utvidelsene 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: Vi har sett at elementer i Pascals trekant tilsvarer binomiale koeffisienter. For eksempel, hvis du har 6 baller og har blitt bedt om å velge 3 baller, blir det det 6C3. Eller du kan finne tallet i det tredje elementet i den sjette raden fra pascals trekant.
Interessante fakta om Pascals trekant
Her er noen fakta du vil finne interessant om Pascals trekant:
- Summen av alle elementene på rad er alltid potensen til 2.
- Diagonalt genererer summen av elementene i radene Fibonacci-sekvensen.
Sammendrag
- Pascals trekant gir koeffisientene for de binomiale utvidelsene.
- Hver rad i pascals trekant starter og slutter med "1". De mellomliggende verdiene er summen av to elementer i den forrige raden.
- Diagonal tillegg av alle elementene i pascals trekant vil gi deg Fibonacci sekvens.
- Pascals trekant kan også genereres med binomiale koeffisienter.
