|
1.5 - n-uple ordinate e n-uple non ordinate
In tutti i problemi precedentemente considerati si trattava, in sostanza, di "pescare" da un insieme per "costruire" delle "sequenze di n elementi" (in una parola: "n-uple") con l'obiettivo finale di contare il numero di tali n-uple.
Le n-uple andavano pensate "ordinate", nel senso che occorreva tenere conto dell'ordine con cui gli elementi di una data n-upla si succedevano, in quanto due n-uple costituite dagli stessi elementi, ma posti in ordine diverso, andavano considerate distinte.
Abbiamo dunque avuto a che fare con coppie ORDINATE, con terne ORDINATE, quaterne ORDINATE, ecc.
Ad esempio: nel problema 1) andavano considerate distinte le due stringhe aio e oai, ossia le due terne (a, i, o) e (o, a, i); nell'esercizio 11) andavano considerati distinti i due messaggi AF ed FA, ossia le due coppie (A, F) ed (F, A).
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: Quando consideriamo irrilevante l’ordine, parleremo di n-upla "non ordinata" e useremo le graffe:
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: 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:
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.
|
1.6 - Il “terzo principio” del C.C.
|
|
q Problema 15 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 ...)
|
|
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" (supponiamo che i due letti siano identici e non siano uno più comodo dell'altro).
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 Il "fratto 2" si deve al fatto che "di due coppie equivalenti ne facciamo una sola".
Consideriamo ora quest’altro problema:
|
|
q Problema 16 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?
|
|
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
Ricapitoliamo il ragionamento. Qui sopra sono elencate tutte le possibili terne ordinate. 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 la
scelta di quei 3 che dormiranno nei letti potrà essere effettuata in |
|
q Problema 17 In una fabbrica con 25 operai, se ne devono sorteggiare 6 per la pulizia dello stabilimento. Quanti sono i possibili esiti del sorteggio?
|
|
Ragioniamo dapprima sulle sestuple
ordinate. Queste sono Te le immagini, queste sestuple ordinate, tutte scritte una dopo l'altra? Sono veramente tantissime!
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 Secondo Principio del Calcolo Combinatorio ci dice che ciò può avvenire in
Pertanto, fissata una sestupla ordinata, essa fa parte di un gruppo di 6! sestuple equivalenti.
Il lungo elenco delle 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à
|
|
TERZO PRINCIPIO GENERALE DEL C.C. (CONSEGUENZA DEL PRIMO E DEL SECONDO)
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!
|