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.