99

8. Probleme de numrare 8.1. Consideraii teoretice i interpretri ale formulelor uzuale din combinatoric Exist o mare varietate de probleme care se pot ncadra n aceast tem. Pentru rezolvarea acestora, este necesar s reinem urmtoarele: I. Dac A i B sunt dou mulimi finite i notm { }: func ieAB f f A B= , atunci AAB B= , (am notat X numrul elementelor mulimii X). Acest rezultat se demonstreaz prin inducie dup m A= . Dm n continuare unele interpretri utile ale acestui rezultat. 1) Numrul submulimilor unei mulimi M avnd n elemente, n , este ( ) 2 MM =P . Aceasta rezult din faptul c numrul cerut este egal cu numrul funciilor : {0,1}f M . 2) n cte moduri poate fi pavat o alee de lungime n *( )n i lime 1 cu plci ptrate de 1 1 , folosindu-se plci de n culori. Numrul cerut este

nm , deoarece fiecrei poziii de plac din cele n trebuie s-i atribuim o culoare din cele m. 3) Cte cuvinte de m litere pot fi fcute cu un alfabet ce conine n simboluri? Numrul cerut este nm i este egal cu numrul funciilor :f A B ,

A n= numrul de simboluri i B m= numrul literelor dintr-un cuvnt. 4) Cte numere naturale de n cifre se pot forma folosind k cifre fixate,

{1,2, ,10}k K ? Dac nici o cifr din cele k nu este 0, putem forma nk numere deoarece orice cifr din numr poate fi aleas n k moduri. Dac printre cele k cifre se afl i cifra 0, prima cifr a numrului poate fi aleas n ( 1k ) moduri i orice alt cifr a numrului poate fi aleas n k moduri. Aadar, numrul de numere n acest caz este 1( 1) nk k . 5) Cte numere naturale au n cifre n scrierea lor n baza k ( 2)k ? Folosind 4) deducem c numrul cerut este 1( 1) nk k . 6) n cte moduri pot fi mprite n obiecte la m persoane? A face o astfel de mprire revine la a stabili un destinatar pentru fiecare obiect, deci a defini o funcie de la mulimea obiectelor la mulimea persoanelor privite ca i destinatari. Obinem c numrul cerut este nm .

100

II. Numrul submulimilor ordonate cu k elemente ale unei mulimi cu n elemente ( , , )k n k n este

not. ! ( 1)( 2) ( 1)( )!

kn

nA n n n n kn k

= = + L , i se citete aranjamente de n luate cte k, unde ! 1 2 3p p= K . Punem n eviden unele interpretri ale numerelor knA . 1) Dac A i B sunt mulimi finite cu A k B n= = , atunci numrul funciilor injective :f A B este egal cu knA . ntr-adevr, pentru a defini o funcie :f A B avem nevoie de valorile 1 2( ), ( ), , ( )kf a f a f aK care vor forma o submulime ordonat cu k elemente a lui B. Deci numrul funciilor injective de la A la B este egal cu numrul submulimilor ordonate cu k elemente ale lui B, n total knA . 2) Numrul cuvintelor formate cu k litere distincte, folosind un alfabet cu n simboluri este tot knA , k n . 3) Numrul modurilor de pavare a unei alei 1 k cu plci alese de culori diferite din n culori date este knA , k n . 4) Dac A este o mulime finit i nevid, atunci numrul funciilor injective (surjective, bijective) :f A A este !nnA n= . Facem observaia c o funcie bijectiv :f A A , A finit, se mai numete i permutare a mulimii A. Numrul permutrilor unei mulimi cu n elemente este egal cu !n . III. Dac A este o mulime cu n elemente, *n , atunci numrul submulimilor lui A avnd fiecare k elemente (k fixat, k n ) este:

! ( 1) ( 1)! !( )! !

kk nn

A n n n n kCk k n k k

+= = =K ,

i se citete combinri de n elemente luate cte k. Redm n continuare cteva aplicaii semnificative. 1) Care este numrul funciilor :{1,2, , } {0,1}f n K i avnd proprietatea

1( )

n

if i k

== ? A defini o astfel de funcie presupune a reine exact k

elemente din domeniul de definiie i a asocia fiecruia valoarea 1. Aadar, numrul cerut este egal cu numrul de submulimi cu k elemente ale domeniului de definiie, adic cu knC . Pentru 0k < sau k n> , sau [0, ] \k n , nu avem astfel de funcii. 2) Numrul drumurilor laticeale de lungime minim care unesc punctul O(0,0) cu punctul B( , ) ( , )m n m n este mm nC + . ntr-adevr, lungimea minim

101

a unui astfel de drum este m n+ , singurele deplasri fiind de forma ( , ) ( 1, )p q p q+a sau ( , ) ( , 1)p q p q +a . Din cei n m+ pai de lungime unu avem de fcut m pai orizontali i n pai verticali, ordinea efecturii lor fiind arbitrar. Numrul drumurilor laticeale cerut este egal cu numrul de pai pe orizontal, ceea ce se poate face n mm nC + moduri. 3) Numrul funciilor strict cresctoare :{1,2, , } {1,2, , }f k nK K , k n , este egal cu knC . Aceasta rezult din faptul c fiecare funcie strict cresctoare este determinat de !k funcii injective prin ordonarea cresctoare a valorilor sale. Aadar, numrul cerut este

Num rul func iilor injective! !

kknn

AN Ck k

= = = . 4) Numrul funciilor cresctoare :{1,2, , } {0,1,2, , }f k n k K K este

knC . Motivm n continuare acest lucru.

Fie f o funcie care ndeplinete condiiile din ipotez. Atunci, funcia :{1,2, , } {1,2, , }g k nK K , ( ) ( ) , ( ) 1,g i i f i i k= + = este strict cresctoare.

ntr-adevr, g este corect definit i dac presupunem 1 21 i i k < , atunci 1 2( ) ( )f i f i , deci 1 1 2 2( ) ( )i f i i f i+ < + , adic 1 2( ) ( )g i g i< .

Reciproc, dac :{1,2, , } {1,2, , }g k nK K , ( ) ( ) , ( ) 1,g i i f i i k= + = , este o funcie strict cresctoare atunci ( ) {1,2, , }i f i n+ K pentru ( ) 1,i k = , de unde ( ) {0,1, , }f i n k K pentru orice 1,i k= i

1 2 (1) (2) ( )k g g g k< < < < < < K K 1 (1) 2 (2) 3 (3) ( )f f f k f k + < + < + < < +K ,

de unde utiliznd faptul c ( ) , 1,f i i k = , obinem (1) (2) ( )f f f k K .

Aadar, funcia f este cresctoare. Ca urmare, mulimea funciilor f cerute este n bijecie cu mulimea funciilor g. A defini o funcie g revine la a alege un ir 1 21 kb b b n < < < K

1 2({ , , , } {1,2, , })kb b b nK K i acesta se poate face n knC moduri (vezi i problema precedent). Ca urmare, numrul cerut este knC . Mai facem observaia c numrul funciilor cresctoare :f A B , A n= , B m= este 1nm nC + .

5) Numrul modurilor de descompunere a numrului natural n n sum de k numere naturale nenule, 1 2 na a a+ + +K , n care conteaz ordinea

102

numerelor 1 2, , , na a aK este 11knC . Pentru a motiva aceasta, este suficient s ne imaginm c intervalul [0, ]n de lungime n, trebuie s-l partiionm n k subintervale. Aceasta se poate face alegnd cele 1k capete dintre numerele 1, 2, , 1n K , alegere ce se poate face n 11knC moduri. 6) Numrul modurilor de pavare a unei alei de lungime n i lime 1 cu plci 1 1 dintre care k albe i n k negre este knC . ntr-adevr, numrul cerut este egal cu numrul de alegeri a k poziii din cele n poziii n care s punem plci albe i acesta este knC . IV. Dac 1 21 2 kkn p p p = K reprezint descompunerea n factori primi a numrului natural n 1 2( , , , kp p pK sunt numere prime iar *1 2, , , k K ), atunci numrul divizorilor naturali ai lui n este:

1 2( 1)( 1) ( 1)k + + +K . Bibliografie 1. Dorin Andrica, Eugen Jecan, Teste de matematic, Editura GIL, Zalu 2. Dan Brnzei, Vasile Gorgota, Sorin Ulmeanu, Concursuri interjudeene de

matematic, Editura Paralela 45, 1999 3. Ovidiu Cojocaru, Matematic, Concursul interjudeean Spiru Haret Gh.

Vrnceanu 1985-1986, Editura Paralela 45 4. Mircea Ganga, Probleme elementare de matematic, Editura Mathpress,

2003 5. Adrian Ghioca, Acad. Nicolae Teodorescu, Culegere de probleme,

Bucureti, 1987 6. Laureniu Panaitopol, Dinu erbnescu, Probleme de teoria numerelor i

combinatoric pentru juniori, Editura GIL, 2003 7. Acad. Nicolae Teodorescu i alii, Culegere de probleme, S.S.M.R., vol.I,

Bucureti 8. Ion Tomescu, Introducere n combinatoric, Editura Tehnic, 1972 9. * * *, Coleciile revistelor G.M. i R.M.T