Τρίγωνο του Πασκάλ

Στα μαθηματικά, το τρίγωνο του Πασκάλ είναι μία τριγωνική γεωμετρική διάταξη των δυωνυμικών συντελεστών. Ονομάστηκε έτσι προς τιμήν του μαθηματικού Μπλεζ Πασκάλ στο μεγαλύτερο μέρος του δυτικού κόσμου, παρόλο που άλλοι μαθηματικοί το είχαν μελετήσει αιώνες πριν στην Ινδία, την Περσία, την Κίνα και την Ιταλία.

Οι σειρές στο τρίγωνο του Πασκάλ αριθμούνται ξεκινώντας από την γραμμή 0, και οι αριθμοί κάθε σειράς είναι συνήθως σχετικοί με τις διπλανές τους. Μια απλή κατασκευή του τριγώνου γίνεται με τον ακόλουθο τρόπο. Στην σειρά 0 γράφεται μόνο ο αριθμός 1. Μετά, για την κατασκευή των στοιχείων των ακόλουθων σειρών προστίθεται ο αριθμός που βρίσκεται αμέσως από πάνω και αριστερά με τον αριθμό αμέσως από πάνω και δεξιά. Αν οποιοσδήποτε από τους αριθμούς δεξιά ή αριστερά δεν υπάρχει, υποκαθίσταται με μηδέν. Για παράδειγμα, ο πρώτος αριθμός της πρώτης γραμμής είναι 0 + 1 = 1, ενώ οι αριθμοί 1 και 3 της τρίτης σειράς προστίθενται ώστε να δώσουν τον αριθμό 4 της τέταρτης σειράς.

Αυτή η κατασκευή είναι συγγενική με του δυωνυμικούς συντελεστές μέσω της ταυτότητας του Πασκάλ, σύμφωνα με την οποία αν:

(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}

τότε

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

για οποιοδήποτε μη αρνητικό ακέραιο n και οποιονδήποτε ακέραιο k μεταξύ 0 και n.^[1]

Το τρίγωνο του Πασκάλ γενικεύεται και σε περισσότερες διαστάσεις. Η τρισδιάστατη εκδοχή αποκαλείται Πυραμίδα του Πασκάλ ή Τετράεδρο του Πασκάλ, ενώ η γενική εκδοχή αποκαλείται Simplex του Πασκάλ.

Υπολογισμός με πρόγραμμα

Το παρακάτω πρόγραμμα σε python υπολογίζει τις πρώτες γραμμές του τριγώνου του Πασκάλ, χρησιμοποιώντας τον αναδρομικό τύπο (δηλαδή δυναμικό προγραμματισμό) για τους διωνυμικούς συντελεστές.

triangle = [ [1] ]
rows = 8

for row in range(1, rows):
   cur_row = [1] # Ξεκινάμε καινούργια γραμμή με το στοιχείο 1.
   for col in range(1, row):
      # Χρησιμοποιούμε τον αναδρομικό τύπο για να υπολογίσουμε 
      # το καινούργιο στοιχείο.
      val = triangle[row-1][col-1] + triangle[row-1][col]
      cur_row.append(val)
   cur_row.append(1) # Προσθέτουμε το τελευταίο στοιχείο.
   # Προσθέτουμε την καινούργια γραμμή στο τρίγωνο.
   triangle.append(cur_row)

# Τυπώνουμε το τρίγωνο του Πασκάλ.
print(triangle)