Teoria Grafurilor ˘si Combinatoric a · 2019. 1. 18. · 5 Teoria lui Polya de num arare 6...
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ă