Numerele lui Catalan, Stirling, Bell

Numerele lui Catalan, Stirling, Bell

Numerele lui Catalan

Problema

Sa se determine numarul sirurilor formate din k litere A si m litere B, care au proprietatea

(P): pentru orice 1≤i≤m+k, numarul de litere B nu depaseste numarul de litere A in prefixul sirului de lungime i.

Solutie

Numarul acestor siruri este nenul daca si numai daca este indeplinita conditia m≤k.

Numarul sirurilor care contin litera A de k ori, iar litera B de m ori este

Nr(k,m)=(m+k)!/(m!k!)=Comb(m+k,m)

Dintre aceste siruri, vom determina numarul sirurilor care nu verifica proprietatea P.

Sa consideram S un sir care contine litera A de k ori, litera B de m ori si care nu verifica proprietatea P. Exista in acest sir o pozitie 2p+1 (p≥0) astfel incat S[2p+1]=B, iar prefixul sirului S de lungime 2p contine p litere A si p litere B. Vom alege p minim cu aceasta proprietate.

Transformam sirul S dupa cum urmeaza.

Adaugam pe prima pozitie o litera A. Se obtine astfel un sir format din m litere B si k+1 litere A, iar prefixul de lungime 2p+2 al acestui sir contine un numar egal de litere A si B.

In prefixul de lungime 2p+2 al sirului obtinut schimbam litera A in litera B, iar litera B in litera A. Prin aceasta transformare numarul total de litere A si B nu se modifica, iar prima litera din sir este acum B.

Prin aceste transformari asociem in mod biunivoc unui sir care contine litera A de k ori, litera B de m ori si care nu verifica proprietatea P un sir care contine litera A de k+1 ori, litera B de m ori si care incepe cu litera B. Adica numarul sirurilor care contin litera A de k ori, litera B de m ori si care nu verifica proprietatea P este egal cu numarul sirurilor care contin litera A de k+1 ori, litera B de m ori si care incep cu litera B (m<k+1).

Suprimand prima litera din acest siruri, obtinem toate sirurile formate din m-1 litere B si k+1 litere A. Numarul lor este Nr(k+1,m-1)=Comb(m+k,m-1).

Deci numarul sirurilor care contin litera A de k ori, litera B de m ori si satisfac proprietatea P este Comb(m+k,m)-Comb(m+k,m-1)=Comb(m+k,m)*(k-m+1)/(k+1)

Observatia 1

Daca in problema precedenta vom avea k=m=n, atunci obtinem problema parantezelor (sirurile formate din n perechi de paranteze rotunde care se inchid corect).

Deducem ca numarul de solutii este Catalan(n)=Comb(2n,n)/(n+1), numar denumit si numarul lui Catalan (de ordin n).

Observatia 2

Datorita modului de obtinere a numerelor Catalan, prezentat in solutia problemei precedente, deducem un mod de calcul al numerelor Catalan, bazat pe triunghiul combinarilor al lui Pascal.

Catalan(n) se obtine din diferenta dintre termenul n de pe linia 2n a triunghiului lui Pascal si termenul din stanga sa (Comb(2n,n)-Comb(2n,n-1)).

Observatia 3

Din formula care descrie numerele Catalan, putem deduce si o relatie de recurenta:

Catalan(0)=1 si (n+2)Catalan(n+1)=(4n+2)Catalan(n), (n>0).

Conform formulei de mai sus, numerele lui Catalan constituie un sir de numere naturale, primii termeni fiind:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,

Numerele lui Catalan intervin in numeroase probleme de combinatorica. Amintim unele dintre cele mai cunoscute interpretari combinatorice ale numerelor lui Catalan.

1.   Fie * o operatie binara asociativa. In cate moduri poate fi parantezata expresia a₁*a₂**a_n? Solutia acestei probleme a fost data de matematicianul belgian Eugene Charles Catalan in 1838 si este Catalan(n-1).

2.   Numarul de posibilitati de a trianguliza (partitiona in triunghiuri) un poligon cu n varfuri cu ajutorul a n-3 diagonale care nu se intersecteaza (exceptand extremitatile) este Catalan(n-2).

3.   Numarul de arbori binari cu n varfuri neetichetate este Catalan(n).

4.   Numarul de moduri in care 2n persoane asezate la o masa rotunda isi pot stange mainile fara ca bratele lor sa se intersecteze este Catalan(n).

5.   Numarul de profiluri montane distincte se pot desena cu ajutorul a n caractere / si n caractere , fara a cobori sub "nivelul marii" (linia orizontala care trece prin punctul de plecare) este Catalan(n).

6.   Sa consideram o tabla de sah de dimensiune (n+1)*(n+1) si o piesa plasata initial intr-un colt al tablei. O mutare consta in plasarea piesei in una dintre pozitiile alaturate (pe orizontala sau verticala). Numarul de drumuri distincte de lungime 2n pe care le poate strabate piesa din coltul initial in coltul opus, fara a intersecta diagonala principala este Catalan(n).

7.   Numarul de permutari ce se pot obtine cu ajutorul unei stive in care se introduc succesiv numerele 1, 2, , n este Catalan(n).

O abordare recursiva

Sa revenim la problema initiala, problema parantezelor (sa determinam numarul de siruri formate din n perechi de paranteze care se inchid corect).

Analizand problema pentru n=1, obtinem o solutie (), pentru n=2 obtinem doua solutii ()() si (()).

Observam ca orice sir format din n perechi de paranteze care se inchid corect incepe cu paranteza deschisa si exista o paranteza inchisa care corespunde acestei paranteze deschise.

Deci sirul poate fi partitionat in doua secvente sub forma: (X)Y, unde X este un sir de k perechi de paranteze care se inchid corect, iar Y este un sir de n-k-1 perechi de paranteze care se inchid corect (0≤k<n). Deducem astfel urmatoarea formula de recurenta:

Catalan(n)=Catalan(0)*Catalan(n-1)+ Catalan(1)*Catalan(n-2)+ Catalan(2)*Catalan(n-3)++ Catalan(n-1)*Catalan(0)

Numerele lui Stirling

Numerele lui Stirling de speta I

Definitie

Numerele lui Stirling de speta I reprezinta numarul de permutari ale elementelor care contin exact k cicluri (notat s(n,k)) .

Observatie

Definitia anterioara corespunde numerelor lui Stirling de speta I, fara semn.

Numerele lui Stirling de speta I cu semn sunt coeficientii polinomului

P_n(x)=x(x-1)(x-2)(x-n+1).

(P_n(x)=s'(n,0)+s'(n,1)x+s'(n,2)x²++s'(n,n)xⁿ)

Relatia dintre numerele lui Stirling de speta I cu semn si fara semn este:

s'(n,k)=(-1)^n-ks(n,k)

O abordare recursiva

Numerele lui Stirling de speta I cu semn satisfac relatia de recurenta:

s'(n,0)=0; s'(n,1)=1

s'(n+1,k)=s'(n,k-1)-ns'(n,k)

Justificare

P_n+1(x)=P_n(x)*(x-n)=P_n(x)*x-nP_n(x)

Numerele lui Stirling de speta I fara semn satisfac relatia de recurenta:

s(n+1,k)=ns(n,k)+s(n,k-1)

Justificare

Elementul n+1 poate forma singur cel de-al k-lea ciclu sau poate fi inserat in unul dintre ciclurile formate cu celelalte n elemente (in n moduri posibile) (p(x)=p(n+1),x= ucc.).

Numerele lui Stirling de speta a II-a

Definitie

Fie X o multime finita, nevida. S= formeaza o partitie a multimii X in k clase daca:

1.     A_i sunt submultimi nevide ale lui X ( i=1, 2, , k)

2.     A_i si A_j sunt disjuncte ( i≠j=1, 2, , k)

3.     A₁ A₂ A_k=X

Observatie

Orice partitie induce o relatie de echivalenta pe multimea X (elementele a si b sunt echivalente daca sunt in aceeasi submultime) si reciproc. Cu alte cuvinte, exista o bijectie intre multimea relatiilor de echivalenta definite pe multimea  X si multimea partitiilor lui X.

Definitie

Numim numarul lui Stirling de speta a II-a (notat S(n,k), k≤n) numarul de partitii ale unei multimi cu n elemente in k clase.

Observatie

Ordinea claselor, cat si ordinea elementelor intr-o clasa nu conteaza.

O abordare recursiva

In primul rand observam ca S(n,1)=S(n,n)=1.

O partitie a multimii in k clase se poate obtine:

din orice partitie a multimii in k-1 clase la care de adauga o noua clasa formata numai din elementul n;

din orice partitie a multimii in k clase, inserand elementul n in oricare dintre cele k clase din aceasta partitie.

Obtinem relatia de recurenta

S(n,k)=S(n-1,k-1)+k*S(n-1,k).

O alta abordare recursiva

Sa consideram o partitie a multimii in k clase. Suprimam din aceasta partitie clasa care contine elementul n. Vom obtine o partitie formata din k-1 clase in care apar x elemente (n - cele existente in clasa din care facea parte n). Dar cele x elemente care raman pot fi alese din cele n-1 (exceptandu-l pe n) in Comb(n-1,x) moduri.

Prin urmare:

Relatie dintre numarul lui Stirling de speta a II-a si numarul de functii surjective

Teorema

Fie A o multime cu n elemente si B o multime cu k elemente (k≤n). Numarul de functii surjective definite de la A la B (notat Sj(n,k)) este k!S(n,k).

Justificare

Sa consideram f:A B o functie surjectiva. Aceasta functie induce o partitie a multimii A in k clase astfel: A_y=. Exista k! posibilitati de a eticheta submultimile partitiei.

O formula

Numerele lui Stirling de speta a II-a sunt descrise de formula:

Demonstratia se poate face prin inductie

Numerele lui Bell

Definitie

Numarul de partitii ale unei multimi cu n elemente se numeste numarul lui Bell (notat B(n)).

Observatie

Din definitia numerelor lui Stirling de speta a II-a, deducem ca:

B(n)=S(n,1)+S(n,2)++S(n,n).

B(0)=1.

O abordare recursiva

Numerele lui Bell satisfac urmatoarea relatie de recurenta

Folosind definitia numerelor lui Stirling si cea de a doua formula de recurenta pentru numerele lui Stirling, urmata de schimbarea ordinii de sumare, obtinem:

Dar

Deci are loc relatia de mai sus.

Exercitii

1. Numere asociate numerelor lui Stirling de speta I

Putem asocia numerele d₂(n,k)=numarul de permutari de ordin n care contin k cicluri avand lungime ≥2.

a.     Deduceti o formula pentru cazurile speciale: d₂(n,1); d₂(2k,k).

b.     Deduceti o relatie de recurenta pentru d₂(n,k).

2. Numerele lui Entringer

Numerele lui Entringer sunt definite astfel:

E(n,k)=numarul de permutari de ordin n+1 care incep cu k si care au forma unui W-zig-zag. Determinati o relatie de recurenta pentru numerele lui Entringer.

3.     Sa consideram sirurile de paranteze in care o paranteza ( este inchisa de doua )).

De exemplu, pentru n=2: ( ( )) )), ( ) ( )) ), ( )) ( )).

Mai exact o parantezare este corecta daca ea contine cel putin o secventa de forma ()), iar prin eliminarea acestei secvente parantezarea obtinuta este de asemenea corecta.

Determinati numarul de parantezari corecte de ordin n.

4. Partitii ale unui numar natural

Definitie

Fie n un numar natural nenul. Numim partitie a lui n in k parti un sistem de numere naturale de forma a₁≥a₂≥≥a_k≥1, astfel incat a₁+a₂++a_k=n.

Notam P(n,k)=numarul de partitii ale lui n in k parti.

Demonstrati ca numerele P(n,k) verifica urmatoarea relatie de recurenta:

P(n,1)=P(n,n)=1

P(n+k,k)=P(n,1)+P(n,2)++P(n,k)

Probleme

1. EXPRESSIONS                               (Baltic - 1999)

Let X be the smallest set defined as follows

- an empty string belongs to X,

- if A, B belong to X then both, (A) and AB, belong to X.

The elements of X are called correctly built parenthesis expressions.

The following strings are correctly built parenthesis expressions:

The expressions below are not correctly built parenthesis expressions:

Let E be a correctly built parenthesis expression.

The length of E is the number of single parenthesis in E.

The depth D(E) of E is defined as follows:

 0if E is empty

D(E)=   D(A)+1 if E = (A), and A is in X

 max(D(A),D(B)) if E = AB, and A, B are in X

What is the number of correctly built parenthesis expressions of length n and depth d, for given  positive integers n and d?

Task

Write a program which reads two integers n and d from the text file PAR.IN; computes the number of correctly built parenthesis expressions of length n and depth d; writes the result into the text file PAR.OUT

Input data

The only line of the input file PAR.IN contains two integers n and d separated by a single space character, 2  n  38, 1  d  19.

Output data

The only line of the output file PAR.OUT should contain a single integer - the number of correctly built parenthesis expressions of length n and depth d.

Example

Input data (file PAR.IN)            Output data (file PAR.OUT)

6 2               3

There are exactly three correctly built parenthesis expressions of length 6 and depth 2:

2.Descompuneri - Baraj 2001

Se dau numerele naturale nenule N, K si X. Numim o K-descompunere a lui N un sir strict crescator de K numere naturale nenule, a caror suma este N.

Dintre toate K-descompunerile lui N, sa se determine in cate apare numarul X.

Date de intrare

Fisier de intrare: DESCOMP.IN

Linia 1: N K X

trei numere naturale nenule, separate prin cate un spatiu, avand semnificatia din enunt.

Date de iesire

Fisier de iesire: DESCOMP.OUT

Linia 1: NR

numar natural, reprezentand numarul descompunerilor respectand cerintele problemei.

Restrictii

2 N 350

Exemplu

DESCOMP.IN                               DESCOMP.OUT

12 3 2                              3

Explicatii:

12=1+2+9

12=2+3+7

12=2+4+6

Bibliografie

Ioan Tomescu - Combinatorica si teoria grafurilor, Bucuresti 1978