Ο τύπος του τριγώνου του Pascal με παραδείγματα
Σάρα Τσεν
⚡ Έξυπνη Σύνοψη
Το Τρίγωνο του Πασκάλ είναι μια τριγωνική διάταξη αριθμών όπου κάθε τιμή ισούται με το άθροισμα των δύο αριθμών ακριβώς από πάνω της, αποκαλύπτοντας βαθιά μοτίβα στη συνδυαστική, τις διωνυμικές επεκτάσεις και τις πιθανότητες που έχουν γοητεύσει τους μαθηματικούς εδώ και αιώνες.
Τι είναι το Τρίγωνο του Πασκάλ;
Το Τρίγωνο του Πασκάλ είναι ένας τριγωνικός πίνακας αριθμών που ακολουθεί ένα απλό μοτίβο με βάση τη γραμμή από πάνω του. Διαδόθηκε από τον Γάλλο μαθηματικό Μπλεζ Πασκάλ τον 17ο αιώνα. Το τρίγωνο ξεκινά με ένα μόνο "1" στην κορυφή και κάθε επόμενη γραμμή ξεκινά και τελειώνει επίσης με "1".
Πέρα από το κομψό του σχήμα, το Τρίγωνο του Πασκάλ κωδικοποιεί βαθιές μαθηματικές σχέσεις. Είναι στενά συνδεδεμένο με το διωνυμικό θεώρημα, τη συνδυαστική αρίθμηση και την πιθανότητα, γι' αυτό και εμφανίζεται σε τάξεις άλγεβρας, στατιστικής και πληροφορικής παγκοσμίως.
Η ιστορία του τριγώνου του Πασκάλ
Αν και πήρε το όνομά του από τον Μπλεζ Πασκάλ, το τρίγωνο προηγείται αυτού κατά αιώνες. Το κινεζικό μαθηματικό κείμενο «Τα εννέα κεφάλαια για την μαθηματική τέχνη» περιέχει ένα από τα πρώτα γνωστά παραδείγματα, που εμφανίζει πολλά από τα ίδια μοτίβα που χρησιμοποιούμε σήμερα.
Πέρσης μαθηματικός Αλ-Καράτζι και Ινδός λόγιος PingΟ Πασκάλ επίσης διερεύνησε παρόμοιους πίνακες. Ο Πασκάλ τυποποίησε τις ιδιότητες του τριγώνου στην πραγματεία του 1654 με τίτλο «Traité du triangle arithmétique», η οποία έδωσε στη δομή το σύγχρονο όνομά της στα δυτικά μαθηματικά.
Κατασκευή του Τριγώνου του Πασκάλ
Η κατασκευή του Τριγώνου του Πασκάλ είναι απλή. Ο μόνος κανόνας που πρέπει να θυμάστε είναι ότι κάθε γραμμή ξεκινά και τελειώνει με 1 και κάθε άλλος αριθμός κατασκευάζεται από την παραπάνω γραμμή.
Για οποιαδήποτε γραμμή r και στήλη c, η τιμή ισούται με το άθροισμα των αριθμών στις στήλες c-1 και c της γραμμής r-1.
Εδώ,
- r = 3, 4, 5, …
- n και c = 2, 3, 4, …, r-1.
Ακολουθούν τα βήματα για την κατασκευή του Τριγώνου του Πασκάλ:
Βήμα 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 έως και επτά γραμμές.
Τα βήματα για να το κάνετε αυτό είναι τα εξής:
Βήμα 1) Ξεκινήστε την πάνω σειρά με το "1".
Βήμα 2) Για τη σειρά «r», το στοιχείο «c» θα είναι το άθροισμα της στήλης «c-1» και της στήλης «c» της σειράς «r-1».
Βήμα 3) Ο πρώτος και ο τελευταίος αριθμός σε κάθε σειρά θα είναι πάντα «1».
Ακολουθώντας αυτά τα τρία απλά βήματα, μπορούμε να κατασκευάσουμε συστηματικά ολόκληρο το τρίγωνο.
C++ Code του Τριγώνου του Πασκάλ από την Προηγούμενη Γραμμή
#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 Code του τύπου του τριγώνου Pascal από την προηγούμενη γραμμή
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, αυτό απαιτεί N2 μοναδιαίους χώρους. Επομένως, η πολυπλοκότητα του χώρου είναι O(N2).
Η συνάρτηση χρησιμοποιεί δύο ένθετους βρόχους, ο καθένας εκτελείται έως και "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++ Code Τρίγωνο του Πασκάλ με διωνυμικό συντελεστή
#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 Code Τρίγωνο του Πασκάλ με διωνυμικό συντελεστή
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" φορές. Συνεπώς, η συνολική χρονική πολυπλοκότητα είναι O(n3).
Η πολυπλοκότητα του χώρου είναι σταθερή επειδή δεν αποθηκεύουμε ενδιάμεσα αποτελέσματα. Το πρόγραμμα υπολογίζει κάθε στοιχείο εν κινήσει και το εκτυπώνει μέσα σε μια σειρά, έτσι ώστε η πολυπλοκότητα του χώρου να μειώνεται σε Ο (1).
Μέθοδος 3: Δόμηση του τριγώνου του Pascal με τροποποιημένο διωνυμικό συντελεστή
Στην προηγούμενη τεχνική, χρησιμοποιήσαμε τον τύπο του διωνυμικού συντελεστή για να υπολογίσουμε κάθε στοιχείο. Η τροποποιημένη προσέγγιση εξάγει το C(n, r) απευθείας από το C(n, r-1), μειώνοντας το έργο κατά μία τάξη μεγέθους.
Ακολουθούν τα βήματα για την κατασκευή του Τριγώνου του Πασκάλ με βάση τον τροποποιημένο διωνυμικό συντελεστή:
Βήμα 1) Ξεκινήστε την πρώτη γραμμή με "1".
Βήμα 2) Υπολογίστε το C(n, r), όπου το “n” είναι ο αριθμός γραμμής και το “r” είναι ο δείκτης στήλης. Αντιστοιχίστε αυτήν την τιμή σε μια μεταβλητή C.
Βήμα 3) Για τον υπολογισμό του επόμενου συντελεστή, χρησιμοποιήστε C * (n – k) / k. Αντιστοιχίστε αυτήν τη νέα τιμή ξανά στο C.
Βήμα 4) Συνεχίστε το βήμα 3 μέχρι το «k» να φτάσει στο τέλος της σειράς. Μετά από κάθε επανάληψη, αυξήστε το k κατά ένα.
C++ Code για το τρίγωνο του 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 Code για το τρίγωνο του 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» είναι ο αριθμός των γραμμών στο τρίγωνο. Έτσι, η χρονική πολυπλοκότητα είναι Επί2), στο τετράγωνο του χρόνου.
Όσον αφορά την πολυπλοκότητα του χώρου, δεν χρειαζόμαστε κανέναν πίνακα για αποθήκευση. Χρησιμοποιούμε μόνο μία μεταβλητή για να διατηρήσουμε τον προηγούμενο διωνυμικό συντελεστή, επομένως χρειαζόμαστε μόνο έναν επιπλέον χώρο. Η πολυπλοκότητα του χώρου είναι επομένως Ο (1).
Εφαρμογή του Τριγώνου του Πασκάλ
Ακολουθούν μερικές πρακτικές εφαρμογές του Τριγώνου του Πασκάλ:
Διωνυμικές επεκτάσεις: Οι συντελεστές οποιουδήποτε διωνυμικού αναπτυξιακού συστήματος μπορούν να διαβαστούν απευθείας από το τρίγωνο του Pascal. Ακολουθεί ένα παράδειγμα:
| (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 |
Υπολογισμός συνδυασμών: Τα στοιχεία του τριγώνου του Pascal αντιστοιχούν άμεσα σε διωνυμικούς συντελεστές. Για παράδειγμα, αν έχετε 6 μπάλες και θέλετε να επιλέξετε 3, η απάντηση είναι 6C3Μπορείτε να βρείτε αυτήν την τιμή στο 3ο στοιχείο της 6ης γραμμής του τριγώνου του Pascal.
Πιθανότητα: Το τρίγωνο του Pascal χρησιμοποιείται ευρέως για τον υπολογισμό πιθανοτήτων σε ρίψεις κερμάτων, προβλήματα ζαριών και άλλα συνδυαστικά γεγονότα όπου κάθε αποτέλεσμα αντιστοιχεί σε μια διωνυμική κατανομή.
Ενδιαφέροντα γεγονότα για το Τρίγωνο του Πασκάλ
Εδώ είναι μερικά στοιχεία που θα βρείτε ενδιαφέροντα για το τρίγωνο του Πασκάλ:
- Το άθροισμα όλων των στοιχείων σε οποιαδήποτε σειρά είναι πάντα δύναμη του 2.
- Τα διαγώνια αθροίσματα των γραμμών δημιουργούν την ακολουθία Fibonacci.
- Κάθε γραμμή αντιστοιχεί στους συντελεστές στην ανάπτυξη του (a+b)n.
- Αν σκιάσετε μόνο τους περιττούς αριθμούς, το σχήμα που προκύπτει σχηματίζει το φράκταλ του τριγώνου Sierpinski.
