De ce contează?
Ai un lacăt cu cifru de două rotițe, fiecare cu cifrele de la 1 la 2. Câte coduri diferite poți forma? Rotești prima rotiță independent de a doua, deci codurile sunt 11, 12, 21 și 22 — toate cele 4. Nimic nu te oprește să pui aceeași cifră de două ori: 11 e un cod perfect valid. Exact asta e produsul cartezian — toate combinațiile posibile când fiecare poziție alege liber.
Intuiția
Vrei toate cuvintele de lungime k formate din valorile 1..n. Gândește-te la cele
k poziții ca la niște rotițe independente: fiecare poate fi orice valoare, indiferent
de ce au celelalte. Pentru n=2, k=2 umpli prima poziție cu 1 sau 2, iar pentru
fiecare alegere umpli a doua poziție tot cu 1 sau 2. Pentru că poziţiile nu se
influenţează, numărul total e n × n × ... × n de k ori, adică „n^k". La n=2,
k=2 asta înseamnă exact 4 cuvinte: 11, 12, 21, 22.