Combinazione

Da Wikipedia, l'enciclopedia libera.

Nota disambigua - Se stai cercando il concetto di combinazione in enigmistica, vedi combinazione enigmistica.

Se n ed m sono interi positivi, l'espressione combinazione di n elementi a m a m o anche combinazione di n elementi di classe m viene usata nel tradizionale calcolo combinatorio per indicare un raggruppamento di m oggetti tratti da un insieme di n, intendendo che due raggruppamenti differiscono se presentano qualche elemento diverso ma non si distinguono se presentano gli stessi elementi in ordini diversi. Invece del termine combinazione si usano anche i termini combinazione semplice e combinazione senza ripetizioni. Questa nozione quindi si riconduce a quella di sottoinsieme di m elementi facente parte di un insieme di cardinalità n.

Per collegare questo termine alla odierna combinatoria conviene fare riferimento alla seguente definizione. Si considera un insieme S di n elementi ed un suo ordinamento totale che caratterizziamo con l'infisso $\,\leq\,$ e si considera un intero naturale m non superiore ad n: $0\leq m\leq n$ . Si dice combinazione di elementi di S di lunghezza m ogni sequenza di m elementi di S che sia crescente per la relazione $\,\leq\,$ .

Ad esempio, le combinazioni di lunghezza 4 degli elementi di {a, b, c, d, e, f} considerati nel tradizionale ordine alfabetico sono:
abcd, abce, abcf, abde, abdf, abef, acde, acdf, acef, adef,
bcde, bcdf, bcef, bdef, cdef.
Si osserva che le precedenti sequenze sono presentate nell'ordine lessicografico.

Le suddette combinazioni forniscono pratiche rappresentazioni dei sottoinsiemi di 4 elementi dell'insieme. Passando alle funzioni indicatrici di tali sottoinsiemi si arriva alle sequenze binarie di lunghezza 6 e peso 4, sequenze che equivalgono come contenuto informativo alle precedenti e che conviene elencare esplicitamente:
111100, 111010, 111001, 110110, 110101, 110011, 101110, 101101, 101011, 100111,
011110, 011101, 011011, 010111, 001111.

Si osserva che queste sequenze sono presentate in ordine antilessicografico. Tra combinazioni di n elementi di lunghezza m e sequenze binarie di lunghezza n e peso m si ha dunque un criptomorfismo: è equivalente operare con le combinazioni o con le sequenze binarie. Questa osservazione può essere utile a chi inizia a studiare la programmazione.

Il numero complessivo di combinazioni di n elementi a m a m si indica con $C n, m$ e si ottiene dal numero delle disposizioni di n oggetti di lunghezza m $D n, m$ e dal numero delle permutazioni di m oggetti $P m$ nel modo seguente:

$C_{n, m} = \frac {\mbox{numero disposizioni di n elementi m a m}} {\mbox {numero permutazioni di m elementi}} = \frac {D_{n, m}} {P_{m}} = \frac{n!}{m! (n-m)!}$