Sia $S$ un insieme di cardinalità $n$ e sia $S^r{\bf =}S\times\ldots\times S$ il prodotto cartesiano di $r$ copie di $S$. Un elemento di $S^r$ è una sequenza ordinata $(a_1,\dots,a_r)$ con $a_i\in S$ $\ \forall\ $ $i{\bf =}1,\dots, r$ non necessariamente tutti distinti.
Definizione. Se $r\in \mathbb{N}$, un elemento di $S^r$ si dice disposizione (con ripetizioni) di $r$ elementi di $S$ (di ordine $r$).
Esempio. Le disposizioni di $A= \{a, b, c\}$ di ordine 1 sono $(a)$, $(b)$ e $(c)$; quelle di ordine 2 sono $(aa)$, $(ab)$, $(ba)$, $(ac)$, $(ca)$, $(bb)$, $(bc)$, $(cb)$ e $(cc)$; quelle di ordine 3 sono $(aaa)$, $(aab)$, $(aba)$, $(baa)$, $(aac)$, $(aca)$, $(caa)$, $(abc)$, $(acb)$, $(bca)$, $(cab)$, $(cba)$, $(bac)$, $(abb)$, $(bab)$, eccetera.
Proposizione. Se $\vert S\vert {\bf =}n$, allora $\vert S^r\vert {\bf =}n^r$ $\forall\ r\in \mathbb{N}$.
Dimostrazione. Per induzione, applicando il principio di moltiplicazione. $\spadesuit$
Osservazioni
Una disposizione è una sequenza ordinata;
$n^r$ è anche il cardinalità dell'insieme delle funzioni $f:\{1,\dots, r\}\to S$, infatti si può stabilire una corrispondenza biunivoca tra $S^r$ e l'insieme di queste funzioni associando alla disposizione $(s_1,\dots ,s_r)$ la funzione $f$ tale che $f(j){\bf =}s_j$ $\ \forall\ $ $j{\bf =}1,\dots, r$;
$n^r$ è anche il numero di modi in cui si possono estrarre $r$ oggetti distinti da un'urna contenente $n$ oggetti, rimettendo ogni volta nell'urna l'oggetto estratto (estrazioni con reinbussolamento).
Definizione. Dato un insieme $S$, l'insieme delle parti di $S$, denotato con $\mathcal{P}(S)$, è l'insieme di tutti i sottoinsiemi di $S$:
$$ \mathcal{P}(S ){\bf =}\{A\ :\ A\subseteq S\}\ \hbox{.} $$Esempio. Dato un insieme $S$ di cardinalità $n$, calcoliamo $\vert\mathcal{P}(S)\vert$: ordiniamo gli elementi di $S$ in un modo qualsiasi $a_1,\dots, a_n$ e a ogni insieme $A\subseteq S$ facciamo corrispondere una sequenza ordinata
$$ \ell_A {\bf =} (m_1,\dots, m_n)\in\{ 0,1\}^n\ \hbox{,} $$tale che se $a_j\in A$ si pone $m_j{\bf =}1$, mentre se $a_j\not\in A$ si pone $m_j{\bf =}0$. Si ha una corrispondenza biunivoca tra i sottoinsiemi di $S$ e $\{ 0,1\}^n$, quindi
$$ \vert\mathcal{P}(S)\vert {\bf =} \vert\{ 0,1\}^n\vert {\bf =} 2^n\ \hbox{.} $$Definizione. Se $n\geq 1$ è un intero positivo, si dice fattoriale di $n$ il numero $n!{\bf =}n\cdot (n{\bf -}1)\cdot (n{\bf -}2)\cdot\ldots\cdot 2\cdot 1$. Per convenzione si pone $0!{\bf =}1$.
Osservazione. Per $n\geq 1$ risulta $n!{\bf =}n(n{\bf -}1)!$.
Definizione. Sia $S$ un insieme di cardinalità $n$. Una disposizione di $r$ elementi di $S$ si dice semplice se ogni elemento di $S$ compare al più una volta (perciò deve essere $r\leq n$).
Esempio. Le disposizioni semplici di $A= \{a, b, c\}$ di ordine 1 sono $(a)$, $(b)$ e $(c)$; quelle di ordine 2 sono $(ab)$, $(ba)$, $(ac)$, $(ca)$, $(bc)$ e $(cb)$; quelle di ordine 3 sono $(abc)$, $(acb)$, $(bca)$, $(cab)$, $(cba)$ e $(bac)$.
Proposizione. L'insieme $\mathcal{D}_r^n$ delle disposizioni semplici di $r$ elementi di $S$ è un sottoinsieme di $S^r$ di cardinalità
$$ {n!\over (n{\bf -}r)!}{\bf =}n(n{\bf -}1)\ldots (n{\bf -}r{\bf +}1)\ \hbox{.} $$ Dimostrazione. >Osservazioni
$\vert\mathcal{D}_r^n\vert$ è anche la cardinalità dell'insieme delle funzioni $f:\{1,\dots, r\}\to S$ iniettive;
$\vert\mathcal{D}_r^n\vert$ è anche il numero di modi in cui si possono estrarre $r$ oggetti distinti da un'urna contenente $n$ oggetti, senza rimettere l'oggetto estratto nell'urna (estrazioni senza reinbussolamento).
Esempio. Quante formazioni può scegliere l'allenatore di una squadra di calcio che ha a disposizione $18$ giocatori? Una formazione è fissata scegliendo una sequenza ordinata di $11$ giocatori distinti tra i $18$ disponibili. In altri termini, si tratta di enumerare le disposizioni semplici a $11$ a $11$ dei giocatori e abbiamo $18!/7!$ ${\bf =}$ $18\cdot 17\cdot\ldots\cdot 8$ possibili formazioni.
Definizione. Una disposizione semplice di $n$ elementi dell'insieme $S$ (ovvero di tutti i suoi elementi) si dice permutazione (semplice) degli elementi di $S$.
Esempio. Le permutazioni semplici degli elementi di $A= \{a, b, c\}$ sono $(abc)$, $(acb)$, $(bca)$, $(cab)$, $(cba)$ e $(bac)$.
Proposizione. L'insieme delle permutazioni degli elementi di un insieme $S$ di cardinalità $n$ ha cardinalità $n!$.
Dimostrazione. Si applica la proposizione precedente con $r{\bf =}n$: $\vert\mathcal{D}_r^n\vert {\bf =} n!/0! {\bf =}n!$. $\spadesuit$