Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand - Dyck

Abstract

Οι αριθμοί Catalan θεωρούνται ως οι πιο σημαντικοί αριθμοί της Συνδυαστικής, μετά τους διωνυμικούς συντελεστές, λόγω της εντυπωσιακά συχνής εμφάνισής τους σε διάφορα προβλήμα¬τα. Ενδεικτικά, ο R. Stanley διατηρεί αρχείο [67] με περισσότερα από 100 διαφορετικά σύνολα συνδυαστικών αντικείμενων που απαριθμούνται από τους αριθμούς Catalan και άρα είναι πλη- θικά αλλά και δομικά ισοδύναμα. Τα πιο διαδεδομένα από αυτά είναι ίσως τα μονοπάτια (λέξεις) Dyck και τα δυαδικά δένδρα. Το κεντρικό αντικείμενο μελέτης της διατριβής αυτής είναι τα μονοπάτια Dyck, τα οποία αποτελούν απλά μια αναπαράσταση στο επίπεδο των λέξεων Dyck. Λόγω της απλής και εύ¬ληπτης γεωμετρικής τους αναπαράστασης, αποτελούν ένα αντιπροσωπευτικό αντικείμενο της οικογένειας των αντικειμένων Catalan και προσφέρονται για τη μελέτη ιδιοτήτων, οι οποίες μπο¬ρούν στη συνέχεια να μεταφραστούν κατάλληλα και σε ιδιότητες των υπόλοιπων αντικειμένων της οικογένειας. Επιπλέον, με την εισαγωγή κατάλληλων περιορισμών (παραμέτρων), προκύπτουν ειδικές κατηγορίες μονοπατιών Dyck που ισοδυναμούν με σύνολα άλλων γνωστών αντικειμένων, οπότε τα αποτελέσματα επεκτείνονται και στα αντικείμενα αυτά. Στη διατριβή αυτή, μελετάται η παράμετρος ‘‘πλήθος εμφανίσεων του προτύπου τ’’, όπου ως πρότυπο θεωρείται μια οποιαδήποτε δυαδική λέξη. Στο πρώτο Κεφάλαιο, παρουσιάζονται εκτενώς οι βασικές έννοιες που χρησιμοποιούνται στα υπόλοιπα Κεφάλαια. Στο δεύτερο Κεφάλαιο, μελετάται το πρόβλημα της απαρίθμησης των εμφανίσεων ενός προ¬τύπου τ σε καθορισμένο ύψος j στο μονοπάτι Dyck. Το πρόβλημα απαντάται πλήρως, για κάθε πρότυπο τ και δίνεται ο τύπος της αντίστοιχης γεννήτριας συνάρτησης. Τα βασικά αποτελέ¬σματα αυτού του Κεφαλαίου έχουν δημοσιευθεί στην εργασία [44]. Στο τρίτο Κεφάλαιο, μελετάται το πρόβλημα της απαρίθμησης των εμφανίσεων ενός προτύ¬που τ ανεξαρτήτως ύψους ή όταν το ύψος τους είναι τουλάχιστον j. Το πρόβλημα απαντάται πλήρως, μέσω της αντίστοιχης γεννήτριας συνάρτησης, όταν το πρότυπο τ είναι ένα πρόθεμα Dyck ή ένα επίθεμα Dyck, καθώς και σε ορισμένες άλλες γενικές περιπτώσεις. Σημειώνεται ότι η πλήρης γενίκευση των αποτελεσμάτων που καλύπτει όλες τις δυνατές μορφές του προτύπου τ αποτελεί ανοικτό πρόβλημα. Τα βασικά αποτελέσματα αυτού του Κεφαλαίου έχουν δημοσιευθεί στην εργασία [45]. Στο τέταρτο Κεφάλαιο, μελετάται το πρόβλημα της απαρίθμησης των εμφανίσεων ενός προ¬τύπου τ μήκους 3 σε μονοπάτια Grand-Dyck. Επιπλέον, θεωρώντας τη βοηθητική παράμετρο ‘‘πλήθος ανόδων σε αρνητικό ύψος’’, προκύπτουν σε ορισμένες περιπτώσεις εκλεπτύνσεις του θεωρήματος Chung-Feller. Τα βασικά αποτελέσματα αυτού του Κεφαλαίου έχουν δημοσιευθεί στην εργασία [47]. Στο πέμπτο Κεφάλαιο, μελετώνται τρεις νέες παράμετροι οι οποίες αποτελούν εξειδικεύσεις της γνωστής παραμέτρου ‘‘πλήθος κορυφών'' των μονοπατιών Dyck. Τα βασικά αποτελέσματα αυτού του Κεφαλαίου είναι υπό κρίση προς δημοσίευση. Στο έκτο Κεφάλαιο δίδονται ακριβείς αλλά και ασυμπτωτικοί τύποι για τη μέση τιμή και τη διακύμανση των παραμέτρων που παρουσιάζονται στα υπόλοιπα κεφάλαια. Τα περισσότερα από τα αποτελέσματα αυτού του Κεφαλαίου έχουν παρουσιαστεί στα συνέδρια [43] και [48].