Combinări cu repetiție

Până acum, combinările erau alegere fără repetiție - fiecare element apărea cel mult o dată.

Combinările cu repetiție permit alegerea aceluiași element de mai multe ori.

Formulă

CR(n, k) = C(n + k - 1, k)

“Câte moduri sunt de a alege k elemente dintr-o mulțime de n tipuri, cu repetiție permisă?”

De ce formula asta?

Va fi demonstrată complet în lecția Stars and Bars (următoarea). Pentru moment, ia-o ca dată.

Exemple concrete

Exemplul 1: cornuri de la brutărie

Brutăria are n = 5 tipuri de cornuri. Cumperi k = 3 cornuri. Câte combinații distincte poți avea?

Poți lua și 3 cornuri de același tip, sau 2+1, sau 1+1+1 din tipuri distincte.

→ CR(5, 3) = C(5+3-1, 3) = C(7, 3) = 35 combinații.

Exemplul 2: aruncarea a 3 zaruri

Câte combinații distincte de sume dau 3 zaruri aruncate (ordinea zarurilor nu contează)?

6 fețe, 3 zaruri → CR(6, 3) = C(8, 3) = 56 combinații.

(Atenție: “aruncare” poate avea sau nu ordine - aici am presupus că nu.)

Exemplul 3: combinații de înghețată

Un magazin are 10 arome. Cumperi un bol cu 4 cupe. Câte bole distincte poți avea?

→ CR(10, 4) = C(13, 4) = 715.

Comparație cu fără repetiție

Observă că la combinări cu repetiție, k poate fi mai mare ca n (poți lua toate de același tip).

Cod

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    long long rez = 1;
    for (int i = 0; i < k; i++) {
        rez *= (n - i);
        rez /= (i + 1);
    }
    return rez;
}

long long combinariRepetitie(int n, int k) {
    return combinari(n + k - 1, k);
}

Cod complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    long long rez = 1;
    for (int i = 0; i < k; i++) {
        rez *= (n - i);
        rez /= (i + 1);
    }
    return rez;
}

int main() {
    int n, k;
    fin >> n >> k;
    fout << "CR(" << n << ", " << k << ") = " << combinari(n + k - 1, k);
    return 0;
}

date.in:

5 3

date.out:

CR(5, 3) = 35

Vizualizare: cumpărăturile

Brutărie cu 3 tipuri: A, B, C. Cumpărăm 2 cornuri.

Combinații posibile:

AA AB AC BB BC CC

Total: 6 combinări = CR(3, 2) = C(4, 2) = 6 ✓

Fără repetiție am fi avut doar: AB, AC, BC = C(3, 2) = 3.

Problemă clasică: soluții ecuație

Câte soluții nenegative întregi are ecuația x₁ + x₂ + ... + xₙ = k?

Răspuns: CR(n, k) = C(n+k-1, k).

De ce?

Fiecare soluție corespunde unei alegeri de k “unități” distribuite în n variabile. Vezi Stars and Bars.

Exemplu: x + y + z = 5

Soluții: (5,0,0), (4,1,0), (4,0,1), (3,2,0), (3,1,1), (3,0,2), (2,3,0), ...

Total: CR(3, 5) = C(7, 5) = 21 soluții.

Variante

1. Soluții pozitive (x_i ≥ 1)

x₁ + x₂ + ... + xₙ = k cu xᵢ ≥ 1

Substituie yᵢ = xᵢ - 1 (yᵢ ≥ 0). Noua ecuație: y₁ + ... + yₙ = k - n.

→ CR(n, k-n) = C(k-1, n-1).

2. Cu limite superioare

x₁ + x₂ + ... + xₙ = k cu xᵢ ≤ mᵢ

Se rezolvă cu PInEx: scădem cazurile în care x₁ > m₁ sau x₂ > m₂, etc.

Mai complicat - vezi problemele avansate.

Aplicații

1. Cumpărături multiple

“Câte moduri de a cumpăra k obiecte dintre n tipuri?” → CR(n, k).

2. Distribuire bomboane

“Câte moduri de a împărți k bomboane identice la n copii?” → CR(n, k).

3. Rezolvarea ecuațiilor liniare cu constraint

“x + y + z + w = 10, xᵢ ≥ 0” → C(13, 3) = 286 soluții.

4. Arborii de sintaxă

Pentru gramatici libere, numărul de arbori posibili pentru o expresie dată.

Pas cu pas pentru CR(3, 2)

n = 3 (tipuri), k = 2 (cât cumpărăm). CR = C(3+2-1, 2) = C(4, 2) = 6.

Listăm toate combinațiile cu k = 2 din {A, B, C}:

Exact 6 ✓.

Greșeli frecvente

1. Confuzia cu fără repetiție

“Câte moduri de a alege 3 tipuri distincte de cornuri?” → C(n, 3). “Câte moduri de a cumpăra 3 cornuri (cu posibile repetiții)?” → CR(n, 3).

Repetiția e permisă?

2. k > n

La C(n, k), dacă k > n, rezultatul e 0. La CR(n, k), k > n e permis: CR(3, 5) = C(7, 5) = 21.

3. Ordinea contează?

Dacă ordinea elementelor contează și se repetă → n^k (aranjamente cu repetiție). Dacă ordinea nu contează și se repetă → CR(n, k).

4. Uitarea ecuației diofantice

“Câte soluții nenegative x + y + z = 7?” e un caz clasic de CR - verifică dacă e ceea ce cere problema.

Ce să reții

• CR(n, k) = C(n+k-1, k) - alegerea de k din n tipuri cu repetiție.
• Ordinea NU contează, repetiția e permisă.
• Echivalentă cu: soluții nenegative ale x₁ + x₂ + ... + xₙ = k.
• Cazuri speciale:
  • xᵢ ≥ 1 → C(k-1, n-1)
  • xᵢ ≤ mᵢ → PInEx
• Aplicații: cumpărături, distribuire obiecte identice, ecuații diofantice nenegative.
• Demonstrația elegantă: tehnica Stars and Bars (lecția următoare).