N-uple ordinate e n-uple non ordinate

Una sequenza di n elementi si dice, genericamente, n-upla (leggi: “ennupla”) (per n=2 si parlerà di “coppia”, per n=3 di “terna”, per n=4 di “quaterna”, per n=5 di “cinquina”, per n=6 di “sestina”, per n>6 di “sequenza di 7, 8, 9, … elementi”).
Quando in un’n-upla consideriamo “importante” l’ordine in cui gli elementi si susseguono, parleremo di n-upla “ordinata”, e la indicheremo con parentesi tonde:

( x₁,x₂,x₃…..x_n)

Quando consideriamo irrilevante l’ordine, parleremo di n-upla “non ordinata” e useremo le graffe:

{x₁,x₂,x₃…..x_n}

Per evitare equivoci, ribadiamo:
– Due n-uple ordinate vengono considerate distinte anche se hanno gli stessi elementi, qualora l’ordine di tali elementi cambi dall’una all’altra:

(a, o, i) ≠ (a, i, o) 

E per indicare che un’n-upla va pensata ORDINATA, si utilizzano le parentesi TONDE.
– Invece se due n-uple NON ORDINATE contengono gli stessi elementi, vengono considerate come un’unica n-upla, indipendentemente dall’ordine nel quale sono stati scritti gli elementi stessi, in quanto quest’ordine viene pensato come irrilevante:

{a, o, i} =  {a, i, o}

E per indicare che un’n-upla va pensata NON ORDINATA, si utilizzano le parentesi GRAFFE, ovvero l’ordinario simbolo per indicare un insieme: si sa che in un insieme non conta l’ordine nel quale si sceglie di elencare gli elementi.

ESEMPIO

Una compagnia di 5 ragazzi, Aldo (A), Bruno (B), Carlo (C), Dario (D) ed Ernesto (E), deve passare una notte in una stanza in cui ci sono solo 2 letti.
In quanti modi è possibile scegliere i due ragazzi che dormiranno nei letti? (gli altri tre si accontenteranno del sacco a pelo …)

Soluzione

E’ chiaro che in questo caso si tratta di contare il numero di coppie NON ordinate che è possibile costruire “pescando” dall’insieme {A, B, C, D, E}.
Coppie NON ordinate, perché evidentemente la scelta {C, E} e la scelta {E, C} andranno considerate “equivalenti”, “non distinte”, andranno “contate come una scelta sola”.
Per risolvere questo facile problema, e, soprattutto, per iniziare a familiarizzare con una “strategia di pensiero” che ci servirà ogniqualvolta avremo a che fare con “n-uple non ordinate”, procediamo nel modo che segue:

Facciamo (o immaginiamo di fare) un grafo che porti a costruire tutte le possibili coppie ORDINATE di ragazzi;
poi, prese due coppie ordinate “equivalenti” (perché contenenti gli stessi due ragazzi, ma in ordine scambiato), “le inglobiamo in una sola”, “le consideriamo come se fossero una sola”.
E’ chiaro che il numero di scelte possibili sarà dato da (5 ⋅ 4) / 2 =10 .
Il “fratto 2” si deve al fatto che “di due coppie equivalenti ne facciamo una sola”.

ESEMPIO

Supponendo che i ragazzi del problema precedente siano 7 (A, B, C, D, E, F, G) e i letti 3, in quanti modi può essere effettuata la scelta?

Soluzione

Evidentemente, basterà pensare a tutte le terne ORDINATE di ragazzi, poi raggruppare le terne equivalenti (=contenenti gli stessi elementi), perché se più terne contengono gli stessi elementi, noi ne vogliamo “fare una sola”.
Ma, presa una terna ordinata, ad esempio: la terna (A, D, E), QUANTE SONO le terne equivalenti ad essa?
Sono tante quanti sono i modi di mettere in fila 3 oggetti fissati, ossia sono 6 (comprendendo anche la terna di partenza):

(A, D, E); (A, E, D); (D, A, E); (D, E, A); (E, A, D); (E, D, A)

Pertanto la risposta al problema è il numero (7 ⋅ 6 ⋅ 5) / 6 = 35.

Ricapitoliamo il ragionamento.
Presa una terna ordinata, essa fa parte di una famiglia di 6 terne ordinate “equivalenti” fra loro (perché contengono gli stessi elementi, se pure in ordine diverso). Le terne ordinate equivalenti vengono “contate come una terna sola”.
Il totale di 7 ⋅ 6 ⋅ 5 terne ordinate viene così diviso per 6. Quindi, se ci sono 7 ragazzi, la scelta di quei 3 che dormiranno nei letti potrà essere effettuata in

(7 ⋅ 6 ⋅ 5) / 6 = 35  modi.

ESEMPIO

In una fabbrica con 25 operai, se ne devono sorteggiare 6 per la pulizia dello stabilimento.
Quanti sono i possibili esiti del sorteggio?

Soluzione

Ragioniamo dapprima sulle sestuple ordinate.

Queste sono 25⋅ 24 ⋅ 23⋅ 22⋅ 21 ⋅20 .
Bene. Noi però vogliamo “raggruppare” tutte le sestuple “equivalenti” (cioè, contenenti gli stessi operai, se pure in ordine diverso) per “farne una sola”,
per “farne un gruppo che verrà contato come un’unica sestupla”.
MA DATA UNA SESTUPLA, QUANTE SONO LE SESTUPLE ORDINATE AD ESSA EQUIVALENTI (COMPRESA QUELLA DI PARTENZA)?
EVIDENTEMENTE, SONO TANTE QUANTI I MODI CON CUI, DATI 6 OGGETTI, QUESTI POSSONO ESSERE ORDINATI (=MESSI IN FILA, O IN CODA).

E il calcolo delle permutazioni semplici ci dice che ciò può avvenire in 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 6! (leggi: “6 fattoriale”) modi diversi.
Pertanto, fissata una sestupla ordinata, essa fa parte di un gruppo di 6! sestuple equivalenti.
Il lungo elenco delle 25⋅24⋅ 23⋅ 22⋅ 21⋅ 20 sestuple ordinate di operai può essere così suddiviso in gruppi ciascuno dei quali contiene 6! sestuple. Ogni gruppo verrà contato come una sola sestupla non ordinata, per cui il numero delle sestuple non ordinate di operai sarà

25⋅24⋅ 23⋅ 22⋅ 21⋅ 20 / 6!

Conclusioni:

Se in un certo problema noi abbiamo considerato inizialmente tutte le n-uple ordinate, ma in realtà ci interessano le n-uple NON ordinate, dobbiamo pensare il nostro elenco di n-uple ordinate ripartito in tanti gruppi, avendo noi posto in ciascun gruppo tutte le n-uple “equivalenti” ad un’n-upla data (cioè, contenenti gli stessi elementi, se pure in ordine diverso).
Abbiamo così tanti gruppi, ciascuno formato da n! n-uple, e ciascun gruppo va contato “come se si trattasse di una sola n-upla”.
E’ chiaro allora che il numero totale delle n-uple ordinate andrà diviso per n!

Pubblicità