permutazione
permutazione
Concetto chiave del calcolo combinatorio. Dato un insieme di n elementi distinti, si dicono p. semplici o senza ripetizione tutte le sequenze diverse degli n elementi che si possono formare modificando il loro ordine. Per es., date 4 lettere distinte dell’alfabeto come A, M, O, R, tutte le parole e le sigle (tutti gli anagrammi anche privi di senso compiuto) che si possono declinare modificando l’ordine delle 4 lettere. Il numero di tali p. indicato dalla notazione Pn è pari a n! (che si legge ‘n fattoriale’ o ‘fattoriale di n’), simbolo il cui significato è quello di prodotto dei primi n numeri naturali (interi positivi) n!=n·(n−1) … 3·2·1. Nel nostro esempio, vi sono 4!=4·3·2·1=24 permutazioni. Posto 0!=1, vale per ogni n intero positivo la n!= n·(n−1)!. ● Di particolare interesse è il sottoinsieme delle p. circolari (o cicliche). Esse consistono nel considerare un ordinamento arbitrario per gli elementi dell’insieme (seme) e nel sostituire poi a ognuno di questi il seguente e all’ultimo il primo. Nell’esempio, esse (includendo l’ordinamento di partenza) formano un insieme di 4 p.: dal seme AMOR seguono, infatti, MORA, ORAM, RAMO. Se gli n elementi non sono tutti distinti ma ve ne sono n1 elementi di un primo tipo, n2 di un secondo tipo, nh di un h-esimo tipo, con n1+ n2 +…+ nh≤n, tutte le possibili sequenze diverse si dicono p. con ripetizione. Il loro numero, identificato dal simbolo Pn1,n2,…,nh si ottiene sfruttando la Pn1,n2,…,nh ·n1!n2!...,nh!=n!, dalla quale immediatamente Pn1,n2,…,nh=n!/(n1!·n2!·...·nh!). Come esempio si consideri il numero dei possibili anagrammi (p. con ripetizione) delle 5 lettere I, V, V, Z, Z, in cui vi sono n1=2 lettere V, e n2=2 lettere Z. Esso è pari a 5!/(2!·2!) =30.