Numerele lui Stirling de speța a II-a reprezintă numărul de partiții ale unei mulțimi de $n$ elemente în $k$ submulțimi, și se notează cu $S(n, k)$. O partiție a unei mulțimi reprezintă un set de submulțimi nevide, disjuncte, a căror reuniune este mulțimea respectivă. Numerele lui Stirling sunt adesea folosite în rezolvarea problemelor de combinatorică.

Formula pentru calcularea $S(n, k)$

Cazurile elementare pentru calcularea $S(n, k)$ sunt:

  • $n = k = 0$: Prin convenție, $S(0, 0) = 1$, adică există $1$ mod de a partiționa mulțimea vidă în $0$ submulțimi.
  • $n = 0, k > 0$: $S(0, k) = 0$, adică nu putem partiționa o mulțime de $0$ elemente în mai mult de $0$ submulțimi (este destul de logic, pentru că nu am avea de unde să punem elemente în ele).
  • $n > 0, k = 0$: $S(n, 0) = 0$, adică nu putem partiționa o mulțime nevidă în $0$ submulțimi (toate elementele ar rămâne pe afară).

Dacă $n$ și $k$ nu se încadrează în vreun caz de mai sus, atunci $S(n, k)$ se poate calcula recurent, prin următoarea formulă:

$$S(n, k) = S(n - 1, k - 1) + kS(n - 1, k)$$

Deducerea formulei

Formula nu trebuie învățată pe de rost – ea se deduce ușor din modul de formare a partițiilor. Pentru demonstrație, voi scrie partițiile mulțimii $A = \{1, 2, 3, 4\}$ în $3$ submulțimi:

$$A = \{1, 2\} \cup \{3\} \cup \{4\}\\A = \{1, 3\} \cup \{2\} \cup \{4\}\\A = \{1\} \cup \{2, 3\} \cup \{4\}\\A = \{1, 4\} \cup \{2\} \cup \{3\}\\A = \{1\} \cup \{2, 4\} \cup \{3\}\\A = \{1\} \cup \{2\} \cup \{3, 4\}$$

Pentru a forma partițiile lui $B = \{1, 2, 3, 4, 5\}$ în $3$ submulțimi, vom folosi partițiile de mai sus la care vom adăuga elementul $5$. Acesta poate fi adăugat în două moduri. Fie la fiecare partiție, într-o submulțime nouă, ce-l va conține doar pe el, fie în una dintre submulțimile deja existente din fiecare partiție. Pornind de la prima partiție, adăugându-l pe $5$, vom obține:

$$\begin{align} B &= \{1, 2\} \cup \{3\} \cup \{4\} \cup \{5\}\\B &= \{1, 2, 5\} \cup \{3\} \cup \{4\}\\B &= \{1, 2\} \cup \{3, 5\} \cup \{4\}\\B &= \{1, 2\} \cup \{3\} \cup \{4, 5\} \end{align}$$

Analog pentru celelalte partiții 🙂 Așadar, pentru cazul 1 obținem $S(n - 1, k - 1)$ noi partiții, iar pentru cazul 2 obținem $k \cdot S(n - 1, k)$. Coeficientul $k$ vine din faptul că în fiecare partiție veche avem $k$ submulțimi la care putem adăuga noul element.

Sursă C++ pentru calcularea $S(n, k)$

Putem folosi metoda programării dinamice pentru calcularea $S(n, k)$ – vom reține într-o matrice rezultatele subproblemelor, mai exact stir[i][j] = S(i, j). Am folosit doar două linii pentru a nu consuma multă memorie, tehnică tipică programării dinamice.

Numărul de funcții surjective

Aceasta este cea mai cunoscută problemă ce folosește numerele lui Stirling. Se dau mulțimile $A$ și $B$, cu $|A| \ge |B|$, și trebuie să determinăm numărul funcțiilor surjective definite pe $A$ cu valori în $B$.

O funcție este surjectivă dacă și numai dacă imaginea ei este egală cu codomeniul. Iată un exemplu de funcție surjectivă definită pe $\{1, 2, 3, 4, 5\}$ cu valori în $\{1, 2\}$:

$$f(1) = 1\\f(2) = 2\\f(3) = 2\\f(4) = 1\\f(5) = 1$$

Iar așa arată toate funcțiile surjective definite pe $\{1, 2, 3\}$ cu valori în $\{1, 2\}$.

$$f(1) = 1, f(2) = 1, f(3) = 2\\f(1) = 2, f(2) = 2, f(3) = 1\\f(1) = 2, f(2) = 1, f(3) = 1\\f(1) = 1, f(2) = 2, f(3) = 2\\f(1) = 1, f(2) = 2, f(3) = 1\\f(1) = 2, f(2) = 1, f(3) = 2$$

Cu alte cuvinte, trebuie aflat numărul de moduri de a împărți elementele lui $A$ în $|B|$ grupe și de a asocia fiecărei dintre aceste grupe câte o valoare diferită din $B$ (adică valoarea pe care o va avea funcția aplicată numerelor din acel grup).

După această reformulare, problema devine destul de simplă. Numărul de partiții este dat de $S(|A|, |B|)$, iar pe acesta îl înmulțim cu $|B|!$ (numărul permutărilor de $|B|$ elemente), deoarece pentru fiecare partiție putem permuta în toate modurile posibile valorile asociate fiecărei submulțimi. Formula finală este:

$$S(|A|, |B|) \cdot |B|!$$

Multe probleme de combinatorică, interpretate matematic, pot fi reduse la aceasta. De exemplu, problema 100m, dată la ONI 2017 la clasa a 10-a.

Bonus

Colorând cu alb numerele pare și cu negru cele impare, numerele lui Stirling de speța a II-a, așezate într-o matrice, vor forma Triunghiul lui Sierpinski 😮

Paritatea numerelor lui Stirling de speța a II-a

Probleme recomandate

Ultimele trei probleme de mai sus nu folosesc în mod direct numerele lui Stirling, însă procedeul pentru deducerea recurențelor din spatele lor este foarte asemănător cu cel prezentat în acest articol. Dacă aveți întrebări despre numerele lui Stirling de speța a II-a, nu ezitați să le adresați în rubrica de comentarii 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!