Salve, l'altro giorno stavo cercando di inventare un problema da proporre alle gare, ritenendo interessante il procedimento che stavo adottando sono andato avanti per poi arrivare ad una conlucione che mi ha distrutto il problema rendendolo "banale" per chi ha fatto almeno una gara di matematica nella vita.. In soldoni, ho ricavato che:
$ n! = \sum_{k=0}^n \binom{n}{k}\cdot !(n-k) $, adesso, pensandoci, la dimostrazione <a parole> è abbastanza immediata e quindi mi sono sforzato di voler dimostrare la formula per induzione, ma son rimasto a fissarla amorevolemente per un'oretta buona.. Mi chiedevo dunque se e in che modo si potesse dimostrare per induzione (nb. ero in spiaggia sotto il sole quindi è possibilissimo che non mi sia accorto di un modo 'semplice', in tal caso non fustigatemi, please )..
Comunque la 'spiegazone/dimostrazione' che ho dato, per chi fosse interessato, è questa:
Testo nascosto:
Considero un insieme $ A $ di $ n $ elementi, e una funzione biettiva $ f:A\rightarrow A $ (in soldoni, considero una permutazione di A). Adesso, procedo per gradi: scelgo $ 0 $ elementi fissi ($ f(x)=x $), lo posso fare in un solo modo, quindi $ \binom{n}{0} $, i restanti n elementi li posso permutare in $ !n $ modi, in modo che nessuno di questi sia fisso. Adesso considero un elemento $ x_0 $ fisso, tale $ x_0 $ lo posso scegliere in $ \binom{n}{1} $ modi e i restanti n-1 elementi li permuto (senza punti fissi) in $ !(n-1) $ modi. Vado avanti...... Considero $ x_0,\cdots , x_{n-3} $ elementi fissi, li posso scegliere in $ \binom{n}{n-2} $ modi e i restanti li permuto in $ !2 $ modi (cioè $ n-(n-3) $), adesso il caso in cui ne fissi n-1 è equivalente al caso in cui li fisso tutti, per ovvi motivi e dunque ottengo $ \binom{n}{n}\cdot !(n-n)=1 $; a questo punto il numero delle possibili permutazione è dato dalla somma di tutti i casi considerati, quindi $ !(n)\binom{n}{0} + !(n-1)\binom{n}{1}+\cdots +!2 \binom{n}{n-2}+!1\binom{n}{n-1}+!0\binom{n}{n} $ e dunque $ \sum_{k=0}^n \binom{n}{k}\cdots !(n-k) =n! $
Re: Come dimostro per induzione?
Inviato: 16 ago 2011, 16:29
da lama luka
A si, per chi non lo sapesse..Con $ !n $ indico le permutazioni senza punti fissi ($ f(x)\neq x \forall x $) di n elementi e $ !n= n!\sum_{k=0}^n \frac{(-1)^k}{k!} $.
Re: Come dimostro per induzione?
Inviato: 16 ago 2011, 18:24
da exodd
Il metodo c'è, e non è neanche troppo brutto..
Lo scrivo nel prossimo post
* Si scrocchia le dita *
)..