Teoria Grafurilor ˘si Combinatoric a · 2019. 1. 18. · 5 Teoria lui Polya de num arare 6...

100
Teoria Grafurilor ¸ si Combinatoric˘ a Curs 1: Introducere. Principii de num˘ arare. Aranjamente, permut˘ ari ¸ si combin˘ ari octombrie 2018 Teoria Grafurilor ¸ si Combinatoric˘ a

Transcript of Teoria Grafurilor ˘si Combinatoric a · 2019. 1. 18. · 5 Teoria lui Polya de num arare 6...

  • Teoria Grafurilor şi CombinatoricăCurs 1: Introducere.

    Principii de numărare. Aranjamente, permutări şi combinări

    octombrie 2018

    Teoria Grafurilor şi Combinatorică

  • Scopul cursului

    Familiarizare cu noţiunile de bază din combinatorică şi teoriagrafurilor

    Cuprins

    1 Principii de numărare, permutări şi combinări2 Metode de enumerare, principiul incluziunii şi excluziunii3 Combinări4 Structura ciclică a permutărilor. Tehnici avansate de numărare5 Teoria lui Polya de numărare6 Noţiuni fundamentale de teoria grafurilor7 Reţele de transport8 Tipuri şi structuri de date pentru grafuri9 Arbori: definiţii, generare, arbori de cost minim

    10 Drumuri, circuite, căi şi cicluri11 Problema comis-voiajorului. Grafuri planare12 Colorarea grafurilor. Teoria lui Ramsey13 Cuplaje

    Teoria Grafurilor şi Combinatorică

  • Aspecte organizatorice

    Curs: Mircea MarinSeminar: Mircea Marin & Gatină Claudiu

    Pagina web:https://staff.fmi.uvt.ro/~mircea.marin/lectures/TGC

    Material de curs: disponibil din pagina web

    Evaluare: 50% probă scrisă (examen final), 50% seminar

    Teoria Grafurilor şi Combinatorică

  • Descrierea primului curs

    Principii fundamentale de numărare

    Regula produsuluiRegula sumeiDemonstraţii combinatoriale; exemple

    Tehnici de numărare pentru

    combinări - selecţii neordonate de elemente distincte din omulţime finităpermutări - selecţii ordonate de elemente distincte din omulţime finită

    Generalizări

    permutări cu repetiţiecombinări cu repetiţiepermutări cu elemente nediferenţiate

    Numere binomiale şi multinomiale

    Teoria Grafurilor şi Combinatorică

  • Principii fundamentale de numărare1. Regula produsului

    Regula produsului. Dacă o procedură poate fi descompusă ı̂n o secvenţăde 2 proceduri astfel ı̂ncât

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

    atunci există n1 · n2 feluri de a efectua acea procedură.

    Regula generalizată a produsului. Dacă o procedură poate fi descompusăı̂n o secvenţă de m proceduri astfel ı̂ncât

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

    atunci există n1 · n2 · . . . · nm feluri de a efectua aceaprocedură.

    Teoria Grafurilor şi Combinatorică

  • Principii fundamentale de numărare1. Regula produsului

    Regula produsului. Dacă o procedură poate fi descompusă ı̂n o secvenţăde 2 proceduri astfel ı̂ncât

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

    atunci există n1 · n2 feluri de a efectua acea procedură.

    Regula generalizată a produsului. Dacă o procedură poate fi descompusăı̂n o secvenţă de m proceduri astfel ı̂ncât

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

    atunci există n1 · n2 · . . . · nm feluri de a efectua aceaprocedură.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    Răspuns

    Alocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    Răspuns

    Alocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    RăspunsAlocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.

    Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    RăspunsAlocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.

    Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    RăspunsAlocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (1) O companie are 12 birouri şi 2 angajaţi: Gheorghe şi Ion. Încâte feluri se pot aloca birouri diferite celor doi angajaţi?

    RăspunsAlocarea se poate descompune ı̂n 2 operaţii distincte: alocareaunui birou pentru Gheorghe, urmată de alocarea unui biroupentru Ion.Există 12 alternative pentru prima operaţie, deoarece sunt 12birouri ı̂n total.Există 11 alternative pentru operaţia a doua, deoarece biroulalocat lui Gheorghe nu mai este liber.

    ⇒ conform regulii produsului, sunt 12 · 11 = 132 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    Răspuns

    Problema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    Răspuns

    Problema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.

    conform regulii produsului, există 26 · 50 = 1300 variante.(3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    Răspuns

    Fiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    RăspunsFiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.

    ⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsului

    (2) Într-o sală de laborator, scaunele sunt numerotate cu o literămare urmată de un număr ı̂ntre 1 şi 50. Câte scaune pot finumerotate diferit ı̂n felul acesta?Se presupune că sunt 26 litere mari.

    RăspunsProblema poate fi descompusă ı̂n o secvenţă de 2 subprobleme:prima este alegerea unei litere din cele 26 posibile, iarurmătoarea este alegerea unui număr din cele 50 posibile.conform regulii produsului, există 26 · 50 = 1300 variante.

    (3) Câte şiruri diferite de 7 biţi există?

    RăspunsFiecare din cei 7 biţi poate fi ales ı̂n 2 feluri: 0 sau 1.

    ⇒ conform regulii produsului, există 27 = 128 variante.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor dintre 2 mulţimi finite

    (4) Câte funcţii sunt de la o mulţime cu m elemente la o mulţimecu n elemente?

    Răspuns f : {a1, . . . , am} → {b1, . . . , bn}

    Definirea unei astfel de funcţii poate fi descompusă ı̂n m etapeindependente: ı̂n etapa i se fixează valoarea lui f (ai )Etapa i are n posibilităţi, deoarece putem alege pentru f (ai )orice valoare din mulţimea {b1, . . . , bn}

    ⇒ conform regulii produsului, numărul de funcţii esten · . . . · n︸ ︷︷ ︸

    m ori

    = nm

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor dintre 2 mulţimi finite

    (4) Câte funcţii sunt de la o mulţime cu m elemente la o mulţimecu n elemente?

    Răspuns f : {a1, . . . , am} → {b1, . . . , bn}Definirea unei astfel de funcţii poate fi descompusă ı̂n m etapeindependente: ı̂n etapa i se fixează valoarea lui f (ai )

    Etapa i are n posibilităţi, deoarece putem alege pentru f (ai )orice valoare din mulţimea {b1, . . . , bn}

    ⇒ conform regulii produsului, numărul de funcţii esten · . . . · n︸ ︷︷ ︸

    m ori

    = nm

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor dintre 2 mulţimi finite

    (4) Câte funcţii sunt de la o mulţime cu m elemente la o mulţimecu n elemente?

    Răspuns f : {a1, . . . , am} → {b1, . . . , bn}Definirea unei astfel de funcţii poate fi descompusă ı̂n m etapeindependente: ı̂n etapa i se fixează valoarea lui f (ai )Etapa i are n posibilităţi, deoarece putem alege pentru f (ai )orice valoare din mulţimea {b1, . . . , bn}

    ⇒ conform regulii produsului, numărul de funcţii esten · . . . · n︸ ︷︷ ︸

    m ori

    = nm

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor dintre 2 mulţimi finite

    (4) Câte funcţii sunt de la o mulţime cu m elemente la o mulţimecu n elemente?

    Răspuns f : {a1, . . . , am} → {b1, . . . , bn}Definirea unei astfel de funcţii poate fi descompusă ı̂n m etapeindependente: ı̂n etapa i se fixează valoarea lui f (ai )Etapa i are n posibilităţi, deoarece putem alege pentru f (ai )orice valoare din mulţimea {b1, . . . , bn}

    ⇒ conform regulii produsului, numărul de funcţii esten · . . . · n︸ ︷︷ ︸

    m ori

    = nm

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]

    Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}

    Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.

    Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}.

    ...Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea funcţiilor injective dintre 2 mulţimi finite

    (5) Câte funcţii injective sunt de la o mulţime cu m elemente la omulţime cu n elemente?[Observaţi că trebuie să avem m ≤ n.]Răspuns: descompunem problema ı̂n n subprobleme distincte

    Presupunem că f : {a1, a2, . . . , am} → {b1, b2, . . . , bn}Există n căi de alegere a valorii luif (a1) ∈ {b1, . . . , bn}.Există n − 1 căi de alegere a valorii luif (a2) ∈ {b1, . . . , bn} − {f (a1)}....Există n − (m − 1) căi de alegere a valorii luif (am) ∈ {b1, . . . , bn} − {f (a1), . . . , f (am−1)}.

    ⇒ conform regulii produsului, există n · (n − 1) · . . . · (n −m + 1)astfel de funcţii.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    Demonstraţie

    Pentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bn

    Definirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii produsuluiNumărarea submulţimilor unei mulţimi finite

    (6) Numărul de submulţimi al unei mulţimi finite S = {a1, a2, . . . , an}este 2n.

    DemonstraţiePentru fiecare submulţime B a lui A definim şirul de biţib1b2 . . . bn cu

    bi =

    {1 dacă ai ∈ B0 dacă ai 6∈ B

    Numărul de submulţimi al lui A coincide cu numărul de şiruridistincte de biţi b1 . . . bnDefinirea a unui şir de biţi de lungime n se poate descompuneı̂n n subprobleme distincte: subproblema i fixează valoareabitului bi

    ⇒ conform regulii produsului, există 2 · . . . · 2︸ ︷︷ ︸n ori

    = 2n astfel de şiruri.

    ⇒ numărul de submulţimi al unei mulţimi S cu n elemente este 2n.

    Teoria Grafurilor şi Combinatorică

  • Principii fundamentale de numărare2. Regula sumei

    Regula sumei. Dacă o procedură se poate efectua ı̂n 2 feluri, pentru feluli sunt ni variante, şi nici una din variantele de primul felnu coincide cu vreo variantă de felul 2, atunci existăn1 + n2 variante de a efectua procedura.

    Regula generalizată a sumei. Presupunem că o procedură poate fiefectuată ı̂n m feluri, pentru felul i sunt ni variante, şivariantele efectuate ı̂n feluri diferite sunt diferite. Atunciexistă n1 + n2 + . . . + nm variante de a efectua procedurarespectivă.

    Teoria Grafurilor şi Combinatorică

  • Principii fundamentale de numărare2. Regula sumei

    Regula sumei. Dacă o procedură se poate efectua ı̂n 2 feluri, pentru feluli sunt ni variante, şi nici una din variantele de primul felnu coincide cu vreo variantă de felul 2, atunci existăn1 + n2 variante de a efectua procedura.

    Regula generalizată a sumei. Presupunem că o procedură poate fiefectuată ı̂n m feluri, pentru felul i sunt ni variante, şivariantele efectuate ı̂n feluri diferite sunt diferite. Atunciexistă n1 + n2 + . . . + nm variante de a efectua procedurarespectivă.

    Teoria Grafurilor şi Combinatorică

  • Principii fundamentale de numărare2. Regula sumei

    Regula sumei. Dacă o procedură se poate efectua ı̂n 2 feluri, pentru feluli sunt ni variante, şi nici una din variantele de primul felnu coincide cu vreo variantă de felul 2, atunci existăn1 + n2 variante de a efectua procedura.

    Regula generalizată a sumei. Presupunem că o procedură poate fiefectuată ı̂n m feluri, pentru felul i sunt ni variante, şivariantele efectuate ı̂n feluri diferite sunt diferite. Atunciexistă n1 + n2 + . . . + nm variante de a efectua procedurarespectivă.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii sumei

    (1) Un student trebuie să aleagă un proiect de programare din 3liste. Prima listă conţine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare ı̂n mai multe liste. Câte proiecteposibile există?

    Răspuns

    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 posibilităţi.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii sumei

    (1) Un student trebuie să aleagă un proiect de programare din 3liste. Prima listă conţine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare ı̂n mai multe liste. Câte proiecteposibile există?

    Răspuns

    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 posibilităţi.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii sumei

    (1) Un student trebuie să aleagă un proiect de programare din 3liste. Prima listă conţine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare ı̂n mai multe liste. Câte proiecteposibile există?

    RăspunsProiectul 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 posibilităţi.

    Teoria Grafurilor şi Combinatorică

  • Aplicaţii ale regulii sumei

    (1) Un student trebuie să aleagă un proiect de programare din 3liste. Prima listă conţine 9 proiecte, a doua 8, iar a treia 12.Nici un proiect nu apare ı̂n mai multe liste. Câte proiecteposibile există?

    RăspunsProiectul 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 posibilităţi.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).

    ⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).

    ⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).

    ⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Probleme mai complexe de numărare

    Multe probleme de numărare nu pot fi rezolvate folosind doar regulasumei sau doar regula produsului, ı̂nsă pot fi rezolvate dacă folosimambele reguli.

    Exemple

    (1) Se ştie că o parolă este un şir ı̂ntre 6 şi 8 caractere lungime, şi căfiecare caracter este fie o literă mare sau o cifră zecimală. Fiecareparolă conţine cel puţin o cifră. Câte parole posibile sunt?

    Răspuns

    Fie P numărul total de parole, şi P6, P7 şi P8 numărul 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 numărul de şiruri de litere mari şi cifre cu lungimea m.Conform regulii produsului, Wm = (26 + 10)

    m = 36m

    Fie Nm numărul de şiruri de litere mari cu lungimea m.Conform regulii produsului, Nm = 26

    m.

    Se observă uşor că Pm = Wm − Nm (explicaţi de ce!).⇒ P = W6−N6+W7−N7+W8−N8 = 366−266+367−267+368−268.

    Teoria Grafurilor şi Combinatorică

  • Exemple mai complexe de numărare

    (2) În câte feluri putem alege 2 cărţi scrise ı̂n limbaje diferitedintr-o colecţie de 5 cărţi scrise ı̂n română, 9 scrise ı̂n engleză,şi 10 ı̂n germană?

    Răspuns

    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 şi Combinatorică

  • Exemple mai complexe de numărare

    (2) În câte feluri putem alege 2 cărţi scrise ı̂n limbaje diferitedintr-o colecţie de 5 cărţi scrise ı̂n română, 9 scrise ı̂n engleză,şi 10 ı̂n germană?

    Răspuns

    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 şi Combinatorică

  • Demonstraţii combinatoriale

    O demonstraţie combinatorială este o demonstraţie carefoloseşte argumente de numărare, precum regula sumei şiregula produsului pentru a demonstra ceva.

    Demonstraţiile ilustrate mai devreme sunt combinatoriale.

    Teoria Grafurilor şi Combinatorică

  • Aranjamente, permutări şi combinăriDefiniţii

    Presupunem că A este o mulţime finită cu n elemente.

    Un aranjament de n luate câte r (sau r -permutare) al lui A este osecvenţă ordonată 〈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 submulţime {a1, a2, . . . , ar} cu relemente a lui A.

    Exemple

    〈3, 1, 2〉 şi 〈1, 3, 2〉 sunt permutări ale mulţimii {1, 2, 3}.〈3, 1〉 şi 〈1, 2〉 sunt 2-permutări ale mulţimii {1, 2, 3}.2-combinările lui {1, 2, 3} sunt submulţimille {1, 2}, {1, 3}, {2, 3}

    P(n, r) := nr. de r -permutări ale unei mulţimi cu n elemente.

    C (n, r) := nr. de r -combinări ale unei mulţimi cu n elemente.Notaţie alternativă:

    (nr

    ).

    Teoria Grafurilor şi Combinatorică

  • Aranjamente, permutări şi combinăriDefiniţii

    Presupunem că A este o mulţime finită cu n elemente.

    Un aranjament de n luate câte r (sau r -permutare) al lui A este osecvenţă ordonată 〈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 submulţime {a1, a2, . . . , ar} cu relemente a lui A.

    Exemple

    〈3, 1, 2〉 şi 〈1, 3, 2〉 sunt permutări ale mulţimii {1, 2, 3}.〈3, 1〉 şi 〈1, 2〉 sunt 2-permutări ale mulţimii {1, 2, 3}.2-combinările lui {1, 2, 3} sunt submulţimille {1, 2}, {1, 3}, {2, 3}

    P(n, r) := nr. de r -permutări ale unei mulţimi cu n elemente.

    C (n, r) := nr. de r -combinări ale unei mulţimi cu n elemente.Notaţie alternativă:

    (nr

    ).

    Teoria Grafurilor şi Combinatorică

  • Aranjamente, permutări şi combinăriDefiniţii

    Presupunem că A este o mulţime finită cu n elemente.

    Un aranjament de n luate câte r (sau r -permutare) al lui A este osecvenţă ordonată 〈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 submulţime {a1, a2, . . . , ar} cu relemente a lui A.

    Exemple

    〈3, 1, 2〉 şi 〈1, 3, 2〉 sunt permutări ale mulţimii {1, 2, 3}.〈3, 1〉 şi 〈1, 2〉 sunt 2-permutări ale mulţimii {1, 2, 3}.2-combinările lui {1, 2, 3} sunt submulţimille {1, 2}, {1, 3}, {2, 3}

    P(n, r) := nr. de r -permutări ale unei mulţimi cu n elemente.

    C (n, r) := nr. de r -combinări ale unei mulţimi cu n elemente.Notaţie alternativă:

    (nr

    ).

    Teoria Grafurilor şi Combinatorică

  • PermutăriCare este valoarea lui P(n, r)?

    Teoremă

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

    Demonstraţie

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

    elemente distincte.

    subprobleme distincte de selecţiep1 ∈ A p2 ∈ A− {p1} . . . pr ∈ A− {p1, . . . , pr−1}

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

    ⇒ P(n, r) = n · (n − 1) · . . . · (n − r + 1) =n!

    (n − r)!Remarcă. n! reprezintă produsul 1 · 2 · . . . · (n − 1) · n.n! se numeşte n factorial. Prin definiţie, 0! = 1.

    Teoria Grafurilor şi Combinatorică

  • PermutăriCare este valoarea lui P(n, r)?

    Teoremă

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

    DemonstraţieA = {a1, . . . , an}r -permutare = 〈p1, p2, ..., pr 〉 cu p1, p2, . . . , pr ∈ A

    elemente distincte.

    subprobleme distincte de selecţiep1 ∈ A p2 ∈ A− {p1} . . . pr ∈ A− {p1, . . . , pr−1}

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

    ⇒ P(n, r) = n · (n − 1) · . . . · (n − r + 1) =n!

    (n − r)!Remarcă. n! reprezintă produsul 1 · 2 · . . . · (n − 1) · n.n! se numeşte n factorial. Prin definiţie, 0! = 1.

    Teoria Grafurilor şi Combinatorică

  • PermutăriCare este valoarea lui P(n, r)?

    Teoremă

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

    DemonstraţieA = {a1, . . . , an}r -permutare = 〈p1, p2, ..., pr 〉 cu p1, p2, . . . , pr ∈ A

    elemente distincte.

    subprobleme distincte de selecţiep1 ∈ A p2 ∈ A− {p1} . . . pr ∈ A− {p1, . . . , pr−1}

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

    ⇒ P(n, r) = n · (n − 1) · . . . · (n − r + 1) =n!

    (n − r)!

    Remarcă. n! reprezintă produsul 1 · 2 · . . . · (n − 1) · n.n! se numeşte n factorial. Prin definiţie, 0! = 1.

    Teoria Grafurilor şi Combinatorică

  • PermutăriCare este valoarea lui P(n, r)?

    Teoremă

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

    DemonstraţieA = {a1, . . . , an}r -permutare = 〈p1, p2, ..., pr 〉 cu p1, p2, . . . , pr ∈ A

    elemente distincte.

    subprobleme distincte de selecţiep1 ∈ A p2 ∈ A− {p1} . . . pr ∈ A− {p1, . . . , pr−1}

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

    ⇒ P(n, r) = n · (n − 1) · . . . · (n − r + 1) =n!

    (n − r)!Remarcă. n! reprezintă produsul 1 · 2 · . . . · (n − 1) · n.n! se numeşte n factorial. Prin definiţie, 0! = 1.

    Teoria Grafurilor şi Combinatorică

  • Permutări şi CombinăriPropertăţi

    Teoremă

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

    Demonstraţie combinatorială

    Enumerarea r -combinărilor unei mulţimi cu n elemente poatefi descompusă ı̂n o secvenţă de 2 activităţi:

    1 Se selectează r elemente din mulţimea cu n elemente2 Se aranjează elementele selectate.

    Există C (n, r) moduri de a selecta r elemente din o mulţimecu n elemente ⇒ activitatea (1) se poate face ı̂n C (n, r)moduri.

    Există P(r , r) moduri de aranjare a celor r elemente selectate⇒ activitatea (2) se poate face ı̂n P(r , r) moduri.

    ⇒ conform regulii produsului, există P(n, r) = C (n, r)× P(r , r)moduri.

    Teoria Grafurilor şi Combinatorică

  • Permutări şi CombinăriPropertăţi

    Teoremă

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

    Demonstraţie combinatorială

    Enumerarea r -combinărilor unei mulţimi cu n elemente poatefi descompusă ı̂n o secvenţă de 2 activităţi:

    1 Se selectează r elemente din mulţimea cu n elemente2 Se aranjează elementele selectate.

    Există C (n, r) moduri de a selecta r elemente din o mulţimecu n elemente ⇒ activitatea (1) se poate face ı̂n C (n, r)moduri.

    Există P(r , r) moduri de aranjare a celor r elemente selectate⇒ activitatea (2) se poate face ı̂n P(r , r) moduri.

    ⇒ conform regulii produsului, există P(n, r) = C (n, r)× P(r , r)moduri.

    Teoria Grafurilor şi Combinatorică

  • Permutări şi CombinăriPropertăţi

    Teoremă

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

    Demonstraţie combinatorială

    Enumerarea r -combinărilor unei mulţimi cu n elemente poatefi descompusă ı̂n o secvenţă de 2 activităţi:

    1 Se selectează r elemente din mulţimea cu n elemente2 Se aranjează elementele selectate.

    Există C (n, r) moduri de a selecta r elemente din o mulţimecu n elemente ⇒ activitatea (1) se poate face ı̂n C (n, r)moduri.

    Există P(r , r) moduri de aranjare a celor r elemente selectate⇒ activitatea (2) se poate face ı̂n P(r , r) moduri.

    ⇒ conform regulii produsului, există P(n, r) = C (n, r)× P(r , r)moduri.

    Teoria Grafurilor şi Combinatorică

  • Permutări şi CombinăriPropertăţi

    Teoremă

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

    Demonstraţie combinatorială

    Enumerarea r -combinărilor unei mulţimi cu n elemente poatefi descompusă ı̂n o secvenţă de 2 activităţi:

    1 Se selectează r elemente din mulţimea cu n elemente2 Se aranjează elementele selectate.

    Există C (n, r) moduri de a selecta r elemente din o mulţimecu n elemente ⇒ activitatea (1) se poate face ı̂n C (n, r)moduri.

    Există P(r , r) moduri de aranjare a celor r elemente selectate⇒ activitatea (2) se poate face ı̂n P(r , r) moduri.

    ⇒ conform regulii produsului, există P(n, r) = C (n, r)× P(r , r)moduri.

    Teoria Grafurilor şi Combinatorică

  • Permutări şi CombinăriPropertăţi

    Teoremă

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

    Demonstraţie combinatorială

    Enumerarea r -combinărilor unei mulţimi cu n elemente poatefi descompusă ı̂n o secvenţă de 2 activităţi:

    1 Se selectează r elemente din mulţimea cu n elemente2 Se aranjează elementele selectate.

    Există C (n, r) moduri de a selecta r elemente din o mulţimecu n elemente ⇒ activitatea (1) se poate face ı̂n C (n, r)moduri.

    Există P(r , r) moduri de aranjare a celor r elemente selectate⇒ activitatea (2) se poate face ı̂n P(r , r) moduri.

    ⇒ conform regulii produsului, există P(n, r) = C (n, r)× P(r , r)moduri.

    Teoria Grafurilor şi Combinatorică

  • CombinăriNumărarea combinărilor

    C (n, r) =?

    Ştim că P(n, r) = n!(n−r)!

    Am demonstrat deja că 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 şi Combinatorică

  • CombinăriNumărarea combinărilor

    C (n, r) =?

    Ştim că P(n, r) = n!(n−r)!

    Am demonstrat deja că 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 şi Combinatorică

  • CombinăriNumărarea combinărilor

    C (n, r) =?

    Ştim că P(n, r) = n!(n−r)!

    Am demonstrat deja că 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 şi Combinatorică

  • CombinăriNumărarea combinărilor

    C (n, r) =?

    Ştim că P(n, r) = n!(n−r)!

    Am demonstrat deja că 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 şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Proprietăţi ale combinaţiilor

    Teoremă

    C (n, r) = C (n − 1, r − 1) + C (n − 1, r) pentru toţi n > r > 0.

    Demonstraţie combinatorială

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

    1 Selecţia celor r elemente din S conţine a1. Fie N1 numărul deastfel de selecţii.

    2 Selecţia celor r elemente din S nu conţine a1. Fie N2 numărulde astfel de selecţii.

    Conform regulii sumei, C (n, r) = N1 + N2. Însă:

    N1 = C (n − 1, r − 1) deoarece N1 reprezintă numărul deselecţii de submulţimi de r − 1 elemente din {a2, . . . , an}N2 = C (n− 1, r) deoarece N2 reprezintă numărul de selecţii desubmulţimi de r elemente din {a2, . . . , an}

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

    Teoria Grafurilor şi Combinatorică

  • Exerciţii

    1 Daţi o demonstraţie algebrică, folosind formula pentruC (n, r), a faptului că C (n, r) = C (n − 1, r − 1) + C (n − 1, r).

    2 Daţi o demonstraţie combinatorială a faptului căC (n, r) = C (n, n − r).

    3 În câte moduri se pot alege primul, al doilea şi al treileacâştigător din 100 de participanţi la un concurs?

    4 În câte moduri se pot aşeza n persoane la o masă rotundă?

    5 Câte permutări ale literelor ABCDEFGH conţin şirul ABC?

    6 Câte şiruri de biţi cu lungimea n conţin cifra 1 de exact r ori?

    Teoria Grafurilor şi Combinatorică

  • Permutări generalizate şi combinăriPermutări cu repetiţie

    În multe probleme de numărare se doreşte folosirea repetată aunor elemente.

    Permutările şi combinările presupun că fiecare element apare osingură dată.

    O r -permutare cu repetiţie a unei mulţimi cu n elemente estean aranjament de r elemente din acea mulţime, ı̂n care fiecareelement poate să apară de mai multe ori.

    Exemplu

    Câte şiruri cu lungimea n se pot forma cu litere mici şi mari dinalfabetul latin?Răspuns: |Alfabetlatin| = 52 ⇒ 52n şiruri (cf. regulii produsului)

    Teoremă

    Numărul de r -permutări cu repetiţie al unei mulţimi cu n elementeeste nr .

    Teoria Grafurilor şi Combinatorică

  • Permutări generalizate şi combinăriPermutări cu repetiţie

    În multe probleme de numărare se doreşte folosirea repetată aunor elemente.

    Permutările şi combinările presupun că fiecare element apare osingură dată.

    O r -permutare cu repetiţie a unei mulţimi cu n elemente estean aranjament de r elemente din acea mulţime, ı̂n care fiecareelement poate să apară de mai multe ori.

    Exemplu

    Câte şiruri cu lungimea n se pot forma cu litere mici şi mari dinalfabetul latin?Răspuns: |Alfabetlatin| = 52 ⇒ 52n şiruri (cf. regulii produsului)

    Teoremă

    Numărul de r -permutări cu repetiţie al unei mulţimi cu n elementeeste nr .

    Teoria Grafurilor şi Combinatorică

  • Permutări generalizate şi combinăriPermutări cu repetiţie

    În multe probleme de numărare se doreşte folosirea repetată aunor elemente.

    Permutările şi combinările presupun că fiecare element apare osingură dată.

    O r -permutare cu repetiţie a unei mulţimi cu n elemente estean aranjament de r elemente din acea mulţime, ı̂n care fiecareelement poate să apară de mai multe ori.

    Exemplu

    Câte şiruri cu lungimea n se pot forma cu litere mici şi mari dinalfabetul latin?Răspuns: |Alfabetlatin| = 52 ⇒ 52n şiruri (cf. regulii produsului)

    Teoremă

    Numărul de r -permutări cu repetiţie al unei mulţimi cu n elementeeste nr .

    Teoria Grafurilor şi Combinatorică

  • Permutări generalizate şi combinăriPermutări cu repetiţie

    În multe probleme de numărare se doreşte folosirea repetată aunor elemente.

    Permutările şi combinările presupun că fiecare element apare osingură dată.

    O r -permutare cu repetiţie a unei mulţimi cu n elemente estean aranjament de r elemente din acea mulţime, ı̂n care fiecareelement poate să apară de mai multe ori.

    Exemplu

    Câte şiruri cu lungimea n se pot forma cu litere mici şi mari dinalfabetul latin?Răspuns: |Alfabetlatin| = 52 ⇒ 52n şiruri (cf. regulii produsului)

    Teoremă

    Numărul de r -permutări cu repetiţie al unei mulţimi cu n elementeeste nr .

    Teoria Grafurilor şi Combinatorică

  • Permutări generalizate şi combinăriPermutări cu repetiţie

    În multe probleme de numărare se doreşte folosirea repetată aunor elemente.

    Permutările şi combinările presupun că fiecare element apare osingură dată.

    O r -permutare cu repetiţie a unei mulţimi cu n elemente estean aranjament de r elemente din acea mulţime, ı̂n care fiecareelement poate să apară de mai multe ori.

    Exemplu

    Câte şiruri cu lungimea n se pot forma cu litere mici şi mari dinalfabetul latin?Răspuns: |Alfabetlatin| = 52 ⇒ 52n şiruri (cf. regulii produsului)

    Teoremă

    Numărul de r -permutări cu repetiţie al unei mulţimi cu n elementeeste nr .

    Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţie

    O r -combinare cu repetiţie a unei mulţimi cu n elemente esteo selecţie de r elemente din mulţimea respectivă, ı̂n carefiecare element poate să apară de oricâte ori.

    Q: Care este numărul r -combinărilor cu repetiţie al unei mulţimicu n elemente?

    Exemplu

    În câte feluri se pot selecta 5 bancnote din o cutie cu bani careconţine bancnote de $1, $2, $5, $10, $20, $50. Presupunem că:ordinea de selecţie a bancnotelor nu contează; există cel puţin 5bancnote de fiecare denominaţie.

    Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţieExemplu – continuat

    Cinci bancnote nu neapărat distincte = o 5-combinare cu repetiţie dinmulţimea {$1, $2, $5, $10, $20, $50} de tipuri de bancnote = a plasare decinci * ı̂n sertarele cutiei de bani ilustrate mai jos:

    Numărul de * ı̂n un sertar reprezintă numărul de bancnote luate dinacel sertar.

    ⇒ Numărul de 5-combinări cu repetiţie al unei mulţimi cu 6 elemente =numărul de moduri de plasare a 5 * ı̂n 6 sertare.

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

    |||∗∗||∗∗∗∗∗ ∗∗∗

    ∗|| ∗ |∗|∗∗|∗ ∗ ∗ ∗∗

    · · ·Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţie

    Observaţie

    Fiecare plasare de 5 * ı̂n 6 sertare posibile este descrisă unicde către un şir de 5 * şi 5 bare roşii.

    În general, numărul de r -combinări cu repetiţie al unei mulţimicu n elemente = numărul de şiruri cu r * şi n − 1 bare roşii.

    Î: În câte feluri putem aranja n − 1 bare şi r *?

    R: Secvenţa are lungimea n + r − 1⇒ secvenţa are n + r − 1 poziţii⇒ trebuie să alegem r poziţii din cele n + r − 1 care să fie

    ocupate cu *; celelalte vor fi ocupate cu bare.

    Există C (n + r − 1, r) de selecţii de acest fel.

    Teoremă

    Numărul de r -combinări cu repetiţie al unei mulţimi cu n elementeeste C (r + n − 1, r).

    Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţie

    Observaţie

    Fiecare plasare de 5 * ı̂n 6 sertare posibile este descrisă unicde către un şir de 5 * şi 5 bare roşii.

    În general, numărul de r -combinări cu repetiţie al unei mulţimicu n elemente = numărul de şiruri cu r * şi n − 1 bare roşii.

    Î: În câte feluri putem aranja n − 1 bare şi r *?R: Secvenţa are lungimea n + r − 1

    ⇒ secvenţa are n + r − 1 poziţii⇒ trebuie să alegem r poziţii din cele n + r − 1 care să fie

    ocupate cu *; celelalte vor fi ocupate cu bare.

    Există C (n + r − 1, r) de selecţii de acest fel.

    Teoremă

    Numărul de r -combinări cu repetiţie al unei mulţimi cu n elementeeste C (r + n − 1, r).

    Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţie

    Observaţie

    Fiecare plasare de 5 * ı̂n 6 sertare posibile este descrisă unicde către un şir de 5 * şi 5 bare roşii.

    În general, numărul de r -combinări cu repetiţie al unei mulţimicu n elemente = numărul de şiruri cu r * şi n − 1 bare roşii.

    Î: În câte feluri putem aranja n − 1 bare şi r *?R: Secvenţa are lungimea n + r − 1

    ⇒ secvenţa are n + r − 1 poziţii⇒ trebuie să alegem r poziţii din cele n + r − 1 care să fie

    ocupate cu *; celelalte vor fi ocupate cu bare.

    Există C (n + r − 1, r) de selecţii de acest fel.

    Teoremă

    Numărul de r -combinări cu repetiţie al unei mulţimi cu n elementeeste C (r + n − 1, r).

    Teoria Grafurilor şi Combinatorică

  • Combinări cu repetiţie

    Observaţie

    Fiecare plasare de 5 * ı̂n 6 sertare posibile este descrisă unicde către un şir de 5 * şi 5 bare roşii.

    În general, numărul de r -combinări cu repetiţie al unei mulţimicu n elemente = numărul de şiruri cu r * şi n − 1 bare roşii.

    Î: În câte feluri putem aranja n − 1 bare şi r *?R: Secvenţa are lungimea n + r − 1

    ⇒ secvenţa are n + r − 1 poziţii⇒ trebuie să alegem r poziţii din cele n + r − 1 care să fie

    ocupate cu *; celelalte vor fi ocupate cu bare.

    Există C (n + r − 1, r) de selecţii de acest fel.

    Teoremă

    Numărul de r -combinări cu repetiţie al unei mulţimi cu n elementeeste C (r + n − 1, r).

    Teoria Grafurilor şi Combinatorică

  • Permutări şi combinăriRezumat

    Tip Repetiţii Formulăadmise?

    r -permutări Nu P(n, r) =n!

    (n − r)!

    r -combinări Nu C (n, r) =n!

    r !(n − r)!r -permutări Da nr

    cu repetiţie

    r -combinări Da C (n + r − 1, r) =(n + r − 1)!r !(n − 1)!

    cu repetiţie

    Teoria Grafurilor şi Combinatorică

  • Permutări cu elemente nediferenţiate

    Problemă

    Câte şiruri distincte se pot obţine reordonând literele şiruluiSUCCES?

    SUCCES conţine 2 S-uri, 2 C-uri, 1U, 1 E.

    alegerea locurilor lui S-uri: C (6, 2) ⇒ 4 locuri rămase.alegerea locurilor pentru C-uri: C (4, 2) ⇒ 2 locuri rămase.alegerea locului pentru U: C (2, 1) ⇒ 1 loc rămas.alegerea locului pentru E: C (1, 1).

    ⇒ cf. regulii produsului, numărul este

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

    Teoria Grafurilor şi Combinatorică

  • Permutări cu elemente nediferenţiate

    Problemă

    Câte şiruri distincte se pot obţine reordonând literele şiruluiSUCCES?

    SUCCES conţine 2 S-uri, 2 C-uri, 1U, 1 E.

    alegerea locurilor lui S-uri: C (6, 2) ⇒ 4 locuri rămase.alegerea locurilor pentru C-uri: C (4, 2) ⇒ 2 locuri rămase.alegerea locului pentru U: C (2, 1) ⇒ 1 loc rămas.alegerea locului pentru E: C (1, 1).

    ⇒ cf. regulii produsului, numărul este

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

    Teoria Grafurilor şi Combinatorică

  • Permutări cu elemente nediferenţiate

    Teoremă

    Numărul de permutări diferite de n obiecte, dintre care n1 suntelemente nediferenţiate de tip 1, n2 sunt elemente nediferenţiatede tip 2, . . . , şi nk sunt elemente nediferenţiate de tip nk , este

    n!

    n1!n2! · · · nk !.

    Teoria Grafurilor şi Combinatorică

  • Numere binomiale şi multinomiale

    Numerele binomiale sunt coeficienţii cn,k din formulabinomului

    (x + y)n =n∑

    k=0

    cn,k · xn−kyk

    Numerele multinomiale sunt coeficienţii cn,k1,...,kr din formula

    (x1 + . . . + xr )n =

    n∑k1+...+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 şi Combinatorică

  • Numere binomiale şi multinomialeFormule de calcul

    (x1 + . . . + xr )n =

    n∑k1+...+kr=n

    n!

    k1! . . . kr !· xk11 x

    k22 . . . x

    krr

    Demonstraţie combinatorială

    (x1 + . . . + xr )n =

    n paranteze︷ ︸︸ ︷(x1 + . . . + xr ) · . . . · (x1 + . . . + xr )

    În câte feluri poate fi produs monomul xk11 · . . . · xkrr ?B Alegem k1 paranteze din care provine x1 ⇒ C (n, k1) posibilităţi.B Alegem k2 paranteze din care provine x2 ⇒ C (n− k1, k2) posibilităţi.

    . . .

    B Alegem kr paranteze din care provine xr ⇒ C (n −∑r−1

    i=1 ki , kr )posibilităţi.

    ⇒ cf. regulii produsului, nr. de apariţii al lui xk11 · . . . · xkrr ı̂n partea

    dreaptă este C (n, k1)C (n − k1, k2) · . . . · C (n −∑r−1

    i=1 ki , kr ) =n!

    k1! . . . kr !Teoria Grafurilor şi Combinatorică

  • Numere binomiale şi multinomialeConcluzii

    Pentru formula n!k1!...kr ! cu k1 + . . . + kr = n se foloseşte

    adesea notaţia( nk1,...,kr

    ).

    Formula binomială este

    (x + y)n =n∑

    k=0

    (n

    k

    )xkyn−k

    Formula multinomială este

    (x1 + . . . + xr )n =

    ∑k1+...+kr=n

    (n

    k1, . . . , kr

    )xk11 · . . . · x

    krr

    Remarcă.(nk

    )=( nk,n−k

    )şi

    (x1 + x2)n =

    n∑k=0

    (n

    k

    )xk1 x

    n−k2 =

    ∑k1+k2=n

    (n

    k1, k2

    )xk11 x

    k22 .

    Teoria Grafurilor şi Combinatorică