CALCOLO COMBINATORIO

Cap. 1 - STRATEGIE DI PENSIERO

INDICE

1.1 - Premessa

1.2 – Il “primo principio” del C.C.

1.3 – Esercizi sul “primo principio”

1.4 – Il “secondo principio” del C.C.

1.5 – n-uple ordinate e n-uple non ordinate

1.6 – Il “terzo principio” del C.C.

1.7 – Esercizi

1.1 - Premessa

Per "calcolo combinatorio" (C.C.) si intende una branca della Matematica che studia i modi di raggruppare ed ordinare oggetti presi da un insieme assegnato, con l'obiettivo finale di contare il numero dei possibili raggruppamenti od ordinamenti.

Il C.C. risulta spesso antipatico e “indigesto” agli studenti. Perché?

Perché spesso viene presentato dai libri di testo in maniera troppo frettolosa e “brutale”: si passa immediatamente ad una trattazione astratta e vengono proposte immediatamente delle formule.

In queste pagine tento di dare invece un’introduzione AMICHEVOLE al C.C.

· Nel capitolo 1 faremo pochissima teoria e molti esercizi.

Utilizzando solamente un metodo grafico (il "grafo ad albero", detto anche "diagramma ad albero" o semplicemente "albero") e due o tre "principi generali", saremo in grado, senza pensare a formule precostituite e senza aver adottato una terminologia specifica, di risolvere problemi apparentemente molto complicati - ma, in genere, curiosi e divertenti.

· Nel capitolo 2 passeremo invece ad una trattazione astratta e alle formule, ma l’aver svolto preliminarmente il capitolo 1 renderà il discorso (almeno spero!) molto più chiaro e comprensibile.

· Nel capitolo 3 presenteremo qualche applicazione ai grandi “giochi iniqui” del Lotto e del Superenalotto

· Nel Capitolo 4 ci occuperemo di un paio di argomenti complementari.

1.2 – Il “primo principio” del C.C.

q Problema 1):

quante parole di tre lettere possono essere scritte utilizzando solo le cinque vocali? (es.: aoe, iii, uaa...)

Per rispondere a questa domanda, e soprattutto per acquisire un metodo di ragionamento che ci servirà in molti altri problemi di questo tipo, pensiamo di scrivere EFFETTIVAMENTE tutte queste parole di tre lettere.

Scriviamole, poi le conteremo.

Evidentemente, per evitare confusione, omissioni o ripetizioni, dovremo seguire un certo ordine, un certo schema nel "mettere giù" tutte queste parole.

Per esempio, potremmo stilare un "grafo ad albero" come il seguente:

La stesura del grafo è partita dall'idea di considerare innanzitutto le possibilità che abbiamo per la prima lettera della parola.

· Evidentemente, per la prima lettera abbiamo 5 possibilità

che sono quelle elencate in prima colonna (a, e, i, o, u).

· Poi, ad ognuna di queste 5 possibilità si possono abbinare 5 possibilità per la seconda lettera della parola.

In totale, per le prime due lettere, abbiamo 5 ∙ 5 = 25 possibilità (aa, ae, ai, ao, au; ea, …).

· E ad ognuna di queste 5 ∙ 5 possibilità per le prime due lettere, potremo abbinare 5 possibilità per la terza lettera, per cui in definitiva avremo 5 ∙ 5 ∙ 5 = 125 possibilità (aaa, aae, aai, …).

Risposta: le parole di tre lettere costruibili utilizzando solo le vocali sono 125.

q Problema 2)

quante sono le parole di 7 lettere costruibili utilizzando tutte le 21 lettere dell'alfabeto italiano?

Pensiamo ancora ad un "albero" come il precedente. Ovviamente, non staremo a completarlo! Vogliamo solo fissare bene in mente le modalità con cui il diagramma potrebbe, avendo tempo e pazienza, essere compilato.

[grafo ad albero (non è qui, ma è nella tua mente… )]

Risposta: le parole di 7 lettere che si possono costruire con le 21 lettere dell'alfabeto italiano sono 21⁷.

(Se calcoli questo numero con la macchinetta, troverai che supera 1 miliardo e 800 milioni).

q Problema 3)

quante parole di tre lettere possono essere scritte utilizzando solo le cinque vocali, ma senza ripetizione? (es.: aoe, uao, aei, MA NON iii, uaa, eie, ...)

E' chiaro che l'albero relativo al probl. 1) si modificherà perdendo qualche ramo; immagina di tracciare il nuovo albero, o, meglio, traccialo realmente, sul tuo quaderno!

Risposta: 5 ∙ 4 ∙ 3 = 60

Ricapitoliamo il ragionamento:

abbiamo

5 possibilità per la prima lettera della parola;

a ciascuna di queste 5 possibilità sono abbinate

4 possibilità per la seconda lettera;

(quindi, per le prime due lettere abbiamo 5 ∙ 4 possibilità),

e a ciascuna di queste 5 ∙ 4 possibilità sono abbinate

3 possibilità per la terza lettera.

In definitiva, abbiamo 5 ∙ 4 ∙ 3 possibili parole.

Adesso siamo in grado di risolvere il seguente

q Problema 4)

Quante sono le parole di 7 lettere costruibili utilizzando tutte le lettere dell'alfabeto italiano, ma “senza ripetizione” cioè col vincolo di non utilizzare una lettera più di una volta in una stessa parola?

Risposta: 21∙20 ∙19 ∙18 ∙17 ∙16 ∙15

q Problema 4’)

Quante sono le parole di 7 lettere costruibili utilizzando tutte le lettere dell'alfabeto italiano, ma “senza consecutività”?(Quindi, “abbcdef” sarebbe vietata, ma andrebbe invece bene “abababa”)

Risposta: 21∙20 ∙20 ∙20 ∙20 ∙20 ∙20

La risoluzione "col metodo del diagramma ad albero" dei problemi 1) ... 4’) mostra che vale il seguente

PRIMO PRINCIPIO GENERALE DEL CALCOLO COMBINATORIO

Se una scelta può essere fatta in r modi diversi, per ciascuno dei quali una seconda scelta può essere effettuata in s modi diversi, e, per ciascuno dei modi in cui si sono compiute le prime due scelte, una terza scelta può essere effettuata in t modi diversi ecc., allora la successione di tutte le scelte può essere compiuta in r·s·t ... modi diversi

(traduzione dal testo americano "Introduction to Finite Maths" di Kemeny-Snell-Thompson)

1.3 – Esercizi sul “primo principio”

ESERCIZI (risposte alla fine)

5)

In una compagnia di quattro amici (Roberto, Paolo, Enzo, Walter) bisogna scegliere un capo e un vice.

In quanti modi può essere effettuata la scelta?

Obbligatorio tracciare il diagramma ad albero (per brevità, usare solo le iniziali dei nomi!)

6)

Per andare da una città A ad una città B ci sono quattro strade diverse.

In quanti modi è possibile "fare un giro" da A fino a B e ritorno?

E se al ritorno non si vuole ripercorrere la stessa strada dell'andata?

Obbligatorio un diagramma, per ciascuno dei due casi.

7)

In un'urna ci sono quattro palline, contrassegnate coi numeri 1, 2, 3, 4.

Se si effettuano tre estrazioni, quanti sono gli esiti possibili, tenendo conto dell’ordine con cui vengono estratte le palline? (nel senso che, ad es., l’esito 1-2-3 sarà considerato distinto dall’esito 2-1-3)

Considerare separatamente i due casi:

a) dopo aver estratto una pallina, la si reintroduce (si dice: "la si reimbussola") nell'urna prima di effettuare l'estrazione successiva

b) le estrazioni avvengono una dopo l'altra, ma senza reimbussolamento.

Obbligatorio il diagramma ad albero, sia per il caso a) che per il caso b).

[Ci occuperemo successivamente del problema di contare gli esiti possibili, qualora si voglia considerare irrilevante l’ordine di estrazione delle palline, e quindi, per esempio, gli esiti 1-2-3 e 2-1-3 NON vengano pensati come distinti]

8)

In un plotone di 25 militari bisogna scegliere:

un addetto alle pulizie;

un addetto alle cucine;

un soldato che monti di sentinella.

In quanti modi è possibile effettuare la scelta?

9)

Quante parole di 5 lettere si possono scrivere utilizzando liberamente le 21 lettere dell'alfabeto italiano, con possibilità di ripetizione di una lettera ma col vincolo di evitare le 'doppie', cioè due (o più) lettere uguali consecutive? (Es. parole ammissibili: atoim, qtatq, eoeoe... Non ammissibili: aggfe, pppio...)

10)

Per giocare al totocalcio, com’è noto, bisogna scegliere un pronostico (che può essere 1, X o 2) per ciascuna delle 13 partite sulla schedina. Quante schedine diverse è possibile, teoricamente, compilare?

11)

La moglie di un carcerato, per poter parlare col marito anche al di fuori delle ore di colloquio coi parenti, ha concordato con lui un codice basato sull'uso di quattro bandierine: una Italiana, una Francese, una Americana e una del Milan.

Un messaggio può consistere nell'esposizione di una singola bandierina, oppure di due, o tre, o tutte e quattro le bandierine.

Nel caso il messaggio sia costituito da più bandierine, conta anche l'ordine in cui queste si susseguono da sinistra a destra.

Si domanda: quanti messaggi è possibile trasmettere con queste modalità?

12)

Sappiamo che in ogni computer, la memoria è costituita da tanti "bit", essendo un "bit" un dispositivo fisico che può assumere due stati differenti (essere magnetizzato o non, essere attraversato da corrente o non).

Indicati convenzionalmente con "0" e "1" tali due stati fisici, diremo, in sostanza, che un bit è una "cella" di memoria che può assumere, di volta in volta, o il valore "0" o il valore "1".

Una sequenza di 8 bit forma il cosiddetto "byte".

a) Quante diverse "informazioni" può contenere un byte?

b) E quante informazioni diverse si potranno memorizzare in una sequenza di 10 bytes?

Tenendo conto che 2¹⁰ =10241000, dai un'approssimazione per difetto del numero trovato.

RISPOSTE AGLI ESERCIZI:

5) 4 ּ 3 = 12 modi 6) 4 ּ 4 = 16 modi; se però al ritorno non si vuole fare la stessa strada dell’andata, i modi possibili si riducono a 4 ּ 3 = 12 7a) 4 ּ 4 ּ 4 = 64 7b) 4 ּ 3 ּ 2 = 24 8) 25 ּ24 ּ23 9) 21 ּ20 ּ 20 ּ 20 ּ20 10) 3¹³ = 1594323

11)

4 messaggi con una sola bandierina;

4 ּ 3 = 12 messaggi con 2 bandierine;

4 ּ 3 ּ 2 = 24 messaggi con 3 bandierine;

4 ּ 3 ּ 2 ּ 1 = 24 messaggi con 4 bandierine.

Totale 4+12+24+24=64 possibili messaggi.

12)

a) 2⁸ = 256 b) 2⁸⁰ = (2¹⁰)^{8 =} 1024⁸ > 1000⁸ = (10³)⁸ = 10²⁴ = 1 milione di miliardi di miliardi

1.4 – Il “secondo principio” del C.C.

Consideriamo ora il seguente

q Problema 13)

Se 6 persone si vogliono mettere in fila da sinistra a destra (rispetto al fotografo) per una foto di gruppo, in quanti modi diversi possono farlo?)

Formulazione equivalente:

se 6 persone arrivano contemporaneamente ad uno sportello, in quanti modi diversi possono mettersi in coda?

Facile:

per scegliere il primo elemento della fila (o della coda), abbiamo 6 possibilità; in corrispondenza di ciascuna di queste 6 possibilità, abbiamo 5 possibilità per il secondo elemento; abbinate a queste 6·5 possibilità abbiamo 4 possibilità per il terzo elemento; per ciascuna di queste 6·5·4 possibilità abbiamo 3 possibilità per il quarto elemento ecc...

Risposta:

In totale, le 6 persone possono mettersi in fila (o in coda) in

6·5·4·3·2·1 = 6! (leggi: "6 fattoriale") modi diversi.

SECONDO PRINCIPIO GENERALE DEL C.C. (CONSEGUENZA DEL PRIMO)

Dati n oggetti, essi si possono "mettere in fila" (o “mettere in coda”, o “mettere in colonna”) in n! (leggi: “n fattoriale”) modi diversi, dove il simbolo n! indica il numero n·(n-1)·(n-2)· … ·3·2·1.

Infatti, per la scelta del primo oggetto della fila abbiamo n possibilità;

a ciascuna di queste n possibilità sono abbinate (n-1) possibilità di scelta per il secondo oggetto della fila;

ad ognuna delle n·(n-1) possibilità per i primi due oggetti corrispondono (n- 2) possibilità di scelta per il terzo oggetto della fila;

... ;

in totale, quindi, n oggetti possono essere ordinati (=messi in fila, o in coda, o in colonna) in

n·(n-1)·(n-2)· … ·3·2·1 = n! modi diversi.

q Problema 14)

Quanti sono i possibili anagrammi della parola "mora" (contando anche quelli che non hanno significato nella lingua italiana)? Obbligatorio il grafo ad albero.

Risposta …

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 avente un certo numero k di elementi, per "costruire" tutte le possibili "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.

Ad esempio:

Nel problema 1) andavano considerate distinte le due parole aio e oai, ossia le due terne (a, i, o) e (o, a, i);

nell'eserc. 11) andavano considerati distinti i due messaggi AF ed FA, ossia le due coppie (A, F) ed (F, A).

In una parola, nei problemi fin qui visti ci siamo occupati di coppie ORDINATE, o di terne ORDINATE, ecc., insomma: di n-uple ORDINATE.

Una sequenza di n elementi si dice, genericamente, n-upla

(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 6, 7, 8, ... 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_n)

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

{ 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]

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 aggiusteranno col 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 (5 · 4)/2 = 10. 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 quate 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.

(ABC)(ABD)(ABE)(ABF)(ABG)(ACB)(ACD)(ACE)(ACF)(ACG)(ADB)(ADC)(ADE)(ADF)(ADG)(AEB)

(AEC)(AED)(AEF)(AEG)(AFB)(AFC)(AFD)(AFE)(AFG)(AGB)(AGC)(AGD)(AGE)(AGF)(BAC)(BAD)

(BAE)(BAF)(BAG)(BCA)(BCD)(BCE)(BCF)(BCG)(BDA)(BDC)(BDE)(BDF)(BDG)(BEA)(BEC)(BED)

(BEF)(BEG)(BFA)(BFC)(BFD)(BFE)(BFG)(BGA)(BGC)(BGD)(BGE)(BGF)(CAB)(CAD)(CAE)(CAF)

(CAG)(CBA)(CBD)(CBE)(CBF)(CBG)(CDA)(CDB)(CDE)(CDF)(CDG)(CEA)(CEB)(CED)(CEF)(CEG)

(CFA)(CFB)(CFD)(CFE)(CFG)(CGA)(CGB)(CGD)(CGE)(CGF)(DAB)(DAC)(DEE)(DAF)(DAG)(DBA)

(DBC)(DBE)(DBF)(DBG)(DCA)(DCB)(DCE)(DCF)(DCG)(DEA)(DEB)(DEC)(DEF)(DEG)(DFA)(DFB)

(DFC)(DFE)(DFG)(DGA)(DGB)(DGC)(DGE)(DGF)(EAB)(EAC)(EAD)(EAF)(EAG)(EBA)(EBC)(EBD)

(EBF)(EBG)(ECA)(ECB)(ECD)(ECF)(ECG)(EDA)(EDB)(EDC)(EDF)(EDG)(EFA)(EFB)(EFC)(EFD)

(EFG)(EGA)(EGB)(EGC)(EGD)(EGF)(FAB)(FAC)(FAD)(FAE)(FAG)(FBA)(FBC)(FBD)(FBE)(FBG)

(FCA)(FCB)(FCD)(FCE)(FCG)(FDA)(FDB)(FDC)(FDE)(FDG)(FEA)(FEB)(FEC)(FED)(FEG)(FGA)

(FGB)(FGC)(FGD)(FGE)(GAB)(GAC)(GAD)(GAE)(GAF)(GBA)(GBC)(GBD)(GBE)(GBF)(GCA)(GCB)

(GCD)(GCE)(GCF)(GDA)(GDB)(GDC)(GDE)(GDF)(GEA)(GEB)(GEC)(GED)(GEF)(GFA)(GFB)(GFC)

(GFD)(GFE)

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 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.

q Esercizio proposto:

scrivi un programma Pascal che fornisca l’elenco di terne sopra riportato.

Problema 17)

in una classe di 25 alunni, si devono scegliere 6 "volontari" per un'ora di interrogazioni. In quanti modi può essere effettuata la scelta?

Ragioniamo dapprima sulle sestuple ordinate. Queste sono 25·24·23·22·21·20

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 ragazzi, se pure in ordine diverso) per "farne una sola", per "farne un gruppo che verrà contato come un'unica sestupla”.

MA DATA UNA SESTUPLA ORDINATA, QUANTE SONO LE SESTUPLE ORDINATE AD ESSA EQUIVALENTI (COMPRESA QUELLA DI PARTENZA)? EVIDENTEMENTE, SONO TANTE QUANTI I MODI CON CUI, DATI 6 OGGETTI, ESSI POSSONO ESSERE ORDINATI (=MESSI IN FILA, O IN CODA)

E il Secondo Principio del Calcolo Combinatorio ci dice che si hanno 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 ragazzi 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 ragazzi sarà (25·24·23·22·21·20)/ 6!

TERZO PRINCIPIO GENERALE DEL C.C. (CONSEGUENZA DEL PRIMO E DEL SECONDO)

Se in un certo problema noi abbiamo considerato inizialmente 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!

1.7 – Esercizi

ESERCIZI (risposte alla fine)

18)

Un mazzo da poker è formato da 32 carte. A ciascun giocatore se ne distribuiscono 5.

Quanti "giochi" diversi può teoricamente avere in mano un giocatore?

19)

In una compagnia di 20 ragazzi, per Carnevale 18 si vestiranno da "zombi".

In quanti modi è possibili scegliere quei 18? (ragiona da “furbo”!)

20) Quanti sottoinsiemi di 5 elementi contiene un insieme di 10 elementi?

21)

a) Con 9 numeri fissati, possiamo costruire molte "quaterne" e molte "cinquine" .Pensiamo sia le une che le altre "non ordinate".

Sono più numerose le quaterne o le cinquine?

b) E se si pensasse a quaterne e cinquine ordinate? In questo caso, sarebbero più numerose le quaterne o le cinquine?

22)

15 secondi di tempo per dire quante cinquine non ordinate è possibile formare con 6 numeri.

30 secondi di tempo per dire quante cinquine ordinate.

23)

Dal mio guardaroba di 10 magliette e 8 paia di pantaloni voglio scegliere 5 magliette e altrettante paia di pantaloni per andare in ferie. In quanti modi diversi posso effettuare la scelta?

24)

In una classe di 28 allieve, tutte belle e intelligenti, bisogna scegliere:

due rappresentanti di classe;

una "miss";

11 ragazze per la squadra di calcio femminile.

Stabilire in quanti modi diversi si può effettuare questa scelta

a) se gli incarichi sono incompatibili

b) se gli incarichi sono compatibili

25)

Riprendiamo la situazione considerata nel problema 7).

In un'urna ci sono quattro palline, contrassegnate coi numeri 1, 2, 3, 4.

Supponiamo di estrarne 3, ma questa volta CONTEMPORANEAMENTE, sicchè non teniamo più conto dell'ordine di estrazione, ma soltanto di quali palline sono state estratte.

Quanti sono gli esiti possibili di queste estrazioni?

26)

In un mazzo da scopa ci sono 40 carte. Si mischia. Quanti sono i possibili esiti della mischiata?

27)

Se si effettuano 4 lanci di una moneta, quanti sono gli esiti possibili della sequenza di lanci?

E' richiesto di tracciare il diagramma ad albero.

28)

Devo distribuire a 10 bambini 5 mele, 2 banane e 3 pesche.

In quanti modi diversi posso effettuare la distribuzione?

29)

Una ragazza possiede tre astucci di smalto per le unghie, di tre colori differenti.

In quanti modi può tingersi le unghie delle mani, se vuole fare in modo che ciascun'unghia sia colorata in tinta unita e non ci siano più di due colori diversi su ciascuna mano? (libera traduzione da "Introduction to Finite Maths". Testo originale:

“A young lady has three shades of nail polish to paint her fingernails. In how many ways can she do this – each nail being one solid color – if there are no more than two different shades on each hand?”).

30)

Prove that two people in Columbus, Ohio, have the same initials (da: "Introduction to Finite Maths")

31)

Ecco un esercizio che richiede tipicamente un diagramma ad albero:

7 persone (tre uomini e quattro donne) desiderano entrare a far parte di un "club" molto esclusivo e riservato.

La direzione del "club" acconsente, a patto però di iscrivere soltanto una persona al mese, e in modo tale che, fra i "nuovi acquisti", ci siano sempre più donne che uomini. In quanti modi diversi può avvenire la successione delle iscrizioni?

32)

In un cinema c'è una fila di 5 poltrone. Se 3 persone vogliono sedersi, in quanti modi diversi si possono disporre?

33)

Stabilire in quanti modi possono disporsi, su di una fila di 4 sedie:

I) 1 persona II) 2 persone III) 3 persone IV) 4 persone

V) 5 persone (s'intende, una resterà in piedi) VI) 6 persone (due forzatamente resteranno in piedi)

(INDICAZIONE: nel caso in cui le persone siano più nelle sedie, può essere conveniente immaginare che siano ...le sedie a scegliere le persone. Così, nel caso V), indicate con 1, 2, 3 e 4 le sedie e con A, B, C, D, E le persone, diciamo che la sedia 1 ha 5 possibilità di scelta; in corrispondenza di ciascuna di queste 5 possibilità ci sono 4 possibilità di scelta per la sedia 2 ecc.)

33')

Stabilire in quanti modi possono disporsi, su di una fila di k sedie, n persone, distinguendo i casi: I) n<k II) n=k III) n>k

34)

Quante sono le possibili schedine di totocalcio con esattamente 5 pronostici "1", 7 pronostici "X" e 1 pronostico "2"?

34')

Generalizzazione del problema precedente per n₁ pronostici "1", n_X pronostici "X" e n₂ pronostici "2".

35)

I) 9 persone vogliono mettersi in fila per una foto di gruppo. In quanti modi diversi si possono disporre?

II) Se vogliono invece fare due file (5 persone accovacciate davanti, le altre 4 in piedi in seconda fila) il numero delle possibili disposizioni cambia?

III) Se si tratta di 5 maschi e 4 femmine, coi maschi accovacciati in prima fila e le femmine in piedi in seconda fila, quante sono le possibili disposizioni?

36)

Un Liceo offre a ciascuno studente la possibilità di iscriversi ad un massimo di due fra sette gruppi sportivi (Pallavolo, Calcetto, Atletica, Ginnastica, Nuoto, Ballo, Tiro con l'arco). Se tu sei uno studente di quel Liceo, quante scelte hai teoricamente a disposizione?

Se Nuoto e Tiro con l'Arco si svolgono contemporaneamente, così da non poter essere scelte entrambe dallo stesso studente, quante risultano le tue possibilità di scelta?

37)

I) Con 5 tessere rettangolari, recanti rispettivamente le 5 lettere A, B, C, D, E, quante sequenze diverse si possono costruire?

II) E se le 5 tessere recano le lettere A, A, C, D, E, quante sequenze diverse si possono costruire con esse?

III) Rispondere al medesimo quesito nel caso le tessere rechino le lettere A, A, E, E, E

IV) Astrattamente:

supponiamo di avere N oggetti, di cui: N₁ oggetti uguali fra loro, altri N₂ oggetti uguali fra loro ma non coi precedenti, … , infine i rimanenti N_r oggetti uguali fra loro ma non coi precedenti.

Insomma, gli N oggetti considerati sono suddivisi in r gruppi, ciascuno contenente rispettivamente N₁, N₂, ..., N_r oggetti, e nell'ambito di ciascun gruppo tutti gli oggetti sono uguali fra loro.

Quante sequenze distinguibili possiamo costruire con questi N₁+N₂+...+N_r=N oggetti?

Dopo aver scritto la formula, rispondi: a quali dei problemi precedentemente affrontati essa è applicabile?

38)

Le pareti della mia cucina sono ricoperte da 800 piastrelle.

Volendo dipingere esattamente 50 piastrelle in giallo, 100 in rosso e 200 in blu, lasciando bianche le rimanenti, in quanti modi è possibile effettuare il lavoro?

39)

Nella mia libreria ho: 10 libri di Storia, 6 libri sugli Animali e 7 libri di Matematica.

Voglio allinearli su di uno scaffale, in modo però che i libri di una medesima materia siano tutti vicini fra loro. In quanti modi diversi posso ordinare i miei 23 libri?

RISPOSTE AGLI ESERCIZI

18) (32ּ31ּ30ּ29ּ28)/5! = 201376

19) In tanti modi, quanti sono i modi con cui è possibile escluderne 2. Quindi: (20ּ19)/2 = 190

20) (10ּ9ּ8ּ7ּ6)/5! = 252

21a) Sono tante le quaterne non ordinate, quante le cinquine non ordinate. Infatti, a ogni quaterna possiamo associare biunivocamente una cinquina (quella dei 5 numeri rimanenti).

Verifica algebrica:

n° quaterne non ordinate = (9ּ8ּ7ּ6)/4! = 126

n° cinquine non ordinate = (9ּ8ּ7ּ6ּ5)/5! = 126

21b) Sono di più le cinquine ordinate delle quaterne ordinate.

n° quaterne ordinate = 9ּ8ּ7ּ6 = 3024

n° cinquine ordinate = 9ּ8ּ7ּ6ּ5 = 15120

22) 6 cinquine non ordinate (tante quanti sono i modi in cui si può escludere 1 numero dall’insieme dei 6 numeri dati)

6ּ5ּ4ּ3ּ2 = 720 cinquine ordinate

23)

24)

a) se gli incarichi sono incompatibili:

b) se gli incarichi sono compatibili:

25) Subito: 4 (tanti quanti i modi di escludere una pallina dall’estrazione). Oppure: (4ּ3ּ2)/3!=4

26) 40! Ecco perché non ci si annoia a giocare a scopa.

27) 2⁴ = 16

28)

Si tratta di scegliere i 5 bambini cui andranno le mele, poi i 2 (fra i 5 bambini rimanenti) cui andranno le banane; a questo punto, agli ultimi 3 bambini rimasti daremo le pesche.

29)

Questo problema è piuttosto complesso.

Pensiamo alla sola mano sinistra; il numero k di possibilità che troveremo dovrà poi essere moltiplicato per il numero di possibilità relative alla mano destra; poichè questo secondo numero sarà evidentemente identico al precedente (e cioè k), in definitiva il numero di possibilità richiesto dal problema sarà k² (evidentemente, va pensato come rilevante il fatto che una mano sia “la sinistra” e l’altra “la destra”, quindi questo risultato NON andrà diviso poi per 2).

1) Posso scegliere di colorare tutte e 5 le dita con lo stesso colore.