Combinatorică

Combinatorica este un domeniu al matematicii care studiază modalitățile de numărare, aranjare și alegere ale elementelor mulțimilor finite.

Produsul cartezian

Dacă mulțimile A1, A2, …, An au cardinalele k1, k2, …, kn atunci numărul de elemente al produsului cartezian A1×A2×…×An este k1⋅k2⋅…⋅kn.

Submulțimile unei mulțimi

Dacă o mulțime are n elemente, atunci aceasta are 2^n submulțimi.

Permutări

O permutare este o aranjare a elementelor unei mulțimi într-o anumită ordine.

{1, 4, 2, 3} este permutare a mulțimii {1, 2, 3, 4}

Numărul de permutări al unei mulțimi cu n elemente este n! = 1 ⋅ 2⋅ ⋅ … ⋅ n.

Aranjamente

Dacă A este o mulțime cu n elemente, submulțimile ordonate cu k elemente ale lui A se numesc aranjamente a n elemente luate câte k.

Probleme

1. Numărul de grafuri neorientate de 5 noduri.
   
   
2. Numărul de grafuri orientate de 5 noduri.
   
   
3. Numărul de grafuri neorientate de 5 noduri, cu nodul 2 legat de nodul 1.
   
   
4. Numărul de grafuri de 5 noduri cu cel putin o muchie.
   
   
5. Numărul de grafuri neorientate în care nodul 2 are gradul 2, cu 7 noduri.
   
   
6. Numărul de grafuri neorientate cu 2 componente conexe și 5 noduri.
   
   
7. Numărul de grafuri orientate complete cu n noduri.
   
   
8. Numărul de grafuri neorientate în care nodul 2 are gradul 3 și nodul 1 poate fi legat doar de nodurile 2 sau 5.
   
   
9. Numărul de numere de 5 cifre distincte.
   
   
10. Numărul de numere de 3 cifre, ordonate strict crescător, impare.
    
    
11. Numărul de cicluri hamiltoniene în graf complet cu n noduri.
    
    
12. Numărul de anagrame ale unui cuvânt.
    
    

Răspunsuri

1. 2^(5 * 4 / 2) = 2^10
   
   
2. 4^(5 * 4 / 2) = 2^20
   
   
3. 2^(5 * 4 / 2 - 1) = 2^9
   
   
4. 3 * 4^9
   
   
5. (C de 6 luate câte 2) * 2^15
   
   
6. Indiciu: împărțirea problemei în posibilitățile de configurare a grafului
   230
   
   
7. 3^(n(n - 1) / 2) (sunt 3 stări ale muchiilor)
   
   
8. 2^((n-3) * (n - 2) / 2) * 2 * ((C de (n - 2) luate câte 2) - (C de (n - 2) luate câte 3))
   
   
9. 8 * 8 * 7 * 6 * 5
   
   
10. (C de 4 luate câte 4) + (C de 6 luate câte 4) + (C de 8 luate câte 4)
    
    
11. (n - 1)! / 2 (împărțirea la 2 ne scapă de oglindite)