Esercizi svolti di calcolo combinatorio. Combinazioni semplici e con ripetizione -1-

 

ESERCIZIO 1

Quanti dei numeri

100, 101, · · · , 999

hanno tre cifre diverse in ordine crescente o in ordine decrescente?

SOLUZIONE

I numeri con le cifre in ordine decrescente sono in corrispondenza biunivoca con i sottoinsiemi di cardinalità 3 di {0, 1, . . . , 9}.

Essi sono

I numeri con le cifre in ordine crescente sono in corrispondenza biunivoca con i sottoinsiemi di cardinalità 3 di {1, 2, . . . , 9}.

Essi sono

Per la regola della somma il numero richiesto è:

120 + 84 = 204

ESERCIZIO 2

In una classe vi sono 20 studenti. In quanti modi si possono assegnare 5 test differenti, con la condizione che ogni test deve essere assegnato a 4 studenti?

SOLUZIONE

Possiamo scegliere gli studenti che devono svolgere il primo test in

modi, dai rimanenti possiamo sceglierne altri 4 per il secondo test in

modi, e così via. Per il PFC il numero richiesto è:

Principio fondamentale del calcolo combinatorio (PFC)

Supponiamo che un problema P possa essere scomposto in k sottoproblemi indipendenti P₁,P₂, · · · , P_k. Se il sottoproblema P₁ può essere risolto in n₁ modi, il sottoproblema P₂ in n₂ modi, · · · , il sottoproblema P_k in n_k modi, allora il problema P può essere risolto in

n₁ · n₂ · · · n_k modi.

 

ESERCIZIO 3

Una pasticceria produce 5 tipi di paste a, b, c, d, e. In quanti modi diversi si può confezionare un vassoio con 7 di queste paste?

SOLUZIONE

Le combinazioni con ripetizione

Definizione
Si chiama combinazione con ripetizione di n elementi di un insieme I composto da k oggetti distinti, un gruppo di n elementi di I non necessariamente distinti e disposto in un ordine qualsiasi.

Teorema sulle combinazioni con ripetizione

Il numero di combinazioni con ripetizione di k elementi di un insieme I composto da n oggetti distinti è:

Ogni confezione di 7 paste può essere pensata come una combinazione con ripetizione di classe 7 scelta da un insieme di 5 oggetti. Quindi si possono confezionare

vassoi diversi.

ESERCIZIO 4

Quanti sono i termini di un polinomio omogeneo completo di 6 grado nelle variabili a, b, c, d?

SOLUZIONE

I termini sono tanti quante le combinazioni con ripetizione di classe 6 che si possono formare con le 4 lettere a, b, c, d, ossia:

ESERCIZIO 5

Un supermercato, in occasione delle festività natalizie ha scontato 3 tipi di articoli X, Y , Z. Giovanni vuole approfittare dell’occasione e decide di acquistare 8 articoli. Quali sono i possibili modi in cui può effettuare gli acquisti?

I possibili acquisti sono tanti quante le combinazioni di classe 8 che si possono formare con i tre oggetti X, Y , Z ossia :

ESERCIZIO 6

Quante sono le soluzioni dell’equazione:

x₁ + x₂ + · · · + x_k = n

(a) con x₁, x₂, . . . , x_k interi positivi
(b) con x₁, x₂, . . . , x_k interi non negativi

SOLUZIONE

(a)

Scriviamo n come somma di n addendi uguali ad 1 :

n = 1 + 1 + · · · +

Per decomporre n nella somma di k addendi positivi è sufficiente scegliere k − 1 segni + e questo, tenuto conto che vi sono n − 1 segni +, può essere fatto in

modi.

(b)

Posto x_i = y_i − 1 allora y_i > 1 > 0 per ogni i e l’equazione si trasforma in :

y₁ + y₂ + · · · + y_k = n + k       (*)

Le soluzioni della (*) in interi positivi, in virtù dell’esempio precedente, sono complessivamente