Combinatorică - Elemente de bază

Elemente de Matematică și Informatică. Teorie, Probleme. Discuții.
User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Combinatorică - Elemente de bază

Postby Admin » 14 Jan 2013, 15:37

LINK spre topicul Combinatorică - Probleme de bază

Image







În topicul acesta vom încerca folosirea mai des a notaţiei uzuale folosită de elevi (începând cu clasa a 10-a) pentru combinări.

Adică vom folosi în loc de ... sau în loc de

Reamintire a definiţiilor la cele 3 noţiuni de bază, folosindu-ne de notaţia :
(Prin definiţie )

1) Permutări : şi reprezintă numărul total în care putem permuta obiecte (elemente).

De exemplu, dacă am avea obiecte notate cu (pentru simplitate) am avea permutările :








adică permutări şi observăm că :

2) Combinări. Ca valoare : iar definiţia combinărilor este aşa : presupunând că avem o mulţime cu elemente atunci (unde ) înseamnă numărul tuturor submulţimilor lui cu elemente.

De exemplu, pentru , dacă avem mulţimea atunci





sunt cele submulţimi care au câte elemente .. şi se verifică uşor că :

3) Aranjamente. Pentru simplitate, ca valoare .
Provenienţă : Dacă avem o mulţime cu elemente iar atunci reprezintă prin definiţie numărul tuturor submulţimilor ordonate cu câte elemente ale lui .
(Practic se iau ca şi la combinări toate submulţimile cu câte elemente, iar la fiecare din aceste submulţimi se iau toate permutările). Exemplificarea este relevantă: presupunem atunci generăm toate aranjamentele de luate câte astfel :

şi
şi
şi

deci toate cele aranjamente de luate câte .

iar



User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Combinatorică - Elemente de bază

Postby Admin » 14 Jan 2013, 15:49

Combinări cu repetiţie

În celebra carte a domnului Ioan Tomescu avem o introducere a combinărilor cu repetiţie legată de funcţiile monotone.

Image


Image


Legătura principală este :

, unde

În postarea de mai jos introduc altfel combinările cu repetiţie.
(Sunt mai multe echivalenţe în modalităţile de introducere ale lor. Sunt feluri diferite de definire, dar înseamnă acelaşi lucru)

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Combinatorică - Elemente de bază

Postby Admin » 14 Jan 2013, 15:51

O introducere a combinărilor cu repetiţie prin exemplu care să sugereze valoarea efectivă a combinărilor cu repetiţie de n luate câte k. Demonstraţia este destul de evidentă odată ce se înţelege definiţia combinărilor cu repetiţie ca fiind numărul submulţimilor lui {1, 2, ..., n} de cardinal k, dar e vorba de submulţimi în care un element poate apare de mai multe ori.

Sau, acelaşi lucru se poate face cu extragerea din urnă în care după fiecare extragere se introduce obiectul la loc în urnă (permiţând deci extrageri multiple într-o "combinare cu repetiţie" a aceluiaşi element - lucru nepermis la combinările obişnuite, unde nu se reintroduce la loc în urnă un element după extragere ... Doar după extragerea tuturor celor k elemente care formează o combinare obişnuită se reintroduc toate în urnă pentru obţinerea unei eventuale combinări ...)

Image

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Combinatorică - Elemente de bază

Postby Admin » 19 Jan 2013, 20:13

Recurenţa combinărilor

$\displaystyle C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$


În cealaltă metodă de scriere a combinărilor (mult mai uzitată, exceptând manualele de liceu) :

$\dbinom{n}{k} = \dbinom{n-1}{k} + \dbinom{n-1}{k-1}$

User avatar
Admin
Site Admin
Posts: 768
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Combinatorică - Elemente de bază

Postby Admin » 30 Jan 2013, 18:23

Permutări circulare

Image


Presupunem că avem obiectele : roşu, albastru, verde, galben, maro, roz .

Ştim că avem 6 ! = 1*2*3*4*5*6 = 720 de permutări. Una din ele este : roşu, albastru, verde, galben, maro, roz .

Mutând circular fiecare obiect pe o poziţie succesivă iar ultimul obiect pe prima poziţie obţinem o nouă permutare :
roz, roşu, albastru, verde, galben, maro .
Dacă procedăm aşa în continuare, până obţinem din nou permutarea iniţială, vom avea un total de 6 permutări.

Definiţie:
Dacă o permutare se poate obţine dintr-o altă permutare prin procedeul descris mai sus atunci spunem că avem o aceeaşi permutare circulară. Deci cele 6 permutări ("obişnuite") de mai sus înseamnă o aceeaşi permutare circulară.

Deci :

roşu, albastru, verde, galben, maro, roz
roz, roşu, albastru, verde, galben, maro
maro, roz, roşu, albastru, verde, galben
galben, maro, roz, roşu, albastru, verde
verde, galben, maro, roz, roşu, albastru
albastru, verde, galben, maro, roz, roşu


înseamnă scrierea aceleiaşi permutări circulare (o "afişare" a ei sub mai multe forme).
Împărţind la 6 numărul total de permutări obţinem numărul permutărilor circulare (deci 120 în acest caz).

Observaţia 1 :
La cazul general avem permutări circulare.

Observaţia 2 : În cazul a 3 obiecte numerotate 1, 2, 3 atunci permutările :

2 1 3
3 2 1
1 3 2


reprezintă aceeaşi permutare circulară (şi acestea sunt toate afişările ordonate ale acestei permutări circulare).





Permutările circulare sunt de mare folos în demonstrarea unor probleme (de multe ori dificile), cum ar fi demonstraţia dată de Katona în 1972 Teoremei Erdös–Ko–Rado (demonstraţia iniţială a fost dată în 1961 prin inducţie).

Vom da detaliat (cu completări explicative) demonstraţia acestei teoreme foarte frumoase.


Return to “Teorie și Probleme”

Who is online

Users browsing this forum: No registered users and 5 guests

mateinfo
UP
cron