OliForum Matematico

Sia $ P_n(k) $ il numero delle permutazioni dell'insieme $ \{1,2,3,\dots,n\} $ con esattamente k punti fissi.
Dimostrare che: $ \sum_{k=0}^nkP_n(k)=n! $

Buon lavoro, Simone.

Allora, posto in invisibile:

stabilisco che il primo elemento rimanga fisso e faccio tutte le permutazioni possibili con gli altri. Faccio la stessa cosa con il secondo elemento e poi con tutti gli altri. A questo punto ho calcolato una somma di permutazioni nella quale ho calcolata k volte le permutazioni con k elementi fissi (le conto una volta per ogni elemento fisso da cui inizio). Il valore trovato è quello che si cercava e corrisponde alle possibili scelte dell'elemento fisso in partenza per le permutazioni degli altri n-1. Banalmente n*(n-1)!=n!

QED

ciao!

P.S. Ma si può calcolare Pk(n)?

piever ha scritto:P.S. Ma si può calcolare Pk(n)?

Si che si può..infatti io l'avevo calcolato e poi avevo indotto (in realtà avevo indotto 2 volte nella stessa soluzione)

Prova a dimostrare che:
$ P_n(k)= {n\choose k}(n-k)!\sum_{i=0}^{n-k}(-1)^i\frac{1}{i!} $

Però è mooolto più figo come hai fatto te (anzi è proprio la soluzione che volevo leggere)!!!

edit: la fretta di scrivere..

La formula per calcolare il numero di permutazioni su $ n>0 $ elementi che non hanno elementi uniti è $ n!\sum^{n}_{i=0}\frac{(-1)^i}{i!} $. L'indice i deve partire da 0.

Kocour ha scritto:La formula per calcolare il numero di permutazioni su $ n>0 $ elementi che non hanno elementi uniti è $ n!\sum^{n}_{i=0}\frac{(-1)^i}{i!} $.

Trallaltro il dimostrare questa formula è un'esercizio utilissimo per imparare ad usare il PIE

Mi sembrava strano che la sommatoria a destra fosse negativa...
In ogni caso quella formula è graficamente evidente guardando il triangolo di tartaglia: se, in ogni riga, sommi le cifre a segno alterno ti viene zero, tranne nella zeresima riga (quella con un elemento) che dà 1.