Permutazioni e punti fissi

[ilario991]

Salve. Esiste una formula o un modo che permetta di trovare il numero di permutazioni di dimensione n che hanno esattamente k punti fissi? (senza generare tutte le permutazioni...)

PS: per punto fisso indento un permutazione in cui l'i-esimo elemento si trova in posizione i, cioè P = i

[Rggb1]

"mate_92":PS: per punto fisso indento un permutazione in cui l'i-esimo elemento si trova in posizione i, cioè P = i

Quindi non entra nella permutazione; dunque è il numero delle permutazioni di n elementi con k punti fissi è il numero delle permutazioni di n-k elementi. Cosa c'è di complicato..? Oppure non ho capito?

[ilario991]

Vediamo se riesco a spiegarmi meglio...
Una permutazione P[1..n] di dimensione n è una sequenza nella quale ciascun numero intero da 1 a n compare una e una sola volta. Esempi di permutazioni sono le due sequenze 1,4,3,5,2 (n=5) e 3,2,1 (n=3) mentre la sequenza 1,2,3,5,1 (n=5) non è una permutazione poiché il numero 1 compare due volte.

L'intero j si definisce punto fisso della permutazione P se vale P[j] = j, dove 1 <= j <= n. Ad esempio, nella permutazione 1,4,3,5,2 ci sono due punti fissi, 1 e 3, mentre la permutazione 5,4,3,2,1 non ha alcun punto fisso.

Io devo stabilire quante permutazioni di dimensione n hanno esattamente k punti fissi

Esempi:
1) N = 5, K = 2 Perm con K punti fissi = 20
2) N = 9, K = 0 Perm con K punti fissi = 133496

[Umby2]

Ne abbiamo discusso QUI

Controlla un po'....

[csrvb-votailprof]

"mate_92":Salve. Esiste una formula o un modo che permetta di trovare il numero di permutazioni di dimensione n che hanno esattamente k punti fissi? (senza generare tutte le permutazioni...)

PS: per punto fisso indento un permutazione in cui l'i-esimo elemento si trova in posizione i, cioè P = i

Per le permutazione con e senza punti fissi prova a controllare qui

http://www.silsismi.unimi.it/SILSISMI/I ... toria1.pdf