Stars and Bars

Stars and Bars (“Stele și Bare”) e o tehnică elegantă de combinatorică care rezolvă o clasă largă de probleme legate de:

• Distribuirea obiectelor identice
• Numărarea soluțiilor ecuațiilor cu constraint
• Combinări cu repetiție

E o tehnică obligatorie pentru orice olimpic de informatică/matematică.

Problema fundamentală

Câte moduri sunt de a distribui n bile identice în k cutii distincte?

Sau echivalent:

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

Ideea: stele și bare

Reprezentăm n bile ca stele (★) și separatoarele între cutii ca bare (|).

Pentru n = 5 bile în k = 3 cutii:

Cutia 1: 2 bile, Cutia 2: 1 bilă, Cutia 3: 2 bile
Reprezentare: ★★ | ★ | ★★

Cutia 1: 0 bile, Cutia 2: 5 bile, Cutia 3: 0 bile
Reprezentare: | ★★★★★ |

Cutia 1: 3 bile, Cutia 2: 0 bile, Cutia 3: 2 bile
Reprezentare: ★★★ | | ★★

Observație cheie: fiecare distribuire e o secvență unică de n stele și k - 1 bare.

Total caractere: n + k - 1. Dintre ele, trebuie să alegem pozițiile barelor (sau echivalent, ale stelelor).

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

De ce funcționează?

Orice permutare a n stele și k-1 bare dă o distribuire unică. Invers, fiecare distribuire dă o permutare unică.

Numărul de astfel de permutări:

(n + k - 1)! / (n! * (k-1)!) = C(n + k - 1, n)

Exemplu vizual: n = 3, k = 2

3 bile în 2 cutii. Formulele zic: C(3+2-1, 3) = C(4, 3) = 4.

Exact 4 distribuiri ✓.

Cod

#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; // n bile, k cutii
    fin >> n >> k;

    // Stars and Bars: C(n + k - 1, k - 1)
    fout << combinari(n + k - 1, k - 1);

    return 0;
}

date.in:

5 3

date.out:

21

Varianta 1: soluții pozitive

x₁ + x₂ + ... + xₖ = n cu xᵢ ≥ 1

Trucul substituției

Fie yᵢ = xᵢ - 1. Atunci yᵢ ≥ 0 și:

y₁ + y₂ + ... + yₖ = n - k

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

Exemplu

x + y + z = 7 cu x, y, z ≥ 1.

→ C(7-1, 3-1) = C(6, 2) = 15 soluții.

Vizualizare

Cu xᵢ ≥ 1, fiecare cutie trebuie să conțină cel puțin o bilă. E ca și cum punem mai întâi 1 bilă în fiecare cutie, apoi distribuim restul n - k liber.

Varianta 2: cu limite superioare

x₁ + x₂ + ... + xₖ = n cu xᵢ ≤ mᵢ

Se rezolvă cu PInEx: din total (stars and bars), scădem cazurile în care cel puțin un xᵢ > mᵢ.

long long rez = 0;
for (int mask = 0; mask < (1 << k); mask++) {
    int sum = 0;
    int bits = __builtin_popcount(mask);
    for (int i = 0; i < k; i++)
        if (mask & (1 << i))
            sum += m[i] + 1;
    if (sum > n) continue;
    long long c = combinari(n - sum + k - 1, k - 1);
    if (bits & 1) rez -= c;
    else rez += c;
}

Ideea PInEx: pentru fiecare submulțime de variabile pe care le forțăm peste limită, substituim yᵢ = xᵢ - (mᵢ + 1) și aplicăm stars and bars.

Aplicații clasice

1. Distribuire bomboane

“n bomboane identice, k copii. Câte moduri?”

→ C(n + k - 1, k - 1).

2. Cumpărături

“Cumpăr k cornuri din n tipuri disponibile (cu repetiție).”

Asta e combinări cu repetiție - aceeași formulă.

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

3. Soluții ecuații diofantice nenegative

“x₁ + x₂ + ... + xₖ = n, nenegative.”

→ C(n + k - 1, k - 1).

4. Selectarea coordonatelor

“Câte puncte lattice (x, y, z) cu coordonate nenegative au x + y + z = n?”

→ C(n + 2, 2) = (n+2)(n+1)/2.

Pas cu pas: x + y + z = 4

Câte soluții nenegative?

Formula: C(4 + 3 - 1, 3 - 1) = C(6, 2) = 15.

Enumerare:

Exact 15 ✓.

Aplicație complexă: probabilitate

Problemă: 10 bomboane împărțite la 4 copii. Care e probabilitatea ca fiecare copil să primească cel puțin una?

Total distribuiri: C(10 + 4 - 1, 4 - 1) = C(13, 3) = 286.

Distribuiri cu fiecare ≥ 1: C(10 - 1, 4 - 1) = C(9, 3) = 84.

Probabilitate: 84/286 ≈ 29.4%.

Cazuri speciale și extensii

Distribuire cu exact r cutii nevide

Din k cutii, exact r să fie nevide.

C(k, r) * C(n - 1, r - 1)

(Alege cele r cutii + distribuire strict pozitivă în ele.)

Distribuire “cu ordine” (compoziții)

Compoziția unui număr n = numărul de moduri de a-l scrie ca sumă de termeni pozitivi, cu ordine.

c(n) = 2^(n-1)

(Fiecare compoziție corespunde unei alegeri binare între cele n-1 “goluri”.)

Tabel rezumativ

Greșeli frecvente

1. Confuzia n vs k

Pentru n bile în k cutii, formula e C(n + k - 1, k - 1). Nu confunda poziția lui n și k.

Regulă: scrii steluțele și barele (n stele, k-1 bare) și alegi unde pui barele.

2. Obiecte distincte vs identice

Stars and bars funcționează pentru obiecte identice. Pentru obiecte distincte, folosești alte formule (principiul produsului, multinomial).

3. Cutii distincte vs identice

Stars and bars presupune cutii distincte. Dacă și cutiile sunt identice, problema devine partiții de întregi (mult mai grea, fără formulă închisă simplă).

4. Variante uitate

• xᵢ ≥ 0 → C(n+k-1, k-1) (clasic)
• xᵢ ≥ 1 → C(n-1, k-1) (substituție)

Cititorul citește “nenegative” sau “pozitive”? Fiecare produce o formulă diferită.

5. Uitarea constraint-urilor superioare

“x + y = 10, x ≤ 5, y ≤ 5” nu e direct stars and bars. Trebuie PInEx. Răspunsul: 6 soluții (0+10, 1+9 excluse, …).

Ce să reții

• Stars and Bars rezolvă distribuirea de obiecte identice în cutii distincte.
• Formula: C(n + k - 1, k - 1) pentru n obiecte în k cutii, nenegative.
• Variante:
  • xᵢ ≥ 1 → substituție, C(n-1, k-1)
  • xᵢ ≤ mᵢ → PInEx
• Ideea: reprezentăm n obiecte ca stele și k-1 separatoare ca bare, alegem poziția barelor.
• Echivalent cu soluții nenegative ale ecuațiilor diofantice liniare.
• Aplicații: distribuire bomboane, cumpărături, ecuații cu constraint, probabilități.
• Tehnică esențială pentru concursuri.

Probleme

pbinfoStarsandbars1→

pbinfoStarsandbars2→

pbinfoInghetata→

pbinfoExpozitie→

pbinfoCrescator2→

pbinfoProbleme→

pbinfoTransport→