permutazioni di quattro elementi come codice di Lehmer
La settimana scorsa abbiamo visto come si scrive
la base fattoradicale. Un paio dei miei ventun lettori si è chiesto come mai si usa anche la posizione relativa a 0!, che tanto è sempre 0 e quindi non porta informazione. In effetti potete trovare anche la rappresentazione senza questa cifra; ma ho preferito lasciarla per poter ampliare il conto ai numeri frazionari. L’estensione ha comunque qualche problema, perché (-1)!, (-2)! e così via non sono definiti; quello che si fa in pratica è usare gli inversi dei fattoriali, 1/1, 1/2, 1/6, 1/24, …, 1/
n!, …; chiaramente anche la prima cifra dopo la virgola è sempre zero, e quindi se avete proprio bisogno di spazio potete toglierla insieme alla cifra immediatamente a sinistra. Basta che avvisiate. Già che ci sono, aggiungo un’altra notazione: come potete immaginare, numeri molto grandi (o numeri frazionari molto lunghi) possono usare cifre maggiori di 10. Per evitare di inventare simboli, si possono usare i numeri in base 10 e separare le “cifre” con un “:”; pertanto 2441010
! si può anche scrivere come 2:4:4:1:0:1:0
!.
La conversione in base fattoradicale permette anche di numerare in ordine intelligente le permutazioni di n elementi. Qual è per esempio la 2023-ma permutazione di sette elementi? Scriviamo gli elementi come {0,1,2,3,4,5,6} e leggiamo da sinistra a destra 2441010!. La prima cifra è un 2; contiamo fino a due (partendo da zero, qui siamo informatici più che matematici) e tiriamo fuori il numero trovato, che è 2. I nostri elementi restano quindi {0,1,3,4,5,6}. Proseguiamo in questo modo: dalla nuova lista contiamo da 0 a 4, troviamo 5 e lasciamo {0,1,3,4,6}; poi prendiamo 6 e lasciamo {0,1,3,4}, prendiamo 1 e lasciamo {0,3,4}, prendiamo 0 e lasciamo {3,4}, prendiamo 4 e lasciamo {3} e infine prendiamo 3. (Visto che avere la posizione zero può servire?). Mettendo insieme i numeri otteniamo la permutazione {2,5,6,1,0,4,3). L’unicità della rappresentazione fattoradicale ci assicura che in questo modo troveremo tutte e sole le permutazioni possibili.
Un altro esempio di uso dei numeri fattoradicali (stavolta senza la cifra finale) è dato dai codici di Lehrer; come vedete nella pagina di Wikipedia relativa, questi codici tanto per cambiare codificano le permutazioni di n elementi, ma questa volta lo fanno per mezzo delle inversioni, cioè gli scambi di due elementi. Se date un’occhiata alla tabella, le colonne le r consistono proprio nei numeri fattoradicali scritti da destra a sinistra, e la somma delle “cifre” è proprio il numero di inversioni necessarie per partire dalla permutazione di base {1,2,3,4} per arrivare a quella voluta.
Evelyn Lamb afferma che questo può servire anche per il problema dei bagni chimici ai festival musicali britannici, come da video di Numberphile; a me non sembra, ma tant’è. Ad ogni modo, buon divertimento!
(figura di Tilman Piesk da Wikimedia Commons, CC-BY-SA 3.0)
Dopo una serie di libri scritti per Hoepli, Chinnici è passato a Codice per questo suo nuovo libro. (Sì, fa tanto calciomercato… Peccato che tranne che in rarissimi casi soldi non ne arrivino). In questo testo l’autore racconta gli sforzi durati più di un secolo per riuscire a trovare un modello funzionante a livello atomico prima e subatomico poi di come è composta la materia. Troverete ovviamente molti nomi e molte descrizioni di esperimenti: ma quello che ho trovato più interessante è la descrizione di quello che succede a livello di struttura atomica. In pratica abbiamo un bel bigino di fisica che mi ha permesso di capire meglio quello che avevo appiccicato all’università per passare gli esami: e scusate se è poco! Testo insomma consigliato per chi non è semplicemente interessato a una storiella ma vuole capirci qualcosa in più.
Ricordate 
Ho finalmente trovato il motivo per cui Facebook e Instagram hanno introdotto l’
