🔺Αριθμοί Catalan – Η Ακολουθία που Μετρά Τριγωνοποιήσεις, Μονοπάτια και Παρενθέσεις

Οι αριθμοί Catalan αποτελούν μία από τις σημαντικότερες ακολουθίες της συνδυαστικής. Εμφανίζονται κάθε φορά που μετράμε δομές οι οποίες δημιουργούνται αναδρομικά: τριγωνοποιήσεις πολυγώνων, σωστά τοποθετημένες παρενθέσεις, δυαδικά δέντρα, μονοπάτια σε πλέγμα και πολλές ακόμη κατασκευές.

\[1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ 4862,\ldots\]

Ο αναδρομικός ορισμός

Θέτουμε \(C_0=C_1=1\). Για \(n\ge1\), ο επόμενος αριθμός προκύπτει από τη συνέλιξη των προηγουμένων:

\[C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}.\]

Για παράδειγμα,

\[C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5.\]

Η σχέση αυτή εξηγεί γιατί οι αριθμοί Catalan εμφανίζονται σε προβλήματα που χωρίζονται φυσικά σε ένα «αριστερό» και ένα «δεξί» ανεξάρτητο τμήμα.

Ο κλειστός τύπος

\[C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}.\]

Ο τύπος επιτρέπει τον άμεσο υπολογισμό του \(C_n\), χωρίς να χρειάζεται να γνωρίζουμε όλους τους προηγούμενους όρους.

Τι μετρούν οι αριθμοί Catalan;

Τριγωνοποιήσεις πολυγώνου

Οι τρόποι διαίρεσης ενός κυρτού \(m\)-γώνου σε τρίγωνα με μη τεμνόμενες διαγωνίους είναι \(C_{m-2}\). Ένα πεντάγωνο έχει \(C_3=5\) τριγωνοποιήσεις.

Σωστές παρενθέσεις

Οι σωστές διατάξεις \(n\) ζευγών παρενθέσεων είναι \(C_n\). Για \(n=3\) υπάρχουν \(C_3=5\) διαφορετικές διατάξεις.

Μονοπάτια Dyck

Τα μονοπάτια από το \((0,0)\) στο \((2n,0)\), με βήματα πάνω και κάτω, τα οποία δεν περνούν κάτω από τον οριζόντιο άξονα, είναι \(C_n\).

Οι πρώτοι είκοσι αριθμοί

C₀ έως C₁₉: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

Πρόγραμμα Python για τους πρώτους 20 αριθμούς Catalan

def catalan_numbers(count):
    C = [0] * count
    C[0] = 1

    for n in range(1, count):
        C[n] = sum(C[i] * C[n - 1 - i]
                   for i in range(n))
    return C

print(catalan_numbers(20))

Το πρόγραμμα εφαρμόζει απευθείας την αναδρομική σχέση. Για τον υπολογισμό ενός μόνο μεγάλου όρου είναι αποδοτικότερος ο κλειστός τύπος με τον διωνυμικό συντελεστή.

Πόσο γρήγορα μεγαλώνουν;

Για μεγάλα \(n\), ισχύει η ασυμπτωτική προσέγγιση

\[C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}.\]

Ο παράγοντας \(4^n\) προκαλεί πολύ γρήγορη αύξηση, ενώ ο παρονομαστής \(n^{3/2}\) τη μετριάζει. Το σύμβολο \(\sim\) σημαίνει ότι ο λόγος των δύο ποσοτήτων τείνει στο \(1\) καθώς \(n\to\infty\).

Μια σύντομη ιστορική σημείωση

Η ακολουθία φέρει το όνομα του Βέλγου μαθηματικού Eugène Charles Catalan, ο οποίος τη μελέτησε τον 19ο αιώνα. Ωστόσο, σχετικές απαριθμήσεις είχαν εμφανιστεί νωρίτερα στο έργο του Leonhard Euler και του Κινέζου μαθηματικού Minggantu. Όπως συμβαίνει συχνά στα μαθηματικά, το όνομα μιας ακολουθίας δεν αφηγείται ολόκληρη την ιστορία της.

Για κοινοποίηση: Τι κοινό έχουν οι τριγωνοποιήσεις πολυγώνων, οι σωστές παρενθέσεις και τα δυαδικά δέντρα; Όλα μετρώνται από τους αριθμούς Catalan.

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →