Combinazioni con ripetizione: calcolare il numero di soluzioni di un’equazione

Esercizio 1

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

Esercizio 2

Determinare il numero di soluzioni dell’equazione

6x₁ + x₂ + x₃ + x₄ = 20

con x₁, x₂, x₃, x₄ interi non negativi.

Soluzione

L’incognita x₁ può assumere i valori 0, 1, 2, 3 (infatti 3 è il massimo valore possibile che può essere assunto da x₁: 3 x 6 = 18 + 1(x₃) + 1(x₂ ) = 20)

Abbiamo, pertanto, i seguenti casi:

• se x₁ = 0 l’equazione diventa x₂ + x₃ + x₄ = 20;
• se x₁ = 1 l’equazione diventa x₂ + x₃ + x₄= 14;
• se x₁ = 2 l’equazione diventa x₂ + x₃ + x₄ = 8;
• se x₁ = 3 l’equazione diventa x₂ + x₃ + x₄ = 2;

Dall’esempio precedente e dalla regola della somma  ne segue che il numero di soluzioni dell’equazione assegnata è dato da:

Esercizio 3

Determinare il numero di terne (a, b, c) di interi non negativi soddisfacenti la disuguaglianza:

a + b + c ≤ 2005

Soluzione

Le soluzioni della disuguaglianza richiesta sono in corrispondenza biunivoca con le soluzioni (in interi non negativi) dell’equazione:

a + b + c + d = 2005

e, pertanto, è dato da

Esercizio 4

Determinare il numero di soluzioni dell’equazione

(x₁ + x₂ + x₃)(y₁ + y₂ + y₃ + y₄) = 55

con x₁, x₂, x₃ e y₁, y₂, y₃, y₄ interi positivi.

Soluzione

I vincoli imposti alle variabili x_i ed y_j implicano che le soluzioni dell’equazione assegnata verificano uno dei seguenti casi:

•x₁ + x₂ + x₃ = 5 ,   y₁ + y₂ + y₃ + y₄ = 11
•x₁ + x₂ + x₃ = 11,  y₁ + y₂ + y₃ + y₄ = 5

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.

Applicando il PFC e la regola della somma abbiamo che il numero di soluzioni è:

Puoi trovare altri esercizi svolti sulle combinazioni semplici e con ripetizione QUI

(148)

PubblicitàPubblicità