Numere Stirling de speța II

Numerele Stirling de speța II, notate S(n, k) sau {n k}, numără câte moduri de a partiționa o mulțime cu n elemente distincte în exact k submulțimi nevide, în care ordinea submulțimilor nu contează.

Sunt numerele de bază pentru problemele de tipul “împart obiecte distincte în grupe identice”.

Șirul

Tabelul pentru n, k mici:

S(n, k):
         k=0   k=1   k=2   k=3   k=4   k=5
n=0       1     0     0     0     0     0
n=1       0     1     0     0     0     0
n=2       0     1     1     0     0     0
n=3       0     1     3     1     0     0
n=4       0     1     7     6     1     0
n=5       0     1    15    25    10     1

Valoarea S(4, 2) = 7 înseamnă: 7 moduri de a împărți {1, 2, 3, 4} în 2 submulțimi nevide.

Relația de recurență

S(n, k) = S(n-1, k-1) + k · S(n-1, k)

cu S(0, 0) = 1 și S(n, 0) = S(0, k) = 0 pentru n, k > 0.

Interpretarea combinatorică:

Vrem să partiționăm {1, ..., n} în k submulțimi nevide. Privim unde ajunge elementul n:

1. n formează propria lui submulțime (singleton) — restul {1, ..., n-1} se împarte în k-1 submulțimi nevide → S(n-1, k-1) moduri.

2. n se alătură unei submulțimi existente — întâi partiționăm {1, ..., n-1} în k submulțimi (S(n-1, k) moduri), apoi alegem în care din cele k îl băgăm pe n → k · S(n-1, k).

Formula explicită (cu incluziune-excluziune)

S(n, k) = (1/k!) · Σ_{j=0}^{k} (-1)^j · C(k, j) · (k - j)^n

Provine din numărul de surjecții de la o mulțime de n elemente la una de k elemente:

Surjecții(n, k) = k! · S(n, k)

Surjecțiile se numără cu incluziune-excluziune (vezi PInEx).

Problema 1: împărțirea elevilor în grupe

Am n = 4 elevi distincți și vreau să-i împart în exact k = 2 grupe nevide. Grupele sunt identice (nu contează dacă le numesc “grupa A” sau “grupa B”). În câte moduri?

Răspuns: S(4, 2) = 7. Enumerare:

{1}, {2,3,4}
{2}, {1,3,4}
{3}, {1,2,4}
{4}, {1,2,3}
{1,2}, {3,4}
{1,3}, {2,4}
{1,4}, {2,3}

4 moduri cu “1+3” + 3 moduri cu “2+2” = 7 ✓.

Atenție: dacă grupele ar fi etichetate (A și B distincte), numărul devine 2! · S(4, 2) = 14 — număr de surjecții de la {1, 2, 3, 4} la {A, B}.

Problema 2: bile distincte în cutii identice

Am n bile distincte (colorate distinct) și k cutii identice (nu se pot deosebi). Câte moduri să pun bilele în cutii, fiecare cutie având cel puțin o bilă?

Răspuns: exact S(n, k).

Variante:

Problema 3: numărul de surjecții

Am n obiecte distincte și vreau să le trimit către k destinații distincte, astfel încât fiecare destinație să primească cel puțin un obiect. În câte moduri?

Răspuns: k! · S(n, k) — pentru că alegem partiția în S(n, k) moduri, apoi etichetăm cele k părți cu destinațiile distincte în k! moduri.

Alternativ, folosind formula explicită de sus:

Surjecții(n, k) = Σ_{j=0}^{k} (-1)^j · C(k, j) · (k - j)^n

Exemplu: n = 4, k = 3 → 3! · S(4, 3) = 6 · 6 = 36 surjecții.

Pas cu pas: calcul S(4, 2)

Folosim recurența: S(4, 2) = S(3, 1) + 2 · S(3, 2).

• S(3, 1): 3 elemente într-o singură submulțime → doar {1, 2, 3} → S(3, 1) = 1.
• S(3, 2): 3 elemente în 2 submulțimi. Elementul singur e ales din 3 moduri → S(3, 2) = 3.

S(4, 2) = 1 + 2 · 3 = 7 ✓.

Cod

Tabel cu recurență (DP)

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

const int NMAX = 30;
long long S[NMAX + 1][NMAX + 1];

void precalcStirling2(int n) {
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            S[i][j] = 0;
    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];
}

int main() {
    int n, k;
    fin >> n >> k;
    precalcStirling2(n);
    fout << "S(" << n << ", " << k << ") = " << S[n][k];
    return 0;
}

Complexitate: O(n²) timp și memorie.

Cu formula explicită (incluziune-excluziune)

Util când vrei să calculezi doar un S(n, k) anume, fără tabel:

long long putere(long long a, long long b) {
    long long rez = 1;
    while (b > 0) {
        if (b & 1) rez *= a;
        a *= a;
        b >>= 1;
    }
    return rez;
}

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

long long stirling2(int n, int k) {
    long long sum = 0;
    for (int j = 0; j <= k; j++) {
        long long t = combinari(k, j) * putere(k - j, n);
        if (j & 1) sum -= t;
        else sum += t;
    }
    long long kfact = 1;
    for (int i = 2; i <= k; i++) kfact *= i;
    return sum / kfact;
}

Complexitate: O(k log n) timp cu exponențiere rapidă.

Tabel identități utile

Creșterea numerelor Stirling II

S(n, k) crește rapid, dar nu la fel de exploziv ca Stirling I. Exemple:

• S(20, 5) ≈ 7.5 · 10^11
• S(30, 10) ≈ 8.6 · 10^20 — depășește long long.

Pentru n ≥ 25, folosește modulo sau BigInt.

Legătura cu Bell

Suma pe linie dă numărul Bell:

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

B(n) numără toate partițiile unei mulțimi cu n elemente (indiferent de câte submulțimi). Vezi lecția următoare.

Greșeli frecvente

1. Confuzia submulțimi identice vs etichetate

S(n, k) tratează cele k submulțimi ca interschimbabile. Dacă le etichetezi (cutia 1, cutia 2, …, cutia k), multiplici cu k!.

2. Ignorarea condiției “nevid”

S(n, k) cere submulțimi nevide. Dacă permiți cutii goale, problema devine “funcții” de la n la k = k^n.

3. Recurența cu coeficient greșit

S(n, k) = S(n-1, k-1) + k·S(n-1, k) — coeficientul e k, NU k-1 sau n. Se numără câte submulțimi existente ai la dispoziție.

4. S(n, 0) și S(0, 0)

Prin convenție: S(0, 0) = 1 (partiția vidă a mulțimii vide — 1 mod), S(n, 0) = 0 pentru n ≥ 1 (nu poți avea 0 submulțimi nevide acoperind n ≥ 1 elemente).

Ce să reții

• S(n, k) = numărul de moduri de a partiționa {1, ..., n} în exact k submulțimi nevide, identice.
• Recurența cheie: S(n, k) = S(n-1, k-1) + k·S(n-1, k).
• Formula explicită: S(n, k) = (1/k!) Σ (-1)^j C(k, j) (k-j)^n.
• Numărul de surjecții: k! · S(n, k).
• Suma pe linie = numărul Bell.
• Calcul DP O(n²).
• Aplicații: împărțirea în grupe identice, surjecții, modele de rime, clasificare.

Probleme

pbinfoCercetasi→