mathematica.gr

Δημοσιεύτηκε: **Κυρ Οκτ 16, 2011 10:35 pm**

Ίσως να μην είναι το πιο κατάλληλο section να αναρτήσω αυτό το θέμα, αλλά για κάποιο λόγο δεν μπορώ να κάνω post στο Seniors.

Να βρεθεί η ακολουθία που ικανοποιεί την αναδρομική σχέση:

$a_n=(n-1)(a_{n-1}+a_{n-2})$

με αρχικές συνθήκες a_1=0, a_2=1

.

Υ.Γ. Με χαρά βλέπω και τις αλλαγές που έγιναν στο forum καθώς και την ανταπόκριση που υπάρχει!

Δημοσιεύτηκε: **Δευ Οκτ 17, 2011 2:45 pm**

Η απάντηση είναι $\displaystyle{ a_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}}$ και είναι φυσικά εύκολο να ελεγχθεί ότι είναι ορθή. Δεν θα κάνω τις πράξεις για τον έλεγχο αλλά θα δώσω κάποιες ιδέες για το πως προέκυψε. (Δεν ήρθε ουρανοκατέβατη.)

Αν η σχέση ήταν μόνο $a_n = (n-1)a_{n-1}$ για n > 2

τότε εύκολα θα βλέπαμε ότι a_n = (n-1)!a_1

. Παίζοντας λίγο με παρόμοιες συναρτήσεις, παρατηρούμε ότι η a_n = n!

ικανοποιεί την αναδρομική σχέση αλλά όχι τις αρχικές συνθήκες. Ορίζουμε λοιπόν a_n = n!b_n

και βλέπουμε ότι $\displaystyle{ b_n = \left(1 - \frac{1}{n} \right)b_{n-1} + \frac{b_{n-2}}{n}}$ με αρχικές συνθήκες b_1=0,b_2=1/2

. Ισοδύναμα έχουμε $\displaystyle{ b_n - b_{n-1} = \frac{b_{n-2} - b_{n-1}}{n}.}$ Από εδώ ορίζουμε $c_n = b_n - b_{n-1}$ και βλέπουμε ότι $\displaystyle{ c_n = -\frac{c_{n-1}}{n}}$ με c_2=1/2

και άρα $\displaystyle{ c_n = \frac{(-1)^{n}}{n!}. }$ Επομένως $\displaystyle{ b_n = b_{n-1} + c_n = b_{n-2} + c_{n-1} + c_n = \cdots = c_1 + \cdots + c_n}$ και άρα $a_n = n!(c_1 + \cdots + c_n)$ που δίνει το πιο πάνω αποτέλεσμα.

Εκ των υστέρων βέβαια, και γνωρίζοντας τι αντιπροσωπεύει το άθροισμα που βρήκαμε μπορούμε να πούμε ότι το a_n

ισούται με τον αριθμό των 1-1 και επί συναρτήσεων $\displaystyle{ f: \{1,2,\ldots,n\} \to \{1,2,\ldots,n\}}$ οι οποίες δεν έχουν σταθερό σημείο.

Να προσθέσω και μια απόδειξη ότι αν D_n

ισούται με τον αριθμό των πιο πάνω συναρτήσεων τότε ισχύει η αναδρομική σχέση $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Πράγματα αν $f(n) = i \neq n$ τότε αναδρομικά υπάρχουν $D_{n-1}$ συναρτήσεις $\displaystyle{ f: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n\} \setminus \{i\}}$ με $f(i) \neq n$ χωρίς σταθερό σημείο και $D_{n-2}$ συναρτήσεις $\displaystyle{ f: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n\} \setminus \{i\}}$ με f(i) = n

χωρίς σταθερό σημείο. Αθροίζοντας για $i=1,2,\ldots,n-1$ βρίσκουμε την αναδρομική σχέση.

Δημοσιεύτηκε: **Κυρ Οκτ 23, 2011 8:40 pm**

Ακριβώς!

Κι εγώ έφτασα σε αυτή την αναδρομική προσπαθώντας να λύσω το πρόβλημα που περιγράφει ο Δημήτρης (γνώστο και ως Derangement Problem) και μετά παρατήρησα ότι

$a_n-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})\Longrightarrow u_n=-u_{n-1}$
...

Μια άλλη λύση για το Derangement Problem προκύπτει με χρήση της αρχής εγκλεισμού-αποκλεισμού.

Υ.Γ. Θα ήθελα να διευκρινίσω για τα νεότερα μέλη του forum ότι με τον όρο σταθερό σημείο ο Δημήτρης εννοεί κάποιο i=1,2,...,n

τέτοιο ώστε f(i)=i

.

Δημοσιεύτηκε: **Τετ Νοέμ 02, 2011 10:58 pm**

Μια λύση με γεννήτριες συναρτήσεις.

$\displaystyle{{a_n} = \left( {n - 1} \right)\left( {{a_{n - 1}} + {a_{n - 2}}} \right) \Rightarrow {a_{n + 2}} = \left( {n + 1} \right)\left( {{a_{n + 1}} + {a_n}} \right)}$ , $\displaystyle{{a_1} = 0}$ και $\displaystyle{{a_2} = 1}$ . Εύκολα προκύπτει ότι $\displaystyle{{a_0} = 1}$

Ορίζουμε $\displaystyle{{a_n} = n!{b_n}}$ , τότε $\displaystyle{\left( {n + 2} \right)!{b_{n + 2}} = \left( {n + 1} \right)\left( {\left( {n + 1} \right)!{b_{n + 1}} + n!{b_n}} \right) \Rightarrow \left( {n + 2} \right){b_{n + 2}} = \left( {n + 1} \right){b_{n + 1}} + {b_n}}$ και $\displaystyle{{b_0} = 1}$ , $\displaystyle{{b_1} = 0}$ .

Έστω $\displaystyle{f\left( x \right) = \sum\limits_{n = 0}^\infty {{b_n}{x^n}} }$ , τότε

$\displaystyle{\left( {n + 2} \right){b_{n + 2}} = \left( {n + 1} \right){b_{n + 1}} + {b_n} \Rightarrow \sum\limits_{n = 0}^\infty {\left( {n + 2} \right){b_{n + 2}}{x^{n + 1}}} = \sum\limits_{n = 0}^\infty {\left( {n + 1} \right){b_{n + 1}}{x^{n + 1}}} + \sum\limits_{n = 0}^\infty {{b_n}{x^{n + 1}}} \Rightarrow }$

$\displaystyle{ \Rightarrow {\left( {\sum\limits_{n = 0}^\infty {{b_{n + 2}}{x^{n + 2}}} } \right){'}} = x{\left( {\sum\limits_{n = 0}^\infty {{b_{n + 1}}{x^{n + 1}}} } \right){'}} + x\sum\limits_{n = 0}^\infty {{b_n}{x^n}} \Rightarrow {\left( {\sum\limits_{n = 2}^\infty {{b_n}{x^n}} } \right){'}} = x{\left( {\sum\limits_{n = 1}^\infty {{b_n}{x^n}} } \right){'}} + x\sum\limits_{n = 0}^\infty {{b_n}{x^n}} \Rightarrow }$

$\displaystyle{ \Rightarrow f'\left( x \right) = xf'\left( x \right) + xf\left( x \right) \Rightarrow \boxed{f'\left( x \right) + \frac{x}{{x - 1}}f\left( x \right) = 0}}$ .

Με κλασσική θεωρία επίλυσης γραμμικών διαφορικών εξισώσεων πρώτου βαθμού βρίσκουμε ότι $\displaystyle{f\left( x \right) = c\frac{1}{{x - 1}}{e^{ - x}}}$

και με δεδομένο ότι $\displaystyle{f\left( 0 \right) = {b_0} = 1}$ προκύπτει $\displaystyle{f\left( x \right) = \frac{1}{{1 - x}}{e^{ - x}} = \sum\limits_{k = 0}^\infty {{x^k}} \cdot \sum\limits_{k = 0}^\infty {{{\left( { - 1} \right)}^k}\frac{{{x^k}}}{{k!}}} = \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} } \right){x^k}} }$

Επομένως $\displaystyle{{b_n} = \sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} }$ και $\displaystyle{{a_n} = n!\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} }$ .

Το ανάπτυγμα Taylor, απευθείας στην a_n

δεν "δούλεψε".

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 8:43 pm**

Αυτό το ν! τι συμβολίζει?
Φερμά
Β’ λυκείου

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 8:46 pm**

Το

είναι το γινόμενο όλων των φυσικών αριθμών από το

εώς το

και διαβάζεται n παραγοντικό.

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 8:50 pm**

$\displaystyle{n!=n\cdot(n-1)\cdot(n-2)\cdot ... \cdot2\cdot1}$
διαβάζεται

παραγοντικό και πρέπει $n\in \mathbb{N}$ δηλαδή το

να είναι φυσικός αριθμός

πχ.
$\displaystyle{1!=1}$
$\displaystyle{2!=2\cdot1=2}$
$\displaystyle{3!=3\cdot2\cdot1=6}$
$\displaystyle{4!=4\cdot3\cdot2\cdot1=24}$
...
τέλος δεχόμαστε πως $\displaystyle{0!=1}$

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:19 pm**

Ευχαριστώ πολύ!!!!
Και αυτό σε ασκήσεις πως το χρησιμοποιώ?

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:21 pm**

Αυτό το σύμβολο θα το συναντήσεις μόνο σε μαθηματικούς διαγωνισμούς ή αργότερα στο πανεπιστήμιο και όχι στο σχολείο.

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:28 pm**

Ακριβώς!!Για διαγωνισμούς ρωτάω.

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:30 pm**

Όπου συνδυαστική και παραγοντικο!!

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:33 pm**

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

Δημοσιεύτηκε: **Τρί Νοέμ 15, 2011 9:34 pm**

Ρίξε μια ματιά εδώ, αλλά ίσως σου πέσει βαρύ γιατί είναι πανεπιστημιακό.
Καλύτερα θα ήταν να έπαιρνες ένα βιβλίο που να τα περιγράφει.
Δεν μπορείς να απαντήσεις συνοπτικά πχ τι κάνεις με τις εξισώσεις. Είναι πολύ γενικό.
Συνήθως χρησιμοποιείται στον κλάδο των Μαθηματικών που λέγεται Συνδυαστική, σχετικό με τις Πιθανότητες.
Οι λέξεις που μπορείς να κάνεις αναζήτηση στο διαδίκτυο είναι ''παραγοντικό'' ,''βασική αρχή απαρίθμησης'' και ''συνδυαστική''.

mathematica.gr

Αναδρομική Σχέση

Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση