Disposizioni semplici e permutazioni
Consideriamo un insieme con un numero finito di elementi, ad esempio
\[A=\{1,2,3,4\}\, (*)\]
Si dice disposizione semplice (cioè senza ripetizioni) di k elementi su n dati un sottoinsieme ordinato di A costituito da k elementi. L'insieme delle disposizioni di 2 elementi tra i 4 dati di A (*) è
\[D=\{12,13,14,21,23,24,31,32,34,41,42,43\}\]
(per comodità uso la notazione 12 per indicare il sottoinsieme ordinato (1,2), dunque 12 è diverso da 21).
Il numero di disposizioni semplici di k elementi su n dati è
\[ D_{n,k}=n(n-1)(n-2)\cdots (n-k+1) \]
Nell'esempio precedente ho n=4, k=2, dunque 4(3)=12 (si osservi che n-k+1=4-2+1=3), che effettivamente è il numero di elementi di D.
Un disposizione semplice di n elementi su n dati viene detta permutazione di n elementi. Il numero di permutazioni di n elementi è
\[ P_n=n!=n(n-1)(n-2)\cdots 1 \]
Il simbolo n! viene detto fattoriale di n. Il numero di permutazioni degli elementi di A (*) è 4!=4(3)(2)(1)=24. Effettivamente l'insieme delle permutazioni di A è
\[ P= \{1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431,\] \[3124, 3142, 3214, 3241, 3412, 3421,4123, 4132, 4213, 4231, 4312, 4321\}\]
Per comprendere la formula osserviamo che nella prima posizione posso scegliere uno degli elementi tra 1, 2, 3 e 4. Nella seconda posizione posso scegliere solo uno dei tre rimanenti elementi. Quindi nella terza solo un dei due rimanenti e nella quarta sarò obbligato a prendere l'unico restante.
Si può osservare come il numero di permutazioni (e anche di disposizioni) cresce molto velocemente al crescere di A.
Se volessimo conoscere il numero di possibili mescolamenti delle carte da gioco italiane, dovremmo andare a calcolare il numero delle loro permutazioni che è
\[ 40!=815915283247897734345611269596115894272000000000 \]
per il calcolo puoi usare pari-gp.
Vedi anche disposizioni con ripetizioni e combinazioni.