Question

Câte relații reflexive există pe o mulțime de 'n' elemente?
Argumentați.

Answer 1

Fie M o multime cu n elemente (nu prea ne intereseaza cum arata, putem zice si ca M={1,2,...,n} pentru ca putem duce o bijectie de la aceasta la o multime arbitrara cu n elemente). O relatie binara pe M este o submultime $\rho$ a produsului cartezian $M \times M$. Relatia aceasta va fi reflexiva daca submultimea $\rho$ contine ceea ce se numeste diagonala lui M, adica multimea perechilor $\{(1,1),(2,2),\ldots,(n,n)\}$. Putem face o reprezentare simpla a relatiei printr-un tabel precum tabla lui Cayley de la grupuri, in care putem preciza daca apare sau nu perechea (i,j) in $\rho$. Cum relatia noastra este relexiva, toata diagonala tabelului va fi "marcata", penru ca toate vor fi continute. Din cele $n^2$ spatii din tabel am ocupat din start n, deci ne mai raman $n^-n=n(n-1)$ locuri libere. Numarul relatiilor binare il obtinem gandindu-ne in care moduri putem ocupa celelalte pozitii cu "e continuta perechea" sau "nu e continuta perechea" (pentru ca daca daca avem diagonala, relatia e deja reflexiva, nu ne mai intereseaza asa tare cum sunt restul). Sa zicem ca dam un 0 pentru "nu e continuta" si un 1 pentru "e continuta". Deci numarul relatiilor reflexive va fi numarul functiilor definite pe multimea "spatiilor libere", care sunt in numar de $n(n-1)$ cu valori in multimea {0,1}, deci $2^{n(n-1)}$ relatii reflexive. Un alt mod de a formula problema e: Determinati numarul de matrici patratice de ordin n cu elemente din $\mathbb{Z}_2$ care au doar $\hat1$ pe diagonala principala.