Numere Bell

Numerele Bell B(n) numără câte moduri de a partiționa o mulțime cu n elemente distincte în submulțimi nevide, fără să fixăm numărul de submulțimi.

Practic, B(n) e suma tuturor modurilor de a împărți n elemente în grupe, indiferent de câte grupe.

Șirul

B(0) = 1
B(1) = 1
B(2) = 2
B(3) = 5
B(4) = 15
B(5) = 52
B(6) = 203
B(7) = 877
B(8) = 4140
B(9) = 21147
B(10) = 115975

Crește super-exponențial. B(25) depășește deja long long.

Conexiunea cu Stirling II

B(n) = Σ_{k=0}^{n} S(n, k)

Deci Bell e suma pe o linie din tabelul Stirling II (vezi Stirling II).

Exemplu: B(4) = S(4, 0) + S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 0 + 1 + 7 + 6 + 1 = 15 ✓.

Relația de recurență

B(n+1) = Σ_{k=0}^{n} C(n, k) · B(k)

cu B(0) = 1.

Interpretarea combinatorică:

Vrem să partiționăm {1, ..., n+1}. Privim submulțimea care îl conține pe n+1. Dacă are dimensiune n+1-k (adică n+1 e grupat cu alte n-k elemente):

Aleg celelalte n-k elemente dintre {1, ..., n} în C(n, n-k) = C(n, k) moduri.
Partiționez cele k elemente rămase în orice fel: B(k) moduri.

Însumez pe toate k:

B(n+1) = Σ C(n, k) · B(k)

Triunghiul lui Bell

Există o construcție elegantă care generează B(n) linie cu linie — triunghiul lui Bell (sau triunghiul lui Peirce):

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203

Reguli de construcție

Prima linie conține doar 1.
Fiecare linie nouă începe cu ultimul element al liniei anterioare.
Restul: fiecare element = stânga + sus-stânga.

Unde stau numerele Bell?

B(n+1) = ultimul element al liniei n (sau primul element al liniei n+1).
B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, B(5) = 52, B(6) = 203 — exact coloana din dreapta / stânga.

Exemplu de construcție pas cu pas

Linia 0: 1
Linia 1: începe cu 1 (ultimul din linia 0), apoi 1 + 1 = 2 → 1 2
Linia 2: începe cu 2 (ultimul din linia 1), apoi 2 + 1 = 3, apoi 3 + 2 = 5 → 2 3 5
Linia 3: începe cu 5, apoi 5 + 2 = 7, 7 + 3 = 10, 10 + 5 = 15 → 5 7 10 15

Problema 1: împărțirea elevilor în grupe (orice număr de grupe)

Am 4 elevi distincți. În câte moduri îi pot împărți în una sau mai multe grupe (neetichetate, nevide)?

Răspuns: B(4) = 15. Detaliat pe număr de grupe:

1 grupă: {1, 2, 3, 4} → 1 mod
2 grupe: 7 moduri (vezi lecția Stirling II)
3 grupe: 6 moduri
4 grupe: {1}, {2}, {3}, {4} → 1 mod

Total: 1 + 7 + 6 + 1 = 15 ✓.

Problema 2: scheme de rime

Câte modele de rime distincte există pentru o strofă cu n versuri?

De exemplu, pentru 3 versuri (A, B, C): - AAA (toate rimează): 1 model - AAB, ABA, ABB: 3 modele (două rimează, una nu) - ABC: 1 model (niciuna nu rimează)

Total: B(3) = 5.

Fiecare partiție a mulțimii {vers1, vers2, ..., versn} într-un număr oarecare de submulțimi corespunde unui model de rimă.

Problema 3: numărul de relații de echivalență

Câte relații de echivalență distincte pot fi definite pe o mulțime cu n elemente?

Răspuns: B(n).

O relație de echivalență partiționează mulțimea în clase de echivalență. Numărul de astfel de partiții e fix numărul Bell.

Pas cu pas: calcul `B(4)` din recurență

B(4) = B(3+1) = Σ_{k=0}^{3} C(3, k) · B(k)

= C(3,0)·B(0) + C(3,1)·B(1) + C(3,2)·B(2) + C(3,3)·B(3)
= 1·1      + 3·1      + 3·2      + 1·5
= 1 + 3 + 6 + 5
= 15 ✓

Cod

Cu triunghiul Bell (eficient și elegant)

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

const int NMAX = 25;
long long triunghi[NMAX + 1][NMAX + 1];

long long bell(int n) {
    if (n == 0) return 1;
    triunghi[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        triunghi[i][0] = triunghi[i - 1][i - 1];
        for (int j = 1; j <= i; j++) {
            triunghi[i][j] = triunghi[i][j - 1] + triunghi[i - 1][j - 1];
        }
    }
    return triunghi[n][0];
}

int main() {
    int n;
    fin >> n;
    fout << "B(" << n << ") = " << bell(n);
    return 0;
}

Complexitate: O(n²) timp.

Din Stirling II

long long S[NMAX + 1][NMAX + 1];

long long bellViaStirling(int n) {
    S[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            S[i][j] = S[i - 1][j - 1] + j * S[i - 1][j];
    long long sum = 0;
    for (int k = 0; k <= n; k++) sum += S[n][k];
    return sum;
}

Din recurența cu combinări

long long B[NMAX + 1];
long long C[NMAX + 1][NMAX + 1];

void precalcBell(int n) {
    for (int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    B[0] = 1;
    for (int i = 1; i <= n; i++) {
        B[i] = 0;
        for (int k = 0; k < i; k++)
            B[i] += C[i - 1][k] * B[k];
    }
}

Toate variantele sunt O(n²). Cea cu triunghiul Bell e cea mai compactă.

Tabel identități utile

Identitate	Interpretare
`B(n) = Σ_k S(n, k)`	Bell = suma Stirling II pe linie
`B(n+1) = Σ C(n, k) · B(k)`	recurența cu combinări
`B(0) = B(1) = 1`	cazurile de bază
Triunghi: `T(n, 0) = T(n-1, n-1)`	element de start pe linie
Triunghi: `T(n, j) = T(n, j-1) + T(n-1, j-1)`	regula de construcție

Formula lui Dobiński (curiozitate)

Există o formulă analitică surprinzătoare:

B(n) = (1/e) · Σ_{k=0}^{∞} k^n / k!

Aceasta leagă numerele Bell de constanta e. Nu e utilă pentru calcul (serie infinită), dar e o relație frumoasă între combinatorică și analiză.

Creșterea numerelor Bell

Sunt cele mai explozive numere combinatorice comune:

B(10) ≈ 1.2 · 10^5
B(15) ≈ 1.4 · 10^9
B(20) ≈ 5.8 · 10^13
B(25) ≈ 4.6 · 10^18  ← la marginea long long
B(26) depășește long long

Pentru n ≥ 25, folosește aritmetică modulară sau BigInt.

Aplicații

Partiționare de mulțime: elevi în grupe, obiecte în categorii, cuvinte în clase.
Relații de echivalență: câte moduri de a grupa obiecte după o proprietate comună.
Modele combinatorice: rime, colorări unde doar grupul contează (nu culoarea exactă).
Probabilistică: numărul de partiții ale spațiului eșantioanelor.
Algoritmi de aglomerare (clustering): numărul total de configurații posibile cu n puncte.

Greșeli frecvente

1. Confuzia cu `2^n` (submulțimi)

B(n) numără partiții (împărțirea exhaustivă și disjunctă), nu submulțimi. Numărul de submulțimi ale unei mulțimi cu n elemente e 2^n, diferit.

2. Triunghiul Bell început greșit

Regula: linia nouă începe cu ultimul element al liniei anterioare (NU cu 1, și NU cu primul element). Fără asta, toate valorile sunt greșite.

3. Overflow rapid

B(n) crește extrem de repede. B(25) e deja ~4.6 · 10^18, foarte aproape de long long. Mereu verifică dacă ai nevoie de modulo sau BigInt.

4. `B(0) = 1`

Prin convenție, mulțimea vidă are o singură partiție (partiția vidă). B(0) = 1, nu 0.

Ce să reții

B(n) = numărul de partiții ale unei mulțimi cu n elemente în submulțimi nevide, fără să fixezi numărul de submulțimi.
B(n) = Σ_k S(n, k) (suma pe linie din Stirling II).
Recurența cu combinări: B(n+1) = Σ C(n, k) · B(k).
Triunghiul Bell: construcție elegantă, elementul de start al liniei n = B(n).
Crește super-exponențial — B(25) depășește long long.
Aplicații: relații de echivalență, modele de rime, grupări generale.
B(0) = 1 prin convenție.