Τρίγωνο του Πασκάλ – Τύπος, Μοτίβα & Παραδείγματα
Σάρα Τσεν
Τι είναι το Τρίγωνο του Πασκάλ;
Το τρίγωνο του Πασκάλ είναι ένας τριγωνικός πίνακας αριθμών που ακολουθείται από ένα συγκεκριμένο μοτίβο και σύνδεση με τη σειρά πριν από αυτό. Εφευρέθηκε από τον Blaise Pascal. Αυτό το τρίγωνο ξεκινά με ένα στοιχείο στην πρώτη σειρά. Μετά από αυτό, κάθε σειρά αρχίζει και τελειώνει με "1".
Η ιστορία του τριγώνου του Πασκάλ
Το κινέζικο βιβλίο «Τα εννέα Κεφάλαια για τη Μαθηματική Τέχνη» περιέχει ένα από τα πρώτα παραδείγματα του Τριγώνου του Πασκάλ. Επιπλέον, περιέχει μερικά από τα ίδια μοτίβα και ιδιότητες που συναντάμε στα τρίγωνα σήμερα.
Ο Πασκάλ ήταν ένας από τους πολλούς ανθρώπους στην Ευρώπη που μελέτησαν το τρίγωνο. Άλλοι μαθηματικοί είχαν εξετάσει παρόμοιους τριγωνικούς πίνακες αριθμών πριν από αυτόν.
Κατασκευή του Τριγώνου του Πασκάλ
Η κατασκευή του τριγώνου του Pascal είναι απλή. Το μόνο πράγμα που πρέπει να θυμάστε είναι ότι η σειρά αρχίζει και τελειώνει με 1. Ο κανόνας για τους υπόλοιπους αριθμούς είναι ο εξής:
Για οποιαδήποτε σειρά r και στήλη c, ο αριθμός θα είναι το άθροισμα των στηλών c-1 και c από τη σειρά r-1.
Εδώ,
- r = 3,4,5….
- n και c = 2,3,4,…r-1.
Ακολουθούν τα βήματα για τη δημιουργία του τριγώνου του Pascal:
Βήμα 1) Ας ξεκινήσουμε συμπληρώνοντας δύο σειρές.
Βήμα 2) Το δεύτερο στοιχείο για την τρίτη γραμμή είναι το άθροισμα του πρώτου και του δεύτερου αριθμού στη δεύτερη σειρά.
Βήμα 3) Η τέταρτη σειρά θα ξεκινά με «1.». Ο δεύτερος αριθμός είναι το 3, που είναι το άθροισμα του 1 και του 2 (επισημαίνεται με μπλε χρώμα).
Η παρακάτω εικόνα δείχνει πώς να γεμίσετε την τέταρτη σειρά:
Βήμα 4) Η πέμπτη σειρά θα αποτελείται από πέντε αριθμούς. Γνωρίζουμε ήδη το μοτίβο για τη συμπλήρωση των σειρών από τα προηγούμενα βήματα.
Τύπος τριγώνου του Pascal – Διωνυμικός συντελεστής
Ένας διωνυμικός συντελεστής είναι ένας αριθμός που εκφράζει διαφορετικές μεθόδους για την επιλογή ενός υποσυνόλου k στοιχείων από μια συλλογή n στοιχείων. Συχνά, γράφεται ως "C(n,k)" ή "n επιλέξτε k."
Ο διωνυμικός συντελεστής ορίζεται ως
Ο "!" υποδηλώνει το «παραγοντικό».
n! = n.(n-1). (n-2)…3.2.1
Για παράδειγμα,
5! = 5.4.3.2.1
= 120
Έτσι, ας πούμε C(5,3) ή 5 επιλέξτε 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Μέθοδος 1: Δημιουργία του τριγώνου του Pascal με την προηγούμενη σειρά
Τα βήματα σε αυτή τη διαδικασία είναι τα ίδια με αυτά στο τρίγωνο του Pascal. Ας υποθέσουμε ότι θέλουμε να δημιουργήσουμε το τρίγωνο του Pascal έως και επτά σειρές.
Τα βήματα για να το πετύχετε είναι τα εξής:
Βήμα 1) Ξεκινήστε την επάνω σειρά με "1".
Βήμα 2) Για τη σειρά "r", το στοιχείο "c" θα είναι το γινόμενο του "c-1" και το "c" ο αριθμός της σειράς "r-1".
Βήμα 3) Ο πρώτος και ο τελευταίος αριθμός στη σειρά θα είναι πάντα "1".
Πρέπει να ακολουθήσουμε αυτά τα τρία εύκολα βήματα για να δημιουργήσουμε το τρίγωνο του Pascal.
C++ Κωδικός του Τριγώνου του Πασκάλ από την προηγούμενη σειρά
#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);
}
Παραγωγή:
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 Κωδικός τύπου Pascal Triangle Formula από την προηγούμενη σειρά
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:
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
Ανάλυση πολυπλοκότητας
A δισδιάστατος πίνακας χρησιμοποιήθηκε στην υλοποίηση. Δεδομένου ότι N είναι ο αριθμός των σειρών στο τρίγωνο του Pascal. Αυτό θα απαιτήσει Ν2 χώρους μονάδας. Επομένως, Ο θα είναι η πολυπλοκότητα του χώρου (Ν2).
Έχουμε δύο βρόχους στη συνάρτηση και κάθε βρόχος εκτελείται για "N" φορές. Άρα, η χρονική πολυπλοκότητα είναι επίσης ΕΠΙ2) ή τετραγωνική χρονική πολυπλοκότητα.
Μέθοδος 2: Δόμηση του τριγώνου του Pascal με υπολογισμό του διωνυμικού συντελεστή
Μπορούμε απλά να εξαγάγουμε τους αριθμούς του τριγώνου του Πασκάλ χρησιμοποιώντας τον διωνυμικό συντελεστή. Εδώ είναι το διάγραμμα:
Ακολουθούν τα βήματα για να δημιουργήσετε το Τρίγωνο του Pascal υπολογίζοντας το Διώνυμο:
Βήμα 1) Η ανώτερη σειρά θα είναι C(0,0). Χρησιμοποιώντας τον παραπάνω τύπο για τον Διωνυμικό Συντελεστή, C(0,0) = 1. Επειδή 0! = 1.
Βήμα 2) Για τη σειρά "i", θα υπάρχουν συνολικά στοιχεία "i". Κάθε στοιχείο θα υπολογιστεί C(n,r) όπου n θα είναι i-1.
Βήμα 3) Επαναλάβετε το βήμα 2 για τον αριθμό των σειρών που θέλετε για το τρίγωνο του Pascal.
C++ Κωδικός Τρίγωνο του Πασκάλ με Διωνυμικό Συντελεστή
#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);
}
Παραγωγή:
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 Κωδικός Τρίγωνο του Πασκάλ με Διωνυμικό Συντελεστή
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:
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
Ανάλυση πολυπλοκότητας
Στην υλοποίηση χρησιμοποιήθηκαν τρεις βρόχοι. Ο ένας βρόχος είναι για τον υπολογισμό του Διωνυμικού συντελεστή και οι άλλοι δύο είναι για τη δημιουργία αριθμών για όλες τις σειρές. Όσον αφορά τον αριθμό των σειρών, έχουμε τρεις βρόχους που εκτελούν "n" φορές. Συνεπώς, η συνολική χρονική πολυπλοκότητα θα είναι 0(n3).
Η πολυπλοκότητα του χώρου είναι πλέον σταθερή επειδή δεν διατηρούμε δεδομένα στην αποθήκευση. Το πρόγραμμα υπολογίζει το στοιχείο και εκτυπώνεται σε μια σειρά. Η πολυπλοκότητα του χώρου στη συνέχεια μειώνεται στο 0(1).
Μέθοδος 3: Δόμηση του τριγώνου του Pascal με τροποποιημένο διωνυμικό συντελεστή
Στην προηγούμενη τεχνική, έχουμε ήδη δει πώς να χρησιμοποιήσουμε έναν διωνυμικό συντελεστή για να υπολογίσουμε κάθε στοιχείο του τριγώνου του Pascal. Αυτή η προσέγγιση θα καθορίσει το C(n,r) από το C. (n, r-1). Θα απλοποιήσει τα πράγματα κατά μία σειρά.
Εδώ, είναι τα βήματα για τη δημιουργία του Τριγώνου του Pascal με Τροποποιημένο Διωνυμικό Συντελεστή:
Βήμα 1) Ξεκινήστε την πρώτη σειρά με "1"
Βήμα 2) Υπολογίστε το C(n,r), όπου "n" είναι ο αριθμός της σειράς και "r" είναι η στήλη ή το στοιχείο. Εκχωρήστε την τιμή σε μια μεταβλητή C.
Βήμα 3) Για τον υπολογισμό του C(n,k), θα είναι C*(nk)/k. Τώρα, αντιστοιχίστε αυτήν την τιμή στο C.
Βήμα 4) Συνεχίστε το βήμα 3 μέχρι το "k" να φτάσει στο τέλος της σειράς. Μετά από κάθε επανάληψη, αυξήστε την τιμή του K κατά ένα.
C++ Κωδικός για το τρίγωνο του Pascal με τροποποιημένο διωνυμικό συντελεστή
#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);
}
Παραγωγή:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python κωδικός για το τρίγωνο του Pascal με τροποποιημένο διωνυμικό συντελεστή
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:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Ανάλυση πολυπλοκότητας
Η υλοποίηση έχει δύο βρόχους. Κάθε βρόχος εκτελεί το μέγιστο χρόνο "n", όπου το "n" σημαίνει τον αριθμό των σειρών στο τρίγωνο pascal. Άρα, η χρονική πολυπλοκότητα είναι Επί2), στο τετράγωνο του χρόνου.
Όσον αφορά την πολυπλοκότητα του χώρου, δεν χρειαζόμασταν καμία συστοιχία για αποθήκευση. Απλώς χρησιμοποιήσαμε μια μεταβλητή για να διατηρήσουμε τον προηγούμενο διωνυμικό συντελεστή. Έτσι, χρειαζόμασταν μόνο έναν επιπλέον χώρο. Η διαστημική πολυπλοκότητα έγινε Ο (1).
Εφαρμογή του Τριγώνου του Πασκάλ
Ακολουθούν ορισμένες εφαρμογές του Τριγώνου του Πασκάλ:
Διωνυμικές επεκτάσεις: Μπορούμε να προσδιορίσουμε τον συντελεστή των διωνυμικών επεκτάσεων από το τρίγωνο του Πασκάλ. Εδώ είναι ένα παράδειγμα:
| (x + ε)0 | 1 |
| (x + ε)1 | 1.x + 1.y |
| (x + ε)2 | 1x2 + 2xy + 1y2 |
| (x + ε)3 | 1x3 + 3x2και + 3xy2 + 1y3 |
| (x + ε)4 | 1x4 + 4x3και + 6x2y2 + 4xy3 + 1y4 |
Υπολογισμός συνδυασμών: Είδαμε ότι στοιχεία του τριγώνου του Πασκάλ είναι ισοδύναμα με διωνυμικούς συντελεστές. Για παράδειγμα, αν έχετε 6 μπάλες και σας ζητήθηκε να επιλέξετε 3 μπάλες, θα είναι 6C3. Ή, μπορείτε να βρείτε τον αριθμό στο 3ο στοιχείο της 6ης σειράς από το τρίγωνο του Πασκάλ.
Ενδιαφέροντα γεγονότα για το Τρίγωνο του Πασκάλ
Εδώ είναι μερικά στοιχεία που θα βρείτε ενδιαφέροντα για το τρίγωνο του Πασκάλ:
- Το άθροισμα όλων των στοιχείων σε μια σειρά είναι πάντα η ισχύς του 2.
- Το διαγώνιο άθροισμα των στοιχείων των σειρών δημιουργεί την ακολουθία Fibonacci.
Σύνοψη
- Το τρίγωνο του Πασκάλ δίνει τους συντελεστές για τις Διωνυμικές Διαστολές.
- Κάθε σειρά του τριγώνου του Πασκάλ αρχίζει και τελειώνει με «1». Οι ενδιάμεσες τιμές είναι το άθροισμα δύο στοιχείων της προηγούμενης σειράς.
- Η διαγώνια προσθήκη όλων των στοιχείων στο τρίγωνο του Πασκάλ θα σας δώσει το Ακολουθία Fibonacci.
- Το τρίγωνο του Pascal μπορεί επίσης να δημιουργηθεί με διωνυμικούς συντελεστές.
