Programare Competitivă

Numere Stirling de speța I

Numerele Stirling de speța I (varianta nesemnată, notată c(n, k) sau |s(n, k)|) numără câte permutări ale mulțimii {1, 2, …, n} se descompun în exact k cicluri disjuncte.

Sunt verii “cu cicluri” ai combinărilor și apar natural în analiza algoritmilor pe permutări.

Șirul

Tabelul pentru n, k mici:

c(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     2     3     1     0     0
n=4       0     6    11     6     1     0
n=5       0    24    50    35    10     1

Linia n însumează la n! (număr total de permutări — orice permutare are un număr bine definit de cicluri).

Σ_{k=0}^{n} c(n, k) = n!

Relația de recurență

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

cu cazurile de bază c(0, 0) = 1 și c(n, 0) = c(0, k) = 0 pentru n, k > 0.

Interpretarea combinatorică (cum apare recurența):

Vrem să formăm o permutare a lui {1, ..., n} cu exact k cicluri. Privim elementul n și avem două cazuri disjuncte:

  1. n formează un ciclu singur de lungime 1. Atunci restul elementelor {1, ..., n-1} trebuie să formeze k-1 cicluri → c(n-1, k-1) moduri.

  2. n e inserat într-un ciclu existent. Întâi formăm o permutare a lui {1, ..., n-1} cu k cicluri (c(n-1, k) moduri), apoi inserăm n “după” oricare dintre cele n-1 elemente existente → (n-1) poziții.

Adunăm: c(n, k) = c(n-1, k-1) + (n-1) · c(n-1, k).

Problema 1: permutări cu k cicluri

Câte permutări ale mulțimii {1, 2, 3, 4} au exact 2 cicluri?

Răspuns: c(4, 2) = 11. Să le enumerăm — o permutare cu 2 cicluri se descompune în două cicluri nevide cu suma lungimilor = 4.

Împărțiri 4 = 3+1 (un ciclu de lungime 3, unul de lungime 1):

(1 2 3)(4)   (1 3 2)(4)
(1 2 4)(3)   (1 4 2)(3)
(1 3 4)(2)   (1 4 3)(2)
(2 3 4)(1)   (2 4 3)(1)

= 8 permutări. (Un ciclu de lungime 3 are (3-1)! = 2 forme distincte, apoi alegem care e fixul din 4 moduri → 4·2 = 8.)

Împărțiri 4 = 2+2 (două cicluri de lungime 2):

(1 2)(3 4)
(1 3)(2 4)
(1 4)(2 3)

= 3 permutări.

Total: 8 + 3 = 11 ✓.

Problema 2: aranjări circulare (numărul de cicluri)

În câte moduri pot aranja n persoane la k mese rotunde, fiecare masă având cel puțin o persoană? (Mesele sunt identice, ordinea la o masă contează doar până la rotație.)

Aceasta e exact c(n, k).

Exemplu: 5 persoane la 3 mese → c(5, 3) = 35 moduri.

Problema 3: conexiunea cu factorialul

Însumând pe toate k:

c(n, 0) + c(n, 1) + ... + c(n, n) = n!

Pentru că orice permutare a lui {1, ..., n} are o descompunere unică în cicluri, iar numărul total de permutări e n!.

Pas cu pas: calcul c(4, 2)

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

  • c(3, 1): 3 elemente într-un singur ciclu → (3-1)! = 2 forme: (1 2 3) și (1 3 2). Deci c(3, 1) = 2.
  • c(3, 2): 3 elemente în 2 cicluri. Un ciclu are 2 elemente, unul are 1. Alegerea elementului fix: 3 moduri. Deci c(3, 2) = 3.

c(4, 2) = 2 + 3 · 3 = 11 ✓.

Cod

Tabel cu recurență (DP)

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

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

void precalcStirling1(int n) {
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            c[i][j] = 0;
    c[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            c[i][j] = c[i - 1][j - 1] + (i - 1) * c[i - 1][j];
}

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

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

Cu aritmetică modulară

Când n e mare (și valorile explodează), reducem modulo:

const int MOD = 1e9 + 7;
long long c[NMAX + 1][NMAX + 1];

void precalcStirling1Mod(int n) {
    c[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j - 1] + (i - 1) * c[i - 1][j]) % MOD;
}

Tabel identități utile

Identitate Interpretare
c(n, k) = c(n-1, k-1) + (n-1)·c(n-1, k) recurența fundamentală
Σ_k c(n, k) = n! toate permutările partiționate pe nr. de cicluri
c(n, 1) = (n-1)! permutări cu un singur ciclu
c(n, n) = 1 singura permutare cu n cicluri e identitatea
c(n, n-1) = C(n, 2) o transpunere + puncte fixe

Creșterea numerelor Stirling I

c(n, k) crește foarte repede cu n. Exemple:

  • c(20, 5) ≈ 3.3 · 10^16 — aproape de limita long long (9.2 · 10^18).
  • c(25, 5) depășește long long.

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

Legătura cu Stirling II și Bell

  • Stirling I numără permutări descompuse în cicluri.
  • Stirling II S(n, k) numără partiții ale mulțimii în k submulțimi nevide.
  • Bell B(n) = Σ S(n, k) numără partiții totale.

Sunt trei fețe ale aceleași idei: cum structurezi o mulțime. Vezi lecțiile următoare.

Greșeli frecvente

1. Confuzia semnată vs nesemnată

Există și o variantă semnată s(n, k) care apare la dezvoltarea factorialului descrescător. În această lecție folosim doar nesemnată c(n, k) = |s(n, k)|, cea cu semnificație combinatorică directă.

2. Ordinea argumentelor în recurență

c(n, k) = c(n-1, k-1) + (n-1)·c(n-1, k) — coeficientul (n-1) se înmulțește cu termenul în care k rămâne neschimbat, NU cu cel în care scade.

3. Confuzia cu combinări

c(n, k) din această lecție NU e combinarea C(n, k) = n!/(k!(n-k)!). Sunt concepte diferite, chiar dacă notația se suprapune uneori în literatură.

Ce să reții

  • c(n, k) = numărul de permutări ale lui {1, ..., n} cu exact k cicluri.
  • Recurența cheie: c(n, k) = c(n-1, k-1) + (n-1)·c(n-1, k).
  • Suma pe linie: Σ_k c(n, k) = n!.
  • Calcul DP O(n²) cu un tabel 2D.
  • Aplicații: aranjări circulare, permutări cu număr fixat de cicluri, analiza algoritmilor randomizați.
  • Nu confunda cu combinările sau cu varianta semnată s(n, k).
Cuprins Inapoi Inainte