αρχείο θεμάτων εμεΌταν η απευθείας μέτρηση είναι δύσκολη, μέτρησε τις περιπτώσεις για \(n\) με βάση τις μικρότερες.
τα βασικά
- Πλακοστρώσεις \(2\times n\) με ντόμινο: \(a_n=a_{n-1}+a_{n-2}\), \(a_1=1\), \(a_2=2\). Δίνει τους αριθμούς Fibonacci.
- Δυαδικές λέξεις μήκους \(n\) χωρίς δύο διαδοχικούς άσσους: ίδια αναδρομή, με 2 λέξεις για \(n=1\) και 3 για \(n=2\).
- Αστέρια και διαχωριστικά: οι λύσεις της \(x_1+\dots+x_k=n\) σε μη αρνητικούς ακέραιους είναι \(\binom{n+k-1}{k-1}\).
- Pascal: \(\binom nk=\binom{n-1}{k-1}+\binom{n-1}k\) και \(\binom n0+\binom n1+\dots+\binom nn=2^n\).
παράδειγμα
Με πόσους τρόπους ανεβαίνεις 6 σκαλοπάτια, αν κάθε φορά ανεβαίνεις 1 ή 2;
Λύση. Αν \(a_n\) οι τρόποι για \(n\) σκαλοπάτια, το τελευταίο βήμα είναι 1 ή 2, άρα \(a_n=a_{n-1}+a_{n-2}\) με \(a_1=1\), \(a_2=2\). Βγαίνει 1, 2, 3, 5, 8, 13. Άρα 13 τρόποι.
συχνό λάθος
Λάθος αρχικές τιμές. Υπολόγισε με το χέρι τις πρώτες δύο ή τρεις περιπτώσεις πριν εμπιστευτείς την αναδρομή.