Diagrame arborescente: pe scurt

O diagramă arborescentă (arbore) organizează alegerile succesive dintr-o problemă de numărare: rădăcina e situația de dinaintea oricărei alegeri, o ramură e o alegere concretă, un nod e un punct la care ai ajuns după una sau mai multe alegeri, iar o frunză e o posibilitate completă. Regula de citire: numărul posibilităților este numărul frunzelor, adică al drumurilor distincte de la rădăcină la capăt.

Când arborele este uniform — din fiecare nod al unui nivel pleacă același număr de ramuri — numărul frunzelor este produsul numerelor de ramuri: dacă la etapa întâi ai $2$ variante și la a doua $3$, ai $2\cdot 3=6$ frunze. Când arborele e neuniform, ramurile mari (care oferă un număr diferit de variante) se tratează separat, iar rezultatele se adună.

Arborele mai arată clar și alte două lucruri: diferența dintre «cu repetiție» (oferta rămâne aceeași la fiecare nivel) și «fără repetiție» (oferta scade cu unu), respectiv dacă ordinea contează — testul e simplu: dacă schimbi între ele două elemente alese și obții altceva, ordinea contează; dacă nu, fiecare grup a fost numărat de mai multe ori.

Exerciții din această mini-lecție

1. O cofetărie are $3$ mărimi de pahar și $4$ arome de înghețată. Câte comenzi (mărime, aromă) există, desenate ca un arbore uniform?

   • a) $12$
   • b) $7$
   • c) $3$
   • d) $4$
   Vezi răspunsul

   Răspuns corect: a) $12$

   Arborele are $3$ ramuri la primul nivel (mărimile) și, din fiecare, $4$ ramuri (aromele), deci $3\cdot 4=12$ frunze — atâtea comenzi diferite.

2. O firmă de curierat merge din $A$ în $D$ prin $B$ sau prin $C$. De la $A$ la $B$ sunt $3$ drumuri, de la $B$ la $D$ sunt $2$; de la $A$ la $C$ sunt $2$ drumuri, de la $C$ la $D$ sunt $4$. Câte trasee complete există?

   • a) $11$
   • b) $14$
   • c) $44$
   • d) $9$
   Vezi răspunsul

   Răspuns corect: b) $14$

   Arborele e neuniform: prin $B$ sunt $3\cdot 2=6$ trasee, prin $C$ sunt $2\cdot 4=8$ trasee. Un traseu trece ori prin $B$, ori prin $C$, deci se adună: $6+8=14$.

3. Câte coduri de două cifre distincte se pot forma cu cifrele $1$, $2$, $4$?

   • a) $3$
   • b) $9$
   • c) $6$
   • d) $4$
   Vezi răspunsul

   Răspuns corect: c) $6$

   Primul nivel are $3$ ramuri, al doilea are $2$ ramuri (cifra deja folosită dispare din listă): $3\cdot 2=6$ coduri — $12,14,21,24,41,42$.