Punti fissi Permutazioni

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
zip92
Messaggi: 6
Iscritto il: 19 nov 2009, 15:27

Punti fissi Permutazioni

Messaggio da zip92 »

Devo risolvere questo problema

Codice: Seleziona tutto

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.

È interessante stabilire quante permutazioni di dimensione n hanno esattamente k punti fissi. Per esempio, dato n=3, abbiamo sei permutazioni, dove tra parentesi indichiamo il rispettivo numero di punti fissi: 1,2,3 (3); 1,3,2 (1); 2,1,3 (1); 2,3,1 (0); 3,1,2 (0); 3,2,1 (1). In tale situazione, non ci sono permutazioni con k=2 punti fissi; per k=1, ne abbiamo tre, e così via.

Scrivere un programma che, ricevuti due numeri n e k, trova il numero di permutazioni di dimensione n che hanno esattamente k punti fissi.
Domanda: esiste una formula o un modo(senza generare tutte le permutazioni) che mi dica quante permutazioni n hanno esattamente k punti fissi?[/code]
Tux94
Messaggi: 2
Iscritto il: 08 lug 2011, 23:33

Re: Punti fissi Permutazioni

Messaggio da Tux94 »

Scrivere un programma che, ricevuti due numeri n e k, trova il numero di permutazioni di dimensione n che hanno esattamente k punti fissi.
se ti può essere ancora utile, puoi scegliere in $ n \choose {k} $ modi diversi i punti fissi, e poi in !(n-k) (subfattoriale) modi i punti non fissi.
lerks
Messaggi: 10
Iscritto il: 19 nov 2009, 18:22

Re: Punti fissi Permutazioni

Messaggio da lerks »

http://en.wikipedia.org/wiki/Rencontres_numbers

Puoi trovare in O(N) il numero di dismutazioni di N-K elementi (cioe' le permutazioni con nessun punto fisso) e poi il numero che cerchi e' $ \binom{n}{k} $ volte questo valore.

In alternativa puoi calcolare $ \frac{n!}{e} $ e arrotondarlo per eccesso se n e' pari o per difetto se n e' dispari.

PS: uno degli esempi e' sbagliato. $ 5,4,3,2,1 $ ha un punto fisso: 3.
Rispondi