Υπολογιστής Αριθμών Catalan

Τύπος

How this is calculated

Εισαγάγετε έναν μη αρνητικό ακέραιο n. Οι αριθμοί Catalan Cₙ μετρούν μια τεράστια οικογένεια συνδυαστικών αντικειμένων: το πλήθος των τρόπων σωστής αντιστοίχισης n ζευγών παρενθέσεων, το πλήθος των πλήρων δυαδικών δέντρων με n+1 φύλλα, το πλήθος των μονότονων μονοπατιών πλέγματος που παραμένουν κάτω από τη διαγώνιο, και το πλήθος των τριγωνοποιήσεων ενός κυρτού (n+2)-γώνου — όλα ίσα με το ίδιο Cₙ.

Η κλειστή μορφή είναι Cₙ = (2n)! / ((n+1)! · n!), ισοδύναμα ο κεντρικός διωνυμικός συντελεστής C(2n, n) διαιρεμένος με (n+1). Ο άμεσος υπολογισμός παραγοντικών υπερχειλίζει γρήγορα, οπότε αυτός ο υπολογιστής χρησιμοποιεί την ακριβή ακέραια αναδρομή C₀ = 1 και C_{k+1} = C_k · 2(2k+1)/(k+2). Κάθε βήμα πολλαπλασιάζει με έναν παράγοντα ακέραιας τιμής, κρατώντας την τρέχουσα τιμή ακριβή για όσο επιτρέπει η διπλή ακρίβεια και χτίζοντας την πλήρη ακολουθία C₀…Cₙ σχεδιασμένη στην καμπύλη ανάπτυξης.

Οι τιμές είναι αδιάστατα πλήθη, οπότε μόνο ακέραιο n ≥ 0 έχει νόημα· η κλασματική είσοδος στρογγυλοποιείται προς τα κάτω. Επειδή το Cₙ μεγαλώνει περίπου σαν 4ⁿ / (n^{3/2}√π), οι αριθμοί υπερβαίνουν το εύρος ακριβών ακεραίων ενός float 64 bit πέρα από περίπου n = 30 και υπερχειλίζουν εντελώς πέρα από n ≈ 170, οπότε η είσοδος περιορίζεται στο 170 και τα μεγάλα αποτελέσματα εμφανίζονται σε επιστημονική σημειογραφία.