Una permutazione, detta anche “numero di disposizione” o “ordine”, è un riordinamento degli elementi di una lista S ordinata in una corrispondenza uno a uno con S stessa. Il numero di permutazioni su un insieme di n elementi è dato da n! (n fattoriale; Uspensky 1937, p. 18). Per esempio, ci sono 2!=2-1=2 permutazioni di {1,2}, cioè {1,2} e {2,1}, e 3!=3-2-1=6 permutazioni di {1,2,3}, cioè {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, e {3,2,1}, e {3,2,1}. Le permutazioni di una lista possono essere trovate nel linguaggio Wolfram usando il comando Permutazioni [lista]. Una lista di lunghezza n può essere testata per vedere se si tratta di una permutazione di 1, …, n nel linguaggio Wolfram usando il comando PermutationListQ[list].

Sedgewick (1977) riassume una serie di algoritmi per la generazione di permutazioni e identifica l’algoritmo di permutazione a cambiamento minimo di Heap (1963) come generalmente il più veloce (Skiena 1990, p. 10). Un altro metodo di enumerazione delle permutazioni è stato dato da Johnson (1963; Séroul 2000, pp. 213-218).

Il numero di modi per ottenere un sottoinsieme ordinato di k elementi da un insieme di n elementi è dato da

(Uspensky 1937, p. 18), dove n! è un fattoriale. Per esempio, ci sono 4!/2!=12 sottoinsiemi di {1,2,3,4}, cioè {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,2}, {3,4}, {4,1}, {4,2}, e {4,3}. I sottoinsiemi non ordinati contenenti elementi k sono noti come i sottoinsiemi k di un dato insieme.

Una rappresentazione di un cambiamento come risultato di cicli di fase è nuova (fino alla richiesta dei cicli). Un caso di decadimento ciclico è lo stadio {4,2,1,3} di {1,2,3,4}. Si intende (2)(143), relativo ai cicli di cambiamento di disgiunzione (2) e (143). Ci sono molte possibilità di scegliere la rappresentazione di una disintegrazione ciclica poiché (1) i cicli sono disgiunti e possono quindi essere determinati in qualsiasi richiesta, e (2) qualsiasi perno di un dato ciclo indica un ciclo simile (Skiena 1990, p. 20). In questo modo, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314) e (2)(143) rappresentano tutti un cambiamento simile.

Un’altra documentazione che riconosce espressamente le posizioni coinvolte dai componenti quando l’utilizzo di un cambiamento su n componenti utilizza un framework 2×n, dove la linea primaria è (123…n) e la linea successiva è la nuova linea di azione. Per esempio, la modifica che commuta i componenti 1 e 2 e fissa 3 sarebbe composta come

Qualsiasi permutazione è anche un prodotto di trasposizione. Le permutazioni sono comunemente indicate in ordine lessicografico o di trasposizione. Esiste una corrispondenza tra una permutazione e un paio di giovani tableaux noti come corrispondenza Schensted.

Il numero di permutazioni errate di n oggetti è [n!/e] dove [x] è la funzione intera più vicina. Una permutazione di n oggetti ordinati in cui nessun oggetto si trova al suo posto naturale si chiama squilibrio (o, a volte, permutazione completa) e il numero di tali permutazioni è dato dal sottofattoriale !n.

Utilizzo di

 (x+y)^n=somma_(r=0)^n(n; r)x^(n-r)y^r  

(3)

con x=y=1 dà

 2^n=somma_(r=0)^n(n; r),           

(4)

quindi il numero di modi per scegliere 0, 1, …, o n alla volta è 2^n.

L’insieme di tutte le permutazioni di un insieme di elementi 1, …, n può essere ottenuto utilizzando la seguente procedura ricorsiva

 1 2; / ; 2 1            

(5)

 1  2 3;     / ; 1 3 2 ; /    ; 3 1 2 ; |     ; 3 2 1 ; \    ; 2 3 1 ; \     ; 2  1 3            

(6)

Si considerino le permutazioni in cui non si verificano coppie di elementi consecutivi (cioè successioni in aumento o in diminuzione). Per n=1, 2, … elementi, i numeri di tali permutazioni sono 1, 0, 0, 0, 2, 14, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Lasciate che l’insieme dei numeri interi 1, 2, …, N sia permuto e che la sequenza risultante sia divisa in serie crescenti. Indicare la lunghezza media dell’ennesima corsa mentre N si avvicina all’infinito, L_n. I primi valori sono riassunti nella seguente tabella, dove e è la base del logaritmo naturale (Le Lionnais 1983, pp. 41-42; Knuth 1998).

nL_nOEISapprossimativo

1e-1A091111311              .7182818…

2e^2-2eA0911321           .9524…

3e^3-3e^2+3/2eA0911331          .9957…