Numerele lui Stirling. Numerele Bell

Numerele lui Stirling. Numerele Bell

În acest articol voi prezenta trei elemente importante de combinatorică, ușor asemănătoare între ele: numerele lui Stirling de speța a II-a, numerele Bell și numerele lui Stirling de speța I. Ele sunt utile în problemele de combinatorică, pentru că primele două numără partițiile unei mulțimi, iar al treilea tip de numere este referitor la ciclurile unei permutări.

Numerele lui Stirling de speța a II-a

Numerele lui Stirling de speța a II-a reprezintă numărul de partiții ale unei mulțimi cu nn elemente în kk submulțimi, și se notează cu S(n,k)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ă.

Formula pentru calcularea S(n,k)S(n, k)

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

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

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

S(n,k)=S(n1,k1)+kS(n1,k)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 prin care se formează partițiile. Pentru demonstrație, voi scrie partițiile mulțimii A={1,2,3,4}A = \{1, 2, 3, 4\} în 33 submulțimi:

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

Pentru a forma partițiile lui B={1,2,3,4,5}B = \{1, 2, 3, 4, 5\} în 33 submulțimi, vom folosi partițiile de mai sus la care vom adăuga elementul 55 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 într-una dintre submulțimile deja existente din fiecare partiție. Pornind de la prima partiție, adăugându-l pe 55 vom obține:

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

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

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

Putem folosi metoda programării dinamice pentru calcularea S(n,k)S(n, k) Vom reține într-o matrice rezultatele subproblemelor, mai exact stir[i][j]=S(i,j)\mathrm{stir}[i][j] = S(i, j)

#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector stir(n + 1, vector<int>(k + 1));
stir[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= min(i, k); j++)
stir[i][j] = stir[i - 1][j - 1] + j * stir[i - 1][j];
cout << stir[n][k] << '\n';
return 0;
}

Numărul de funcții surjective

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

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}\{1, 2, 3, 4, 5\} cu valori în {1,2}\{1, 2\}

f(1)=1f(2)=2f(3)=2f(4)=1f(5)=1 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}\{1, 2, 3\} cu valori în {1,2}\{1, 2\}

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

Cu alte cuvinte, trebuie aflat numărul de moduri de a împărți elementele lui AA în B|B| grupe și de a asocia fiecărei dintre aceste grupe câte o valoare diferită din BB (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)S(|A|, |B|) iar pe acesta îl înmulțim cu B!|B|! (numărul permutărilor de B|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)B!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

Numerele Bell

Numerele Bell se referă la numărul de modalități prin care putem partiționa o mulțime cu nn elemente, și se notează cu BnB_n Seamănă cu numerele lui Stirling de speța a II-a, doar că nu iau în calcul numărul de submulțimi ale partițiilor. Astfel, ele numără toate partițiile posibile ale unei mulțimi. Numerele Bell pot fi calculate trivial pe baza numerelor lui Stirling de speța a II-a:

Bn=S(n,0)+S(n,1)++S(n,n)B_n = S(n, 0) + S(n, 1) + \cdots + S(n, n)

Însă putem formula și o recurență ce depinde doar de numerele Bell:

Bn=k=0n1Cn1kBkB_n = \sum_{k = 0}^{n - 1} C_{n - 1}^k B_k

Cazul de bază este B0=1B_0 = 1 Din păcate, recurența aceasta se calculează tot în O(n2)O(n^2) însă pe noi ne interesează modul prin care a fost obținută. Ne putem gândi că din cele nn elemente ale mulțimii noastre, putem selecta nkn - k (0k<n\htmlClass{katexified}{(} 0 \le k \lt n pe care să le punem într-o submulțime, rămânând ca pe celelalte kk să le partiționăm separat, în BkB_k moduri. Cum cele nkn - k elemente pot fi alese în Cnnk=CnkC_n^{n - k} = C_n^k moduri, obținem că Bn=k=0n1CnkBkB_n = \sum_{k = 0}^{n - 1} C_n^k B_k

Însă, avem o greșeală fundamentală în raționament. De exemplu, pe partiția {1,2},{3}\{1, 2\}, \{3\} am numărat-o de două ori: Când am ales să-i punem pe 11 și 22 în aceeași submulțime, rămânând să partiționăm recursiv submulțimea {3}\{3\} dar și atunci când am ales să-l punem pe 33 într-o submulțime și să partiționăm recursiv submulțimea {1,2}\{1, 2\} Pentru a remedia această problemă, trebuie să fixăm un element arbitrar (de exemplu 11 pe care-l punem mereu în submulțimea de cardinal nkn - k selectată de noi. Este perfect în regulă, pentru că el oricum trebuie să se afle într-o submulțime. Acum rămâne să selectăm în Cn1nk1=Cn1kC_{n - 1}^{n - k - 1} = C_{n - 1}^k moduri ce elemente punem în aceeași submulțime cu 11 Astfel, ajungem la recurența inițială, fără să numărăm de mai multe ori vreo configurație.

Numerele lui Stirling de speța I

Numerele lui Stirling de speța I numără câte permutări de ordin nn cu kk cicluri există, și se notează cu s(n,k)s(n, k) De exemplu, permutarea

σ=(123456142365)\sigma = \begin{pmatrix} \textcolor{orangered}{1} & \textcolor{limegreen}{2} & \textcolor{limegreen}{3} & \textcolor{limegreen}{4} & \textcolor{dodgerblue}{5} & \textcolor{dodgerblue}{6}\\ \textcolor{orangered}{1} & \textcolor{limegreen}{4} & \textcolor{limegreen}{2} & \textcolor{limegreen}{3} & \textcolor{dodgerblue}{6} & \textcolor{dodgerblue}{5} \end{pmatrix}

are 33 cicluri: (1)\textcolor{orangered}{(1)} (2,4,3)\textcolor{limegreen}{(2, 4, 3)} și (5,6)\textcolor{dodgerblue}{(5, 6)} Al doilea ciclu, de pildă, a fost format așa:

σ(2)=4σ(4)=3σ(3)=2 \sigma(2) = 4\\ \sigma(4) = 3\\ \sigma(3) = 2

Cazurile particulare sunt: s(0,0)=1s(0, 0) = 1 s(n,0)=0s(n, 0) = 0 (n>0\htmlClass{katexified}{(} n \gt 0 și s(0,k)=0s(0, k) = 0 (k>0\htmlClass{katexified}{(} k \gt 0 Motivele sunt similare cu cele de la numerele de speța a II-a. Recurența este:

s(n,k)=s(n1,k1)+(n1)s(n1,k)s(n, k) = s(n - 1, k - 1) + (n - 1) \cdot s(n - 1, k)

Explicație: Putem forma o permutare de ordin nn pornind de la una de ordin n1n - 1 în două moduri. Prima variantă este să adăugăm elementul nn la final, deci σ(n)=n\sigma(n) = n formând un nou ciclu, ce-l conține doar pe el. A doua variantă este să-l introducem pe nn într-un ciclu deja existent. Pentru asta, alegem un număr aa (1a<n\htmlClass{katexified}{(} 1 \le a \lt n cu σ(a)=b\sigma(a) = b și îl schimbăm pe σ(a)\sigma(a) în nn iar lui σ(n)\sigma(n) îi atribuim valoarea bb

(12an1σ(1)σ(2)bσ(n1))(12an1nσ(1)σ(2)nσ(n1)b)\begin{pmatrix} 1 & 2 & \cdots & a & \cdots & n - 1\\ \sigma(1) & \sigma(2) & \cdots & b & \cdots & \sigma(n - 1) \end{pmatrix} \to \begin{pmatrix} 1 & 2 & \cdots & a & \cdots & n - 1 & n\\ \sigma(1) & \sigma(2) & \cdots & n & \cdots & \sigma(n - 1) & b \end{pmatrix}

Așadar, folosind prima metodă obținem s(n1,k1)s(n - 1, k - 1) permutări noi, iar folosind-o pe a doua obținem (n1)s(n1,k)(n - 1) \cdot s(n - 1, k) Coeficientul n1n - 1 vine de la faptul că, de fiecare dată când alegem aaul despre care vorbeam mai devreme, avem n1n - 1 variante.

Sursă C++ pentru calcularea s(n,k)s(n, k)

Iată mai jos o sursă care calculează s(n,k)s(n, k) Este aproape identică cu cea pentru numere lui Stirling de speța a II-a, singura diferență fiind relația de recurență (linia 10).

#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector stir(n + 1, vector<int>(k + 1));
stir[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= min(i, k); j++)
stir[i][j] = stir[i - 1][j - 1] + (i - 1) * stir[i - 1][j];
cout << stir[n][k] << '\n';
return 0;
}

Probleme recomandate

100m și Permutări folosesc numerele lui Stirling (de ambele spețe), iar Sistem folosește o recurență foarte asemănătoare cu cea a numerelor Bell. Ultima problemă nu e legată în mod direct vreun concept din cele trei, însă procedeul pentru deducerea recurenței din spatele ei este foarte asemănător cu cele prezentate în acest articol. Dacă aveți întrebări despre numerele lui Stirling sau despre numerele Bell, nu ezitați să le adresați în rubrica de comentarii

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii