Λύση αναδρομικής σχέσης

Mathletic · #1

Γειά

Πώς μπορώ να λύσω την παρακάτω αναδρομική σχέση;

$\displaystyle{P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)}$ για $\displaystyle{n>1}$
$\displaystyle{P(1)=1}$

Ιστοσελίδα · #2

Είναι ένας τύπος για τους αριθμούς Catalan.
Θα επανέλθω αναλυτικότερα...

Συγκεκριμένα, αν θέλουμε να υπολογίσουμε το πλήθος των δυνατών τριγωνοποιήσεων ενός πολυγώνου

, τότε
θεωρούμε το πολύγωνο

, όπως στην εικόνα. Η ακμή του e θα ανήκει σε μοναδικό τρίγωνο Τ. Επιλέγοντας την τρίτη κορυφή του Τ (που δεν ανήκει στην e) σχηματίζονται δύο μικρότερα πολύγωνα P_1 , P_2

τα οποία θα έχουν σύνολο πλευρών n+2

. Από πολλαπλασιαστική αρχή της συνδυαστικής προκύπτει ότι οι τριγωνοποιήσεις του n-γώνου

θα είναι : $T_n = T_2 T_{n-1} + T_3 T_{n-2} + \ldots + T_{n-1} T_2 , n\geq 3$ . Συνεπώς, αν θεωρήσουμε $C_n = T_{n+2}$ τότε προκύπτει ο αναδρομικός τύπος ( του Segner όπως λέγεται) : $C_n = C_0 C_{n-1} + C_1 C_{n-2} + \ldots + C_{n-1} C_0$

Εικόνα

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Λύση αναδρομικής σχέσης

Λύση αναδρομικής σχέσης

Re: Λύση αναδρομικής σχέσης

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