Combinatorica Multimi finite ordonate Permutari

Incepem prin a invata o notiune noua si anume Combinatorica, iar in cadrul acestui capitol o sa vorbim despre Multimi finite ordonate Permutari.

Despre multimi finite am mai discutat si in clasa a IX-a, notiunea noua pe care o introducem o sa fie Permutari.

Multimi finite ordonate

Definitie:

Multimea A se numeste finita daca exista o functie bijectiva $f:\left\{1,2,...,n\right\}\rightarrow A$ . Numarul n al elemenelor lui A se numeste cardinalul lui A si se noteaza $card A$ sau |A|. Prin conventie: $card \oslash=0$

Proprietati:

1) $card\left(A\cup B\right)=card\left(A\right)+card\left(B\right)-card\left(A\cap B\right)$

2) $card\left(A-B\right)=card\left(A\right)-card\left(A\cap B\right)$

3) $card\left(A\times B\right)=card\left(A\right)\cdot card\left(B\right)$

Teorema. Fie A si B doua multimi finite, $card\left(A\right)=n$ si $card\left(B\right)=m$ . Atunci numarul tuturor functiilor $f:A\rightarrow B$ este $m^{n}$ .

Propozitie. Numarul tuturor submultimilor unei multimi cu n elemente este $2^{n}$

Exemplu:

1) Dintr-un grup de 50 de turisti, 35 cunosc engleza, iar 25 franceza Cati turisti cunosc ambele limbi?

Solutie:

Fie A multimea turistilor , B multimea turistilor care cunosc engleza, C multimea turistilor care cunosc franceza.

Avem $card\left(A\right)= 50, card\left(B\right)=35, card\left(C\right)=25$

Stim ca $card\left(A\right)=card\left(B\cup C\right)$

astfel,

$card\left(B\cup C\right)=$

$card\left(B\right)+card\left(C\right)-card\left(B\cap C\right)$

$\Rightarrow$

$50=35+25-card\left(B\cap C\right)\Rightarrow 50=60-card\left(B\cap C\right)\Rightarrow$

$card\left(B\cap C\right)=60-50\Rightarrow$

$card\left(B\cap C\right)=10$ ,

deci numarul turistilor care cunosc ambele limbi sunt 10.

2) Fie multimea $A=\left\{1,2,...,8\right\}$

a) Cate submultimi ale lui A contin numai numere pare

b) Cate submultimi ale lui A care contin elementul 1 exista.

Solutie:

a) Ca sa aflam numarul submultimilor lui A care contin numai numere pare scriem multimea elementelor pare astfel

$\left\{2,4,6,8\right\}$ si numarul submultimilor lui A sunt $2^{4}-1=8-1=7$ (multimea vida nu convine)

b) $2^{7}=128$ submultimi.

Permutari

Definitie: Multimile ordonate cu n elemente ce se obtin prin ordonarea unei multimi finite cu n elemente se numesc permutari ale unei multimi.

Teorema: Numarul $P_{n}$ al tuturor permutarilor unei multimi cu n elemente este $P_{n}=n!$ unde $n!=1\cdot 2\cdot 3\cdot...\cdot n, n\in N^{*}$ . Prin convenctie $0!=1=P_{0}$

Exemple

1) In cate moduri pot fi asezate 9 vagoane ale unui tren la o locomotiva?

Solutie:

Trebuie sa determinam numarul de permutari ale unei multimi cu 9 elemente (vagoane), adica

$P_{9}=9!=1\cdot2\cdot 2\cdot 3\cdot 3\cdot 4\cdot...\cdot 9$

2) Rezolvati ecuatiile:

a) $latex \frac{P_{n}}{P_{n-2}}=72\Rightarrow \frac{n!}{\left(n-2\right)!}=72\Rightarrow \frac{\left(n-2\right)\cdot\left(n-1\right)\cdot n}{\left(n-2\right)}=72\Rightarrow \frac{\left(n-1\right)\cdot n}{1}=72\Rightarrow \left(n-1\right)\cdot n=72\Rightarrow n^{2}-n=72\Rightarrow n^{2}-n-72=0$

$\Delta=b^{2}-4\cdot a\cdot c=\left(-1\right)^{2}-4\cdot 1\cdot\left(-72\right)=1+288=289$ ;

$n_{1}=\frac{-b+\sqrt{\Delta}}{2\cdot a}=\frac{1+\sqrt{289}}{2\cdot 1}=\frac{1+17}{2}=\frac{18}{2}=9$ ;

$n_{2}=\frac{-b-\sqrt{\Delta}}{2\cdot a}=$

$\frac{1-\sqrt{289}}{2\cdot 1}=$

$\frac{1-17}{2}=\frac{-16}{2}=-8$ (nu convine ).

Cum $n\in N$ , observam ca doar pentru n=9 este o solutie a ecuatiei.

Ca sa rezolvam ecuatia de mai sus folosim pentru inceput teorema care am enuntat-o mai sus, apoi am simplificat pe unde am putut, observam ca pana la n factorial la numarator mai avem de la n-2 factorial mai avem n-1 si evident 2, de unde am simplificat n-2 cu n-2 si ne-a ramas $\left(n-1\right)\cdot n$ , evident in membrul stang. Restul este cu calcul normal a unei ecuatii de gradul al doilea.

b) $\frac{\left(n+1\right)!}{\left(n-1\right)!}<30\Rightarrow \frac{\left(n-1\right)\cdot n\cdot\left(n+1\right)}{n-1}<30\Rightarrow n\cdot\left(n+1\right)<30\Rightarrow n^{2}+n<30\Rightarrow n^{2}+n-30<0$

$\Delta=b^{2}-4\cdot a\cdot c=1^{2}-4\cdot 1\cdot\left(- 30\right)=1+120=121$ ;

Observam ca Delta este mai mare ca 0 si a>0, deci inecuatia noastra are multimea solutiilor inecutiilor este $S=\left(n_{1}, n_{2}\right)$

$n_{1}=\frac{-1+\sqrt{121}}{2\cdot 1}=\frac{-1+11}{2}=\frac{10}{2}=5$ ;

$\\n_{2}=\frac{-1-\sqrt{121}}{2\cdot 1}=$

$\frac{-1-11}{2}=$

$\frac{-12}{2}=-6\Rightarrow n_{2}$

Deci $n\in \left(-6, 5\right)$ , pune acum conditiile:

$n+1\geq 0$ si $n-1\geq 0$

Astfel avem

$n+1\geq 0\Rightarrow n\geq -1; n-1\geq 0\Rightarrow n\geq 1$ si $n\in N$

Deci $n\in \left[-1,\infty\right)$ si $n\in\left[1,\infty\right)\Rightarrow n\in\left[1, \infty\right)$ (calculam intersectia ccelor doua sulutii ale inecuatiei).

Si astfel gasim ca $n\in\left\{1, 2, 3, 4\right\}$

Ca sa rezovam inecuatia de mai sus am folosit ca si la exercitiul a) teorema care am enuntat-o mai sus, am simplificat ce am putut. Observati mai sus cum am scris si numitorul si numaratorul si ce am simplificat. Am obtinut o inecuatie de gradul al doilea pe care am rezolvat-o folosind regulile de rezolvare a inecuatiilor de gradul a II-lea. Important sa tinem cont de conditiile de mai sus ca sa gasim solutiile inecuatiei.

Combinatorica Multimi finite ordonate Permutari

Multimi finite ordonate

Lasă un răspuns Anulează răspunsul

Recente

Categorii