Problema mesei rotunde si problema colierului

Problema mesei rotunde

Problema mesei rotunde consta in determinarea numarului de moduri in care putem aseza n persoane la o masa rotunda cu n  locuri.

Ne vom ocupa mai indeaproape de cazul n=4. Notam cele 4 locuri la masa cu 1,2,3,4 si cele 4 persoane cu A,B,C,D. Daca aranjarea persoanelor ar fi liniara (aranjarea s-ar face pe un rand), ar exista P4=4!=24 posibilitati de aranjare a celor 4 persoane, corespunzatoare permutarilor liniare ale mutimii {A,B,C,D}, anume:

(A,B,C,D),   (A,B,D,C),   (A,C,B,D),   (A,C,D,B),   (A,D,B,C),   (A,D,C,B)
(B,A,C,D),   (B,A,D,C),   (B,C,A,D),   (B,C,D,A),   (B,D,A,C),   (B,D,C,A)
(C,A,B,D),   (C,A,D,B),   (C,B,A,D),   (C,B,D,A),   (C,D,A,B),   (C,D,B,A)
(D,A,B,C),   (D,A,C,B),   (D,B,A,C),   (D,B,C,A),   (D,C,A,B),    (D,C,B,A).

Considerand multimea de permutari liniare Γ={(A,B,C,D), (B,C,D,A), (C,D,A,B), (D,A,B,C)} si aranjand elementele acestei multimi la masa rotunda se obtin situatiile din figura urmatoare:

circular-permutation

Fig.1

Constatam ca cele 4 situatii sunt echivalente in sensul ca fiecare din cele 4 persoane isi pastreaza atat vecinul din dreapta cat si vecinul din stanga (are loc o rotire, in sens trigonometric, a personelor in jurul mesei).

Deci cele 4 permutari liniare din multimea Γ, determina o singura permutare circulara pe care o vom nota cu  <A,B,C,D> sau <B,C,D,A> sau <C,D,A,B> sau <D,A,B,C>, iar in total vor fi  \frac{4!}{4}  =6 permutari circulare pe care le vedem in figura de mai jos:

circular-permutation1

Fig.2

Revenind la problema mesei rotunde in cazul general, numarul de permutari circulare de n obiecte este egal cu  Equation18 .

Problema colierului

Problema colierului consta in determinarea numarului de moduri in care putem confectiona un colier din n  margele de culori diferite (colierul poate fi purtat pe ambele fete).

Ne vom ocupa mai indeaproape de cazul n=6. Notam cele 6 pozitii ale margelelor pe colier cu  1,2,3,4,5,6  si cu A,B,C,D,E,F  margelele (culorile margelelor).

Plecand de la permutarea liniara (A,B,C,D,E,F) si asezand margelele in sens trigonometric direct obtinem urmatoarele 6 configuratii care genereaza acelasi model de colier (fiecare margea isi pastreaza atat vecinul din dreapta cat si vecinul din stanga):

Colier1

Fig.3

Plecand tot de la permutarea liniara (A,B,C,D,E,F) si asezand margelele in sens trigonometric invers obtinem urmatoarele 6 configuratii:

Colier2

Fig.4

Rotind cofiguratiile din Fig.4 in jurul dreptei determinata de pozitiile 1 si 4  (ceea ce inseamna schimbarea fetei colierului ) se obtin configuratiile din Fig.3.

In concluzie, plecand de la o permutarea liniara (A,B,C,D,E,F) obtinem 2·6=12  permutari liniare ale multimii {A,B,C,D,E,F} care genereaza acelasi model de colier, anume (A,B,C,D,E,F)  (F,A,B,C,D,E), (E,F,A,B,C,D,),  (D,E,F,A,B,C),  (C,D,E,F,A,B),  (B,C,D,E,F,A), (A,F,E,D,C,B), (F,E,D,C,B,A), (E,D,C,B,A,F), (D,C,B,A,F,E), (C,B,A,F,E,D) si (B,A,F,E,D,C). Astfel numarul de modalitati de confectionare a colierului va fi  \frac{6!}{2\cdot 6}=\frac{5!}{2}=60.

In cazul general, numarul de modalitati de confectionare a colierului va fi  Equation19.

 

Academia de matematica aici:http://robeauty.ro

orange.ro

Reclame

Partitionarea ordonata a unei multimi

Consideram n obiecte o1,o2,….,on . Impartim multimea A={ o1,o2,….,on } a celor n obiecte int-o secventa ordonata de m submultimi (mn) A1, A2,…., Am disjuncte doua cate doua, astfel incat:

  • submultimea A1 are k1 obiecte;
  • submultimea A2 are k2 obiecte;
  • ………………………………………………………….
  • submultimea Am are km elemente.

Evident n=k1+k2+….+km. Numarul de moduri in care se poate partitiona, astfel multimea A este:
Equation8

Intr-adevar:

  • elementele submultimii A1  pot fi alese in Equation9 moduri;
  • elementele submultimii A2  pot fi alese in Equation10 moduri;
  • elementele submultimii A3  pot fi alese in Equation11  moduri;
  • ……………………………………………………………………………………………………………….
Deci numarul de posibilitati de partitionare a multimii A  intr-o secventa ordonata de  m submultimi avand cardinalele k1, k2,….. ,k (k1+k2+….+km=n)  va fi:
Equation12.jpg
Exemplu:
Daca A={1,2,3,4,5}, k1=2, k2=2 si k3=2, atunci multimea A se va putea partitiona in secvente ordonate de 3 submultimi avand cardinalele egale cu 2, 2, respectiv 1,  in  Equation16 moduri, anume:
 Equation17.jpg
Numarul Equation8, se mai numeste coeficient multinomial . Se folosesc si urmatoarele notatii:
Equation14.
Remarcam in incheiere formula de dezvolatare a unui multinom:
Equation15.jpg
Academia de matematica aici:http://robeauty.ro

 

digitalcomputer.ro

Aranjamente

Consideram doua multimi nevide X={x1,x2,…,xk }, Y={y1,y2,…,yn } si o functie f:X→Y.

1.

Daca x∈X, y∈Y si y=f (x). vom spune ca am aranjat elementul x in casuta y.

In acest fel oricarei functii f:X→Y  ii corespunde o aranjare a elementelor x1,x2,…,xk multimii X in casutele y1,y2,…,yn multimii Y si reciproc oricarei aranjari a elementelor  x1,x2,…,xk in casutele y1,y2,…,yn ii corespunde o functie f:X→Y. Astfel multimea functiilor f:X→Y este echipotenta cu multimea aranjarilor a k obiecte in n casute (intre cele doua multimi exista o bijectie).

Exemplu:Equation3

Equation4

Functia definita mai sus se va numi karanjament cu repetitie in n casute(casuta se repeta) . Observam ca:

  • pentru aranjarea elementului x1 se pot folosi n casute,
  • pentru aranjarea elementului x2 se pot folosi n casute,
  • ……………………………………………………..
  • pentru aranjarea elementului xk se pot folosi n casute,

deci numarul de k – aranjamente cu repetitie in n casute este

Equation5

Fie n≥k. Functia f :{x1,x2,…,xk }→{y1,y2,…,yn } este injectiva daca si numai daca orice casuta este folosita cel mult o data. In acest caz functia f se numeste k – aranjament (al multimii Y) fara repetitie.

Astfel multimea functiilor injective f:X→Y este echipotenta cu multimea aranjarilor a k obiecte in n casute cu conditia ca orice casuta sa fie folosita cel mult o data (intre cele doua multimi exista o bijectie).

Daca orice casuta este folosita cel mult o data, obsevam ca:

  • pentru aranjarea elementului x1 se pot folosi n casute,
  • pentru aranjarea elementului x2 se pot folosi n-1 casute,
  • ………………………………………………………………………
  • pentru aranjarea elementului xk-1 se pot folosi n-k+2 casute,
  • pentru aranjarea elementului xk se pot folosi n-k+1 casute,

deci numarul de k – aranjamente fara repetitie in n casute este

Equation7

2.

Functiei f :{x1,x2,…,xk}→{y1,y2,…,yn} ii putem atasa secventa f (x1)f (x2)….f (xk) pe care o numim cuvant de lungime k  format din literele alfabetului  Y={y1,y2,…,yn}. Reciproc oricarui cuvant de lungime k format din literele alfabetului Y  ii corespunde o functie  f:{x1,x2,…,xk}→{y1,y2,…,yn}. Astfel multimea functiilor f:X→Y este echipotenta cu multimea cuvintelor formate cu literele alfabetului Y (intre cele doua multimi exista o bijectie).

Exemplu:

Equation6

In cazul unui alfabet de de n litere, sa obsevam ca:

  • litera de pe pozitia 1, a unui cuvant, poate fi aleasa in n moduri,
  • litera de pe pozitia 2, a unui cuvant, poate fia aleasa in n moduri,
  • ……………………………………………………………………………..
  • litera de pe pozitia k, a unui cuvant, poate fi aleasa in n moduri,

deci numarul cuvintelor de lungime k, care se pot forma din literele unui alfabet cu n litere este

Equation5

Fie n≥k. Functia f :{x1,x2,…,xk }→{y1,y2,…,yn } este injectiva daca si numai daca  cuvantul  corespunzator f (x1) f (x2)…..f (xk) este format din litere distincte. Reciproc oricarui cuvand de lungime k format din litere distincte ale alfabetului Y={y1,y2,…,yn } ii corespunde o functie injectiva

f :{x1,x2,…,xk }→{y1,y2,…,yn }. Astfel multimea functiilor injective  f:X→Y este echipotenta cu multimea cuvintelor formate cu litere distincte alfabetului Y (intre cele doua multimi exista o bijectie).

In cazul unui cuvant de lungime k,  format cu litere distincte ale unui afabet de n litere , sa obsevam ca:

  • litera de pe pozitia 1 poate fi aleasa in n moduri,
  • litera de pe pozitia 2 poate fi aleasa in n-1 moduri,
  • ……………………………………………………………………………..
  • litera de pe pozitia k-1  poate fi aleasa in n-k+2 moduri,
  • litera de pe pozitia poate fi aleasa in n-k+1 moduri,

deci numarul cuvintelor de lungime avand literele diferite, care se pot forma din literele unui alfabet cu n  litere esteEquation7

Academia de matematica aici:http://robeauty.ro
eJobs