Επαγωγή σε δέντρα

Σίλης · #1

Έπεσα πάνω σ' αυτό το πρόβλημα κάποια στιγμή αναπάντεχα, και αν μή τι άλλο καθότι σκουριασμένος με τέτοια «στοιχειώδη», μου πήρε κάμποσο να το λύσω. Δέν το ξέρω το φόρουμ καλά, και δέν είμαι σίγουρος σε ποιά κατηγορία ταιριάζει. Μπορεί να τεθεί με όρους κατηγορηματικής λογικής ή θεωρητικής πληροφορικής: «ποιές ακολουθίες συμβόλων φτιάχνουν έναν επιτρεπτό όρο;». Εγώ το συνάντησα συγκεκριμένα σε συμφραζόμενα συντακτικής ανάλυσης, ψάχνοντας να βρώ στα πρόχειρα έναν γρήγορο αλγόριθμο για ν' αναγνωρίζω συμβολοσειρές πάνω σε δοσμένο αλφάβητο, χωρίς να πρέπει πρώτα να μάθω πάρσιν θίορι και δέ συμμαζεύεται. Τον τρόπο τον βρήκα σχετικά γρήγορα και ευχάριστα, παίζοντας απο δώ κι' απο κεί στο Μαθεμάτικα (του Γούλφραμ, όχι το φόρουμ), αλλα όταν είπα να τη δώ μαθηματικός και να δείξω οτι ο αλγόριθμος πράγματι κάνει αυτό που τον θέλω, έπεσ' η αυτοεκτίμησή μου εκεί που της έπρεπε ξανά (...όχι που θα μου σηκώσεις κεφάλι!).

Σε κάθε περίπτωση, ο πυρήνας του προβλήματος είναι πράγματι στοιχειώδης, καθώς πρόκειται για μιά μπουρδουκλωμένη άσκηση επαγωγής, και έτσι θα το παρουσιάσω. Άς επιληφθούν οι αρμόδιοι για τη μετακίνησή του, άν το θεωρήσουν σκόπιμο.

Τα προκαταρκτικά. Ας είναι

ένα πεπερασμένο σύνολο και $r : A \to \mathbb{N}$ μία συνάρτηση (υπόψιν οτι εδώ συμπεριλαμβάνω το μηδέν στους φυσικούς). Θεωρούμε το σύνολο S_A

των πεπερασμένων ακολουθιών απο στοιχεία του

: για παράδειγμα, άν $A = \{a, b, c\}$ τότε $(a, a, c, b, a, b) \in S_A$ αλλα και $() \in S_A$ (η κενή ακολουθία). Αυτό το σύνολο μπορούμε να το περιγράψουμε επαγωγικά ξεκινώντας απ' την κενή ακολουθία και προθέτοντας στοιχεία του

:

$() \in S_A$ ·
άν $a \in A$ και $(a_1, \ldots, a_m) \in S_A$ τότε και $(a, a_1, \ldots, a_m) \in S_A$ .

Είπα «πρόθέτοντας», αλλα φυσικά γίνεται να το ορίσουμε και χώνοντας κάθε νέο στοιχείο ώς επίθημα· η επιλογή να το κάνουμε με προθήματα βοηθάει στη λύση καθώς συνάδει με τον επόμενο ορισμό. Ορίζουμε λοιπόν και το σύνολο T_A

ώς εξής:

για κάθε $a \in A$ με είναι $(a) \in T_A$ (η ακολουθία με μόνο στοιχείο το )·
άν $a \in A$ με και $(a_{10}, a_{11}, \ldots, a_{1n_1}), \ldots, (a_{m0}, a_{m1}, \ldots, a_{mn_m}) \in T_A$ , τότε και $(a, a_{10}, a_{11}, \ldots, a_{1n_1}, \ldots, a_{m0}, a_{m1}, \ldots, a_{mn_m}) \in T_A$ .

Σά να λέμε, οι ακολουθίες του T_A

λαμβάνουν υπόψη τη συνάρτηση

: άν φερειπείν r(a) = 0, r(b) = 1, r(c) = 3

για το σύνολο επάνω, τότε έχουμε

$() \not\in T_A, (a) \in T_A, (b) \not\in T_A, (b, a) \in T_A, (c, a, a, a) \in T_A, (c, b, a, a, b, a) \in T_A$

και τα λοιπά. Βοηθάει ίσως να το μαρτυρήσουμε οτι μπορούμε να φανταστούμε αυτές τις ακολουθίες σά δέντρα: πιχί η τελευταία αντιστοιχεί στην παράσταση

$\begin{array}{ccc} & c & \\ \quad / & \mid & \backslash\quad \\ b & a & b \\ \mid & & \mid \\ a & & a \\ \end{array}$

Ίσως βέβαια και να μή βοηθάει. Εντάξει.

Τώρα, το πρόβλημα. Ισχύει $T_A \subseteq S_A$ . Ανάποδα, ας είναι $(a_0, a_1, \ldots, a_m) \in S_A$ μιά οποιαδήποτε περατή ακολουθία· πώς μπορούμε να μάθουμε άν $(a_0, a_1, \ldots, a_m) \in T_A$ χρησιμοποιώντας το πολύ προσθαφαιρέσεις;

Για να το φέρω πιό πολύ σε άσκηση, να δώσω μία κατεύθυνση προς τη λύση που είχα βρεί προσωπικά. Θεωρήστε τη συνάρτηση $tr: S_A \to \mathbb{Z}$ με

,
$tr(a_0, a_1, \ldots, a_m) := r(a_0) + tr (a_1, \ldots, a_m) - 1$ ,

και δείξτε ότι

$(a_0, a_1, \ldots, a_m) \in T_A$ άν και μόνο άν $tr(a_0, a_1, \ldots, a_m) = 0$ και $tr(a_0, \ldots, a_{m'}) > 0$ για κάθε m' < m

.

Κάτι που ξέχασα επάνω: για να βγάζουν όλ' αυτά νόημα, είναι καλό να απαιτήσουμε απο την

να απεικονίζει ένα τουλάχιστον στοιχείο του

στο

.

#2

Η επιβεβαίωση της λύσης δεν είναι τόσο δύσκολη. (Άλλη κουβέντα το πόσο δύσκολα βρέθηκε.)

Δίνω μια διαφορετική αντιμετώπιση:

Για κάθε ακολουθία $(a_0,a_1,\ldots,a_m)$ ορίζω μια λέξη στα R,U

(σκεφτείτε "RIGHT" και "UP") ως εξής: Το στοιχείο

με

αντιστοιχεί στην λέξη

$\underbrace{RR\cdots R}_{k\, R's}U$ .

Σε κάθε λέξη στα R,U

αντιστοιχώ ένα μονοπάτι στο πλέγμα το οποίο ξεκινάει από το (0,0)

και κατασκευάζεται ως εξής: Ξεκινώντας την λέξη από τα αριστερά, αν δω

πάω από το (x,y)

στο

, αν δω

πάω από το (x,y)

στο

.

Οπότε σε κάθε ακολουθία $(a_0,a_1,\ldots,a_m)$ μπορώ να αντιστοιχίσω ένα μονοπάτι μέσω της ενδιάμεσης λέξης.

Τότε έχω το εξής: $(a_0,a_1,\ldots,a_m) \in T_A$ αν και μόνο αν r(a_m)=0

και το μονοπάτι που αντιστοιχεί στην ακολουθία $(a_0,a_1,\ldots,a_{m-1})$ [Προσοχή! Σταματώ στο m-1

.] ξεκινάει από το (0,0)

, τελειώνει στο (m,m)

και δεν περνάει ποτέ πάνω από την ευθεία y=x

.

Η απόδειξη είναι της ίδιας δυσκολίας με την απόδειξη της άσκησης του Σίλη (της οποίας δεν έδωσα λύση). Μάλιστα δεν είναι δύσκολο να δείξουμε ότι οι δυο συνθήκες (η δική μου και του Σίλη) είναι ισοδύναμες χωρίς να αποδείξουμε καμία από αυτές.

Ο λόγος που έγραψα αυτήν την συνθήκη είναι ο εξής: Αν η ακολουθία $(a_0,\ldots,a_m)$ ανήκει στο T_A

ή όχι εξαρτάται αποκλειστικά και μόνο από την ακολουθία $(r(a_0),\ldots,r(a_m))$ . Για κάθε

ο αριθμός αυτών των ακολουθιών που μας κάνουν είναι ο αριθμός Catalan $\displaystyle{C_m = \frac{1}{m+1}\binom{2m}{m}.}$ Δείτε π.χ. εδώ.

Σίλης · #3

Αριθμοί Καταλάν λοιπόν... Άρα έχουμε διάβασμα. Νά 'σαι καλά Δημήτρη, χτύπησες νεύρο.

#4

Να πω ότι υπάρχει περιγραφή των αριθμών Catalan χρησιμοποιώντας και δέντρα αντί τα μονοπάτια που χρησιμοποίησα. Απλά έδωσα τα μονοπάτια που είναι η πιο κλασική περιγραφή. Εδώ μπορείτε να βρείτε δύο αρχεία με συνολικά 207

περιγραφές ακολουθιών που απαριθμούνται από τους αριθμούς Catalan.

Επαγωγή σε δέντρα

Επαγωγή σε δέντρα

Re: Επαγωγή σε δέντρα

Re: Επαγωγή σε δέντρα

Re: Επαγωγή σε δέντρα

Μέλη σε σύνδεση