Teoria Grafurilor si CombinatoricaCurs 1: Introducere.

Principii de numarare. Aranjamente, permutari si combinari

octombrie 2017

Teoria Grafurilor si Combinatorica

Scopul cursului

Familiarizare cu notiunile de baza din combinatorica si teoriagrafurilor

Cuprins

1 Principii de numarare, permutari si combinari2 Metode de enumerare, principiul incluziunii si excluziunii3 Combinari4 Structura ciclica a permutarilor. Tehnici avansate de numarare5 Teoria lui Polya de numarare6 Notiuni fundamentale de teoria grafurilor7 Retele de transport8 Tipuri si structuri de date pentru grafuri9 Arbori: definitii, generare, arbori de cost minim

10 Drumuri, circuite, cai si cicluri11 Problema comis-voiajorului. Grafuri planare12 Colorarea grafurilor. Teoria lui Ramsey13 Cuplaje

Teoria Grafurilor si Combinatorica

Aspecte organizatorice

Curs: Mircea MarinSeminar: Mircea Marin / Monica Tirea

Pagina web:https://users.info.uvt.ro/~mmarin/lectures/TGC

Material de curs: disponibil din pagina web

Evaluare: 50% proba scrisa (examen final), 50% seminar

Teoria Grafurilor si Combinatorica

Descrierea primului curs

Principii fundamentale de numarare

Regula produsuluiRegula sumeiDemonstratii combinatoriale; exemple

Tehnici de numarare pentru

combinari - selectii neordonate de elemente distincte din omultime finitapermutari - selectii ordonate de elemente distincte din omultime finita

Generalizari

permutari cu repetitiecombinari cu repetitiepermutari cu elemente nediferentiate

Numere binomiale si multinomiale

Teoria Grafurilor si Combinatorica

Principii fundamentale de numarare1. Regula produsului

Regula produsului. Daca o procedura poate fi descompusa n o secventade 2 proceduri astfel ncat

prima se poate efectua n n1 feluria doua se poate efectua n n2 feluri

atunci exista n1 n2 feluri de a efectua acea procedura.

Regula generalizata a produsului. Daca o procedura poate fi descompusan o secventa de m proceduri astfel ncat

prima se poate efectua n n1 feluria doua se poate efectua n n2 feluri. . .a m-a se poate efectua n nm feluri

atunci exista n1 n2 . . . nm feluri de a efectua aceaprocedura.

Teoria Grafurilor si Combinatorica

Principii fundamentale de numarare1. Regula produsului

Regula produsului. Daca o procedura poate fi descompusa n o secventade 2 proceduri astfel ncat

prima se poate efectua n n1 feluria doua se poate efectua n n2 feluri

atunci exista n1 n2 feluri de a efectua acea procedura.

Regula generalizata a produsului. Daca o procedura poate fi descompusan o secventa de m proceduri astfel ncat

prima se poate efectua n n1 feluria doua se poate efectua n n2 feluri. . .a m-a se poate efectua n nm feluri

atunci exista n1 n2 . . . nm feluri de a efectua aceaprocedura.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

Raspuns

Alocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

Raspuns

Alocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

RaspunsAlocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.

Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

RaspunsAlocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.

Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

RaspunsAlocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(1) O companie are 12 birouri si 2 angajati: Gheorghe si Ion. Incate feluri se pot aloca birouri diferite celor doi angajati?

RaspunsAlocarea se poate descompune n 2 operatii distincte: alocareaunui birou pentru Gheorghe, urmata de alocarea unui biroupentru Ion.Exista 12 alternative pentru prima operatie, deoarece sunt 12birouri n total.Exista 11 alternative pentru operatia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

conform regulii produsului, sunt 12 11 = 132 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

Raspuns

Problema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

Raspuns

Problema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.

conform regulii produsului, exista 26 50 = 1300 variante.(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

Raspuns

Fiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1. conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

RaspunsFiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1.

conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsului

(2) Intr-o sala de laborator, scaunele sunt numerotate cu o literamare urmata de un numar ntre 1 si 50. Cate scaune pot finumerotate diferit n felul acesta?Se presupune ca sunt 26 litere mari.

RaspunsProblema poate fi descompusa n o secventa de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmatoarea este alegerea unui numar din cele 50 posibile.conform regulii produsului, exista 26 50 = 1300 variante.

(3) Cate siruri diferite de 7 biti exista?

RaspunsFiecare din cei 7 biti poate fi ales n 2 feluri: 0 sau 1.

conform regulii produsului, exista 27 = 128 variante.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor dintre 2 multimi finite

(4) Cate functii sunt de la o multime cu m elemente la o multimecu n elemente?

Raspuns f : {a1, . . . , am} {b1, . . . , bn}

Definirea unei astfel de functii poate fi descompusa n m etapeindependente: n etapa i se fixeaza valoarea lui f (ai )Etapa i are n posibilitati, deoarece putem alege pentru f (ai )orice valoare din multimea {b1, . . . , bn}

conform regulii produsului, numarul de functii esten . . . n

m ori

= nm

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor dintre 2 multimi finite

(4) Cate functii sunt de la o multime cu m elemente la o multimecu n elemente?

Raspuns f : {a1, . . . , am} {b1, . . . , bn}Definirea unei astfel de functii poate fi descompusa n m etapeindependente: n etapa i se fixeaza valoarea lui f (ai )

Etapa i are n posibilitati, deoarece putem alege pentru f (ai )orice valoare din multimea {b1, . . . , bn}

conform regulii produsului, numarul de functii esten . . . n

m ori

= nm

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor dintre 2 multimi finite

(4) Cate functii sunt de la o multime cu m elemente la o multimecu n elemente?

Raspuns f : {a1, . . . , am} {b1, . . . , bn}Definirea unei astfel de functii poate fi descompusa n m etapeindependente: n etapa i se fixeaza valoarea lui f (ai )Etapa i are n posibilitati, deoarece putem alege pentru f (ai )orice valoare din multimea {b1, . . . , bn}

conform regulii produsului, numarul de functii esten . . . n

m ori

= nm

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor dintre 2 multimi finite

(4) Cate functii sunt de la o multime cu m elemente la o multimecu n elemente?

Raspuns f : {a1, . . . , am} {b1, . . . , bn}Definirea unei astfel de functii poate fi descompusa n m etapeindependente: n etapa i se fixeaza valoarea lui f (ai )Etapa i are n posibilitati, deoarece putem alege pentru f (ai )orice valoare din multimea {b1, . . . , bn}

conform regulii produsului, numarul de functii esten . . . n

m ori

= nm

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]

Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}

Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.

Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}.

...Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea functiilor injective dintre 2 multimi finite

(5) Cate functii injective sunt de la o multime cu m elemente la omultime cu n elemente?[Observati ca trebuie sa avem m n.]Raspuns: descompunem problema n n subprobleme distincte

Presupunem ca f : {a1, a2, . . . , am} {b1, b2, . . . , bn}Exista n cai de alegere a valorii luif (a1) {b1, . . . , bn}.Exista n 1 cai de alegere a valorii luif (a2) {b1, . . . , bn} {f (a1)}....Exista n (m 1) cai de alegere a valorii luif (am) {b1, . . . , bn} {f (a1), . . . , f (am1)}.

conform regulii produsului, exista n (n 1) . . . (n m + 1)astfel de functii.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

Demonstratie

Pentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bn

Definirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii produsuluiNumararea submultimilor unei multimi finite

(6) Numarul de submultimi al unei multimi finite S = {a1, a2, . . . , an}este 2n.

DemonstratiePentru fiecare submultime B a lui A definim sirul de bitib1b2 . . . bn cu

bi =

{1 daca ai B0 daca ai 6 B

Numarul de submultimi al lui A coincide cu numarul de siruridistincte de biti b1 . . . bnDefinirea a unui sir de biti de lungime n se poate descompunen n subprobleme distincte: subproblema i fixeaza valoareabitului bi

conform regulii produsului, exista 2 . . . 2 n ori

= 2n astfel de siruri.

numarul de submultimi al unei multimi S cu n elemente este 2n.

Teoria Grafurilor si Combinatorica

Principii fundamentale de numarare2. Regula sumei

Regula sumei. Daca o procedura se poate efectua n 2 feluri, pentru feluli sunt ni variante, si nici una din variantele de primul felnu coincide cu vreo varianta de felul 2, atunci existan1 + n2 variante de a efectua procedura.

Regula generalizata a sumei. Presupunem ca o procedura poate fiefectuata n m feluri, pentru felul i sunt ni variante, sivariantele efectuate n feluri diferite sunt diferite. Atunciexista n1 + n2 + . . . + nm variante de a efectua procedurarespectiva.

Teoria Grafurilor si Combinatorica

Principii fundamentale de numarare2. Regula sumei

Regula sumei. Daca o procedura se poate efectua n 2 feluri, pentru feluli sunt ni variante, si nici una din variantele de primul felnu coincide cu vreo varianta de felul 2, atunci existan1 + n2 variante de a efectua procedura.

Regula generalizata a sumei. Presupunem ca o procedura poate fiefectuata n m feluri, pentru felul i sunt ni variante, sivariantele efectuate n feluri diferite sunt diferite. Atunciexista n1 + n2 + . . . + nm variante de a efectua procedurarespectiva.

Teoria Grafurilor si Combinatorica

Principii fundamentale de numarare2. Regula sumei

Regula sumei. Daca o procedura se poate efectua n 2 feluri, pentru feluli sunt ni variante, si nici una din variantele de primul felnu coincide cu vreo varianta de felul 2, atunci existan1 + n2 variante de a efectua procedura.

Regula generalizata a sumei. Presupunem ca o procedura poate fiefectuata n m feluri, pentru felul i sunt ni variante, sivariantele efectuate n feluri diferite sunt diferite. Atunciexista n1 + n2 + . . . + nm variante de a efectua procedurarespectiva.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii sumei

(1) Un student trebuie sa aleaga un proiect de programare din 3liste. Prima lista contine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare n mai multe liste. Cate proiecteposibile exista?

Raspuns

Proiectul poate fi ales independent din una din cele 3 listeDeoarece nici un project nu apare n mai multe liste, putemaplica regula sumei 9 + 8 + 12 = 29 posibilitati.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii sumei

(1) Un student trebuie sa aleaga un proiect de programare din 3liste. Prima lista contine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare n mai multe liste. Cate proiecteposibile exista?

Raspuns

Proiectul poate fi ales independent din una din cele 3 listeDeoarece nici un project nu apare n mai multe liste, putemaplica regula sumei 9 + 8 + 12 = 29 posibilitati.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii sumei

(1) Un student trebuie sa aleaga un proiect de programare din 3liste. Prima lista contine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare n mai multe liste. Cate proiecteposibile exista?

RaspunsProiectul poate fi ales independent din una din cele 3 liste

Deoarece nici un project nu apare n mai multe liste, putemaplica regula sumei 9 + 8 + 12 = 29 posibilitati.

Teoria Grafurilor si Combinatorica

Aplicatii ale regulii sumei

(1) Un student trebuie sa aleaga un proiect de programare din 3liste. Prima lista contine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare n mai multe liste. Cate proiecteposibile exista?

RaspunsProiectul poate fi ales independent din una din cele 3 listeDeoarece nici un project nu apare n mai multe liste, putemaplica regula sumei 9 + 8 + 12 = 29 posibilitati.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!).

P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!).

P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.

Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.

Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!).

P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Probleme mai complexe de numarare

Multe probleme de numarare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, nsa pot fi rezolvate daca folosimambele reguli.

Exemple

(1) Se stie ca o parola este un sir ntre 6 si 8 caractere lungime, si cafiecare caracter este fie o litera mare sau o cifra zecimala. Fiecareparola contine cel putin o cifra. Cate parole posibile sunt?

Raspuns

Fie P numarul total de parole, si P6, P7 si P8 numarul deparole cu lungimea 6, 7, sau 8.Conform regulii sumei, P = P6 + P7 + P8.Calculul lui Pm pentru m {6, 7, 8}, se poate face astfel:

Fie Wm numarul de siruri de litere mari si cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

m = 36m

Fie Nm numarul de siruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

m.

Se observa usor ca Pm = Wm Nm (explicati de ce!). P = W6N6+W7N7+W8N8 = 366266+367267+368268.

Teoria Grafurilor si Combinatorica

Exemple mai complexe de numarare

(2) In cate feluri putem alege 2 carti scrise n limbaje diferitedintr-o colectie de 5 carti scrise n romana, 9 scrise n engleza,si 10 n germana?

Raspuns

R&E = 5 9 = 45 cf. regulii produsuluiR&G = 5 10 = 50 cf. regulii produsuluiE&G = 9 10 = 90 cf. regulii produsului

45 + 50 + 90 = 185 feluri (cf. regulii sumei).

Teoria Grafurilor si Combinatorica

Exemple mai complexe de numarare

(2) In cate feluri putem alege 2 carti scrise n limbaje diferitedintr-o colectie de 5 carti scrise n romana, 9 scrise n engleza,si 10 n germana?

Raspuns

R&E = 5 9 = 45 cf. regulii produsuluiR&G = 5 10 = 50 cf. regulii produsuluiE&G = 9 10 = 90 cf. regulii produsului

45 + 50 + 90 = 185 feluri (cf. regulii sumei).

Teoria Grafurilor si Combinatorica

Demonstratii combinatoriale

O demonstratie combinatoriala este o demonstratie carefoloseste argumente de numarare, precum regula sumei siregula produsului pentru a demonstra ceva.

Demonstratiile ilustrate mai devreme sunt combinatoriale.

Teoria Grafurilor si Combinatorica

Aranjamente, permutari si combinariDefinitii

Presupunem ca A este o multime finita cu n elemente.

Un aranjament de n luate cate r (sau r -permutare) al lui A este osecventa ordonata a1, a2, . . . , ar de elemente distincte din A.O permutare a lui A este un aranjament a1, a2, . . . , an al tuturorelementelor lui A.

O r -combinare a lui A este o submultime {a1, a2, . . . , ar} cu relemente a lui A.

Exemple

3, 1, 2 si 1, 3, 2 sunt permutari ale multimii {1, 2, 3}.3, 1 si 1, 2 sunt 2-permutari ale multimii {1, 2, 3}.2-combinarile lui {1, 2, 3} sunt submultimille {1, 2}, {1, 3}, {2, 3}

P(n, r) := nr. de r -permutari ale unei multimi cu n elemente.

C (n, r) := nr. de r -combinari ale unei multimi cu n elemente.Notatie alternativa:

(nr

).

Teoria Grafurilor si Combinatorica

Aranjamente, permutari si combinariDefinitii

Presupunem ca A este o multime finita cu n elemente.

Un aranjament de n luate cate r (sau r -permutare) al lui A este osecventa ordonata a1, a2, . . . , ar de elemente distincte din A.O permutare a lui A este un aranjament a1, a2, . . . , an al tuturorelementelor lui A.

O r -combinare a lui A este o submultime {a1, a2, . . . , ar} cu relemente a lui A.

Exemple

3, 1, 2 si 1, 3, 2 sunt permutari ale multimii {1, 2, 3}.3, 1 si 1, 2 sunt 2-permutari ale multimii {1, 2, 3}.2-combinarile lui {1, 2, 3} sunt submultimille {1, 2}, {1, 3}, {2, 3}

P(n, r) := nr. de r -permutari ale unei multimi cu n elemente.

C (n, r) := nr. de r -combinari ale unei multimi cu n elemente.Notatie alternativa:

(nr

).

Teoria Grafurilor si Combinatorica

Aranjamente, permutari si combinariDefinitii

Presupunem ca A este o multime finita cu n elemente.

Un aranjament de n luate cate r (sau r -permutare) al lui A este osecventa ordonata a1, a2, . . . , ar de elemente distincte din A.O permutare a lui A este un aranjament a1, a2, . . . , an al tuturorelementelor lui A.

O r -combinare a lui A este o submultime {a1, a2, . . . , ar} cu relemente a lui A.

Exemple

3, 1, 2 si 1, 3, 2 sunt permutari ale multimii {1, 2, 3}.3, 1 si 1, 2 sunt 2-permutari ale multimii {1, 2, 3}.2-combinarile lui {1, 2, 3} sunt submultimille {1, 2}, {1, 3}, {2, 3}

P(n, r) := nr. de r -permutari ale unei multimi cu n elemente.

C (n, r) := nr. de r -combinari ale unei multimi cu n elemente.Notatie alternativa:

(nr

).

Teoria Grafurilor si Combinatorica

PermutariCare este valoarea lui P(n, r)?

Teorema

P(n, r) = n (n 1) . . . (n r + 1).

Demonstratie

A = {a1, . . . , an}r -permutare = p1, p2, ..., pr cu p1, p2, . . . , pr A

elemente distincte.

subprobleme distincte de selectiep1 A p2 A {p1} . . . pr A {p1, . . . , pr1}

nr. de posib. n n 1 . . . n r + 1

P(n, r) = n (n 1) . . . (n r + 1) =n!

(n r)!Remarca. n! reprezinta produsul 1 2 . . . (n 1) n.n! se numeste n factorial. Prin definitie, 0! = 1.

Teoria Grafurilor si Combinatorica

PermutariCare este valoarea lui P(n, r)?

Teorema

P(n, r) = n (n 1) . . . (n r + 1).

DemonstratieA = {a1, . . . , an}r -permutare = p1, p2, ..., pr cu p1, p2, . . . , pr A

elemente distincte.

subprobleme distincte de selectiep1 A p2 A {p1} . . . pr A {p1, . . . , pr1}

nr. de posib. n n 1 . . . n r + 1

P(n, r) = n (n 1) . . . (n r + 1) =n!

(n r)!Remarca. n! reprezinta produsul 1 2 . . . (n 1) n.n! se numeste n factorial. Prin definitie, 0! = 1.

Teoria Grafurilor si Combinatorica

PermutariCare este valoarea lui P(n, r)?

Teorema

P(n, r) = n (n 1) . . . (n r + 1).

DemonstratieA = {a1, . . . , an}r -permutare = p1, p2, ..., pr cu p1, p2, . . . , pr A

elemente distincte.

subprobleme distincte de selectiep1 A p2 A {p1} . . . pr A {p1, . . . , pr1}

nr. de posib. n n 1 . . . n r + 1

P(n, r) = n (n 1) . . . (n r + 1) =n!

(n r)!

Remarca. n! reprezinta produsul 1 2 . . . (n 1) n.n! se numeste n factorial. Prin definitie, 0! = 1.

Teoria Grafurilor si Combinatorica

PermutariCare este valoarea lui P(n, r)?

Teorema

P(n, r) = n (n 1) . . . (n r + 1).

DemonstratieA = {a1, . . . , an}r -permutare = p1, p2, ..., pr cu p1, p2, . . . , pr A

elemente distincte.

subprobleme distincte de selectiep1 A p2 A {p1} . . . pr A {p1, . . . , pr1}

nr. de posib. n n 1 . . . n r + 1

P(n, r) = n (n 1) . . . (n r + 1) =n!

(n r)!Remarca. n! reprezinta produsul 1 2 . . . (n 1) n.n! se numeste n factorial. Prin definitie, 0! = 1.

Teoria Grafurilor si Combinatorica

Permutari si CombinariPropertati

Teorema

P(n, r) = C (n, r) P(r , r).

Demonstratie combinatoriala

Enumerarea r -combinarilor unei multimi cu n elemente poatefi descompusa n o secventa de 2 activitati:

1 Se selecteaza r elemente din multimea cu n elemente2 Se aranjeaza elementele selectate.

Exista C (n, r) moduli de a selecta r elemente din o multime cun elemente activitatea (1) se poate face n C (n, r) moduri.Exista P(r , r) moduli de aranjare a celor r elemente selectate activitatea (2) se poate face n P(r , r) moduri.

conform regulii produsului, exista P(n, r) = C (n, r) P(r , r)moduri.

Teoria Grafurilor si Combinatorica

Permutari si CombinariPropertati

Teorema

P(n, r) = C (n, r) P(r , r).

Demonstratie combinatoriala

Enumerarea r -combinarilor unei multimi cu n elemente poatefi descompusa n o secventa de 2 activitati:

1 Se selecteaza r elemente din multimea cu n elemente2 Se aranjeaza elementele selectate.

Exista C (n, r) moduli de a selecta r elemente din o multime cun elemente activitatea (1) se poate face n C (n, r) moduri.Exista P(r , r) moduli de aranjare a celor r elemente selectate activitatea (2) se poate face n P(r , r) moduri.

conform regulii produsului, exista P(n, r) = C (n, r) P(r , r)moduri.

Teoria Grafurilor si Combinatorica

Permutari si CombinariPropertati

Teorema

P(n, r) = C (n, r) P(r , r).

Demonstratie combinatoriala

Enumerarea r -combinarilor unei multimi cu n elemente poatefi descompusa n o secventa de 2 activitati:

1 Se selecteaza r elemente din multimea cu n elemente2 Se aranjeaza elementele selectate.

Exista C (n, r) moduli de a selecta r elemente din o multime cun elemente activitatea (1) se poate face n C (n, r) moduri.

Exista P(r , r) moduli de aranjare a celor r elemente selectate activitatea (2) se poate face n P(r , r) moduri.

conform regulii produsului, exista P(n, r) = C (n, r) P(r , r)moduri.

Teoria Grafurilor si Combinatorica

Permutari si CombinariPropertati

Teorema

P(n, r) = C (n, r) P(r , r).

Demonstratie combinatoriala

Enumerarea r -combinarilor unei multimi cu n elemente poatefi descompusa n o secventa de 2 activitati:

1 Se selecteaza r elemente din multimea cu n elemente2 Se aranjeaza elementele selectate.

Exista C (n, r) moduli de a selecta r elemente din o multime cun elemente activitatea (1) se poate face n C (n, r) moduri.Exista P(r , r) moduli de aranjare a celor r elemente selectate activitatea (2) se poate face n P(r , r) moduri.

conform regulii produsului, exista P(n, r) = C (n, r) P(r , r)moduri.

Teoria Grafurilor si Combinatorica

Permutari si CombinariPropertati

Teorema

P(n, r) = C (n, r) P(r , r).

Demonstratie combinatoriala

Enumerarea r -combinarilor unei multimi cu n elemente poatefi descompusa n o secventa de 2 activitati:

1 Se selecteaza r elemente din multimea cu n elemente2 Se aranjeaza elementele selectate.

Exista C (n, r) moduli de a selecta r elemente din o multime cun elemente activitatea (1) se poate face n C (n, r) moduri.Exista P(r , r) moduli de aranjare a celor r elemente selectate activitatea (2) se poate face n P(r , r) moduri.

conform regulii produsului, exista P(n, r) = C (n, r) P(r , r)moduri.

Teoria Grafurilor si Combinatorica

CombinariNumararea combinarilor

C (n, r) =?

Stim ca P(n, r) = n!(nr)!

Am demonstrat deja ca P(n, r) = C (n, r) P(r , r)

C (n, r) = P(n, r)P(r , r)

=n!

(n r)! 0!r !

=n!

r !(n r)!

Teoria Grafurilor si Combinatorica

CombinariNumararea combinarilor

C (n, r) =?

Stim ca P(n, r) = n!(nr)!

Am demonstrat deja ca P(n, r) = C (n, r) P(r , r)

C (n, r) = P(n, r)P(r , r)

=n!

(n r)! 0!r !

=n!

r !(n r)!

Teoria Grafurilor si Combinatorica

CombinariNumararea combinarilor

C (n, r) =?

Stim ca P(n, r) = n!(nr)!

Am demonstrat deja ca P(n, r) = C (n, r) P(r , r)

C (n, r) = P(n, r)P(r , r)

=n!

(n r)! 0!r !

=n!

r !(n r)!

Teoria Grafurilor si Combinatorica

CombinariNumararea combinarilor

C (n, r) =?

Stim ca P(n, r) = n!(nr)!

Am demonstrat deja ca P(n, r) = C (n, r) P(r , r)

C (n, r) = P(n, r)P(r , r)

=n!

(n r)! 0!r !

=n!

r !(n r)!

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Proprietati ale combinatiilor

Teorema

C (n, r) = C (n 1, r 1) + C (n 1, r) pentru toti n > r > 0.

Demonstratie combinatoriala

Fie S = {a1, a2, . . . , an}. Exista C (n, r) moduri de a selecta relemente din S . Avem 2 cazuri distincte:

1 Selectia celor r elemente din S contine a1. Fie N1 numarul deastfel de selectii.

2 Selectia celor r elemente din S nu contine a1. Fie N2 numarulde astfel de selectii.

Conform regulii sumei, C (n, r) = N1 + N2. Insa:

N1 = C (n 1, r 1) deoarece N1 reprezinta numarul deselectii de submultimi de r 1 elemente din {a2, . . . , an}N2 = C (n 1, r) deoarece N2 reprezinta numarul de selectii desubmultimi de r elemente din {a2, . . . , an}

C (n, r) = N1 + N2 = C (n 1, r 1) + C (n 1, r).

Teoria Grafurilor si Combinatorica

Exercitii

1 Dati o demonstratie algebrica, folosind formula pentruC (n, r), a faptului ca C (n, r) = C (n 1, r 1) + C (n 1, r).

2 Dati o demonstratie combinatoriala a faptului caC (n, r) = C (n, n r).

3 In cate moduri se pot alege primul, al doilea si al treileacastigator din 100 de participanti la un concurs?

4 In cate moduri se pot aseza n persoane la o masa rotunda?

5 Cate permutari ale literelor ABCDEFGH contin sirul ABC?

6 Cate siruri de biti cu lungimea n contin cifra 1 de exact r ori?

Teoria Grafurilor si Combinatorica

Permutari generalizate si combinariPermutari cu repetitie

In multe probleme de numarare se doreste folosirea repetata aunor elemente.

Permutarile si combinarile presupun ca fiecare element apare osingura data.

O r -permutare cu repetitie a unei multimi cu n elemente estean aranjament de r elemente din acea multime, n care fiecareelement poate sa apara de mai multe ori.

Exemplu

Cate siruri cu lungimea n se pot forma cu litere mici si mari dinalfabetul latin?Raspuns: |Alfabetlatin| = 52 52n siruri (cf. regulii produsului)

Teorema

Numarul de r -permutari cu repetitie al unei multimi cu n elementeeste nr .

Teoria Grafurilor si Combinatorica

Permutari generalizate si combinariPermutari cu repetitie

In multe probleme de numarare se doreste folosirea repetata aunor elemente.

Permutarile si combinarile presupun ca fiecare element apare osingura data.

O r -permutare cu repetitie a unei multimi cu n elemente estean aranjament de r elemente din acea multime, n care fiecareelement poate sa apara de mai multe ori.

Exemplu

Cate siruri cu lungimea n se pot forma cu litere mici si mari dinalfabetul latin?Raspuns: |Alfabetlatin| = 52 52n siruri (cf. regulii produsului)

Teorema

Numarul de r -permutari cu repetitie al unei multimi cu n elementeeste nr .

Teoria Grafurilor si Combinatorica

Permutari generalizate si combinariPermutari cu repetitie

In multe probleme de numarare se doreste folosirea repetata aunor elemente.

Permutarile si combinarile presupun ca fiecare element apare osingura data.

O r -permutare cu repetitie a unei multimi cu n elemente estean aranjament de r elemente din acea multime, n care fiecareelement poate sa apara de mai multe ori.

Exemplu

Cate siruri cu lungimea n se pot forma cu litere mici si mari dinalfabetul latin?Raspuns: |Alfabetlatin| = 52 52n siruri (cf. regulii produsului)

Teorema

Numarul de r -permutari cu repetitie al unei multimi cu n elementeeste nr .

Teoria Grafurilor si Combinatorica

Permutari generalizate si combinariPermutari cu repetitie

In multe probleme de numarare se doreste folosirea repetata aunor elemente.

Permutarile si combinarile presupun ca fiecare element apare osingura data.

O r -permutare cu repetitie a unei multimi cu n elemente estean aranjament de r elemente din acea multime, n care fiecareelement poate sa apara de mai multe ori.

Exemplu

Cate siruri cu lungimea n se pot forma cu litere mici si mari dinalfabetul latin?Raspuns: |Alfabetlatin| = 52 52n siruri (cf. regulii produsului)

Teorema

Numarul de r -permutari cu repetitie al unei multimi cu n elementeeste nr .

Teoria Grafurilor si Combinatorica

Permutari generalizate si combinariPermutari cu repetitie

In multe probleme de numarare se doreste folosirea repetata aunor elemente.

Permutarile si combinarile presupun ca fiecare element apare osingura data.

O r -permutare cu repetitie a unei multimi cu n elemente estean aranjament de r elemente din acea multime, n care fiecareelement poate sa apara de mai multe ori.

Exemplu

Cate siruri cu lungimea n se pot forma cu litere mici si mari dinalfabetul latin?Raspuns: |Alfabetlatin| = 52 52n siruri (cf. regulii produsului)

Teorema

Numarul de r -permutari cu repetitie al unei multimi cu n elementeeste nr .

Teoria Grafurilor si Combinatorica

Combinari cu repetitie

O r -combinare cu repetitie a unei multimi cu n elemente esteo selectie de r elemente din multimea respectiva, n carefiecare element poate sa apara de oricate ori.

Q: Care este numarul r -combinarilor cu repetitie al unei multimicu n elemente?

Exemplu

In cate feluri se pot selecta 5 bancnote din o cutie cu bani carecontine bancnote de $1, $2, $5, $10, $20, $50. Presupunem ca:ordinea de selectie a bancnotelor nu conteaza; exista cel putin 5bancnote de fiecare denominatie.

Teoria Grafurilor si Combinatorica

Combinari cu repetitieExemplu continuat

Cinci bancnote nu neaparat distincte = o 5-combinare cu repetitie dinmultimea {$1, $2, $5, $10, $20, $50} de tipuri de bancnote = a plasare decinci * n sertarele cutiei de bani ilustrate mai jos:

Numarul de * n un sertar reprezinta numarul de bancnote luate dinacel sertar.

Numarul de 5-combinari cu repetitie al unei multimi cu 6 elemente =numarul de moduri de plasare a 5 * n 6 sertare.

$1 $2 $5 $10 $20 $50cutie de bani cu 6 tipuri de bancnote

|||||

|| |||

Teoria Grafurilor si Combinatorica

Combinari cu repetitie

Observatie

Fiecare plasare de 5 * n 6 sertare posibile este descrisa unicde catre un sir de 5 * si 5 bare rosii.

In general, numarul de r -combinari cu repetitie al unei multimicu n elemente = numarul de siruri cu r * si n 1 bare rosii.

I: In cate feluri putem aranja n 1 bare si r *?

R: Secventa are lungimea n + r 1 secventa are n r + 1 pozitii trebuie sa alegem r pozitii din cele n r + 1 care sa fie

ocupate cu *; celelalte vor fi ocupate cu bare.

Exista C (n + r 1, r) de selectii de acest fel.

Teorema

Numarul de r -combinari cu repetitie al unei multimi cu n elementeeste C (r + n 1, r).

Teoria Grafurilor si Combinatorica

Combinari cu repetitie

Observatie

Fiecare plasare de 5 * n 6 sertare posibile este descrisa unicde catre un sir de 5 * si 5 bare rosii.

In general, numarul de r -combinari cu repetitie al unei multimicu n elemente = numarul de siruri cu r * si n 1 bare rosii.

I: In cate feluri putem aranja n 1 bare si r *?R: Secventa are lungimea n + r 1

secventa are n r + 1 pozitii trebuie sa alegem r pozitii din cele n r + 1 care sa fie

ocupate cu *; celelalte vor fi ocupate cu bare.

Exista C (n + r 1, r) de selectii de acest fel.

Teorema

Numarul de r -combinari cu repetitie al unei multimi cu n elementeeste C (r + n 1, r).

Teoria Grafurilor si Combinatorica

Combinari cu repetitie

Observatie

Fiecare plasare de 5 * n 6 sertare posibile este descrisa unicde catre un sir de 5 * si 5 bare rosii.

In general, numarul de r -combinari cu repetitie al unei multimicu n elemente = numarul de siruri cu r * si n 1 bare rosii.

I: In cate feluri putem aranja n 1 bare si r *?R: Secventa are lungimea n + r 1

secventa are n r + 1 pozitii trebuie sa alegem r pozitii din cele n r + 1 care sa fie

ocupate cu *; celelalte vor fi ocupate cu bare.

Exista C (n + r 1, r) de selectii de acest fel.

Teorema

Numarul de r -combinari cu repetitie al unei multimi cu n elementeeste C (r + n 1, r).

Teoria Grafurilor si Combinatorica

Combinari cu repetitie

Observatie

Fiecare plasare de 5 * n 6 sertare posibile este descrisa unicde catre un sir de 5 * si 5 bare rosii.

In general, numarul de r -combinari cu repetitie al unei multimicu n elemente = numarul de siruri cu r * si n 1 bare rosii.

I: In cate feluri putem aranja n 1 bare si r *?R: Secventa are lungimea n + r 1

secventa are n r + 1 pozitii trebuie sa alegem r pozitii din cele n r + 1 care sa fie

ocupate cu *; celelalte vor fi ocupate cu bare.

Exista C (n + r 1, r) de selectii de acest fel.

Teorema

Numarul de r -combinari cu repetitie al unei multimi cu n elementeeste C (r + n 1, r).

Teoria Grafurilor si Combinatorica

Permutari si combinariRezumat

Tip Repetitii Formulaadmise?

r -permutari Nu P(n, r) =n!

(n r)!

r -combinari Nu C (n, r) =n!

r !(n r)!r -permutari Da nr

cu repetitie

r -combinari Da C (n + r 1, r) =(n + r 1)!r !(n 1)!

cu repetitie

Teoria Grafurilor si Combinatorica

Permutari cu elemente nediferentiate

Problema

Cate siruri distincte se pot obtine reordonand literele siruluiSUCCES?

SUCCES contine 2 S-uri, 2 C-uri, 1U, 1 E.

alegerea locurilor lui S-uri: C (6, 2) 4 locuri ramase.alegerea locurilor pentru C-uri: C (4, 2) 2 locuri ramase.alegerea locului pentru U: C (2, 1) 1 loc ramas.alegerea locului pentru E: C (1, 1).

cf. regulii produsului, numarul este

C (6, 2) C (4, 2) C (2, 1) C (1, 1) = 6!2!2!1!1!

Teoria Grafurilor si Combinatorica

Permutari cu elemente nediferentiate

Problema

Cate siruri distincte se pot obtine reordonand literele siruluiSUCCES?

SUCCES contine 2 S-uri, 2 C-uri, 1U, 1 E.

alegerea locurilor lui S-uri: C (6, 2) 4 locuri ramase.alegerea locurilor pentru C-uri: C (4, 2) 2 locuri ramase.alegerea locului pentru U: C (2, 1) 1 loc ramas.alegerea locului pentru E: C (1, 1).

cf. regulii produsului, numarul este

C (6, 2) C (4, 2) C (2, 1) C (1, 1) = 6!2!2!1!1!

Teoria Grafurilor si Combinatorica

Permutari cu elemente nediferentiate

Teorema

Numarul de permutari diferite de n obiecte, dintre care n1 suntelemente nediferentiate de tip 1, n2 sunt elemente nediferentiatede tip 2, . . . , si nk sunt elemente nediferentiate de tip nk , este

n!

n1!n2! nk !.

Teoria Grafurilor si Combinatorica

Numere binomiale si multinomiale

Numerele binomiale sunt coeficientii cn,k din formulabinomului

(x + y)n =n

k=0

cn,k xnkyk

Numerele multinomiale sunt coeficientii cn,k1,...,kr din formula

(x1 + . . . + xr )n =

nk1+...+kr=n

cn,k1,...,kr xk11 x

k22 . . . x

krr

Exemple

(x + y)3 = 1 x3 + 3 x2y + 3 x y2 + 1 y3

(x1 + x2 + x3)2 = 1 x21 + 1 x22 + 1 x23 +

2 x1x2 + 2 x1x3 + 2 x2x3

Teoria Grafurilor si Combinatorica

Numere binomiale si multinomialeFormule de calcul

(x1 + . . . + xr )n =

nk1+...+kr=n

n!

k1! . . . kr ! xk11 x

k22 . . . x

krr

Demonstratie combinatoriala

(x1 + . . . + xr )n =

n paranteze (x1 + . . . + xr ) . . . (x1 + . . . + xr )

In cate feluri poate fi produs monomul xk11 . . . xkrr ?B Alegem k1 paranteze din care provine x1 C (n, k1) posibilitati.B Alegem k2 paranteze din care provine x2 C (n k1, k2) posibilitati.

. . .

B Alegem kr paranteze din care provine xr C (n r1

i=1 ki , kr )posibilitati.

cf. regulii produsului, nr. de aparitii al lui xk11 . . . xkrr n partea

dreapta este C (n, k1)C (n k1, k2) . . . C (n r1

i=1 ki , kr ) =n!

k1! . . . kr !Teoria Grafurilor si Combinatorica

Numere binomiale si multinomialeConcluzii

Pentru formula n!k1!...kr ! cu k1 + . . . + kr = n se foloseste

adesea notatia( nk1,...,kr

).

Formula binomiala este

(x + y)n =n

k=0

(n

k

)xkynk

Formula multinomiala este

(x1 + . . . + xr )n =

k1+...+kr=n

(n

k1, . . . , kr

)xk11 . . . x

krr

Remarca.(nk

)=( nk,nk

)si

(x1 + x2)n =

nk=0

(n

k

)xk1 x

nk2 =

k1+k2=n

(n

k1, k2

)xk11 x

k22 .

Teoria Grafurilor si Combinatorica