Permutări cu restricții: pe scurt

O restricție nu schimbă metoda de numărare, ci doar reduce libertatea de alegere într-unul dintre pași. Trei tehnici acoperă majoritatea situațiilor. Metoda lipirii: dacă $k$ elemente trebuie să stea împreună (bloc compact, în orice ordine), le tratezi ca pe un singur obiect — $k!\cdot (n-k+1)!$ — factorul $k!$ numără ordinile din interiorul blocului, iar $(n-k+1)!$ permută blocul împreună cu restul.

Scăderea cazurilor nefavorabile: pentru «nu stau alături» scazi din total exact cazurile în care stau alături (calculate prin lipire). Semnalul din enunț: cuvintele «nu», «niciun» cer aproape mereu complementul.

Metoda locurilor libere: pentru «niciun element din grupul restricționat nu e vecin cu altul din același grup», așezi întâi elementele libere ($p!$ moduri), apoi strecori elementele restricționate în cele $p+1$ spații create (înainte, între, după), câte cel mult unul în fiecare spațiu, ținând cont că elementele sunt distincte.

La alternanță (F,B,F,B,…), numeri întâi tiparele posibile, apoi permuți în interiorul fiecărui grup. La ordine relativă impusă între câteva elemente, împarți totalul la numărul de ordini posibile ale acelor elemente.

Exerciții din această mini-lecție

1. $5$ persoane se așază într-un rând. În câte moduri, dacă Ana și Bogdan trebuie să stea unul lângă altul?

   • a) $48$
   • b) $24$
   • c) $120$
   • d) $12$
   Vezi răspunsul

   Răspuns corect: a) $48$

   Lipim Ana și Bogdan într-un bloc: rămân $4$ obiecte de permutat, $4!=24$ moduri; în interiorul blocului sunt $2!=2$ ordini. Total: $2!\cdot 4!=48$.

2. Aceleași $5$ persoane. În câte moduri se așază dacă Ana și Bogdan nu stau unul lângă altul?

   • a) $48$
   • b) $72$
   • c) $96$
   • d) $60$
   Vezi răspunsul

   Răspuns corect: b) $72$

   Total: $5!=120$. Cazurile «alături» au fost numărate anterior: $48$. Prin complement: $120-48=72$.

3. $3$ fete și $2$ băieți se așază într-un rând, alternând (fată, băiat, fată, băiat, fată). Câte așezări există?

   • a) $6$
   • b) $120$
   • c) $12$
   • d) $720$
   Vezi răspunsul

   Răspuns corect: c) $12$

   Cu grupuri de mărimi $3$ și $2$, tiparul este unic: F-B-F-B-F. Fetele se permută în $3!=6$ moduri, băieții în $2!=2$ moduri: $3!\cdot 2!=12$.