Answer to Question #129543 in Discrete Mathematics for Hazha

Question

how many reflexive relation on A={1,2,3,4,5},could be definde

Answer 1

Let set A = {1 , 2}. In reflexive relation on $A \times A$ are such that $(a,b) \in A \times A \implies (b,a) \in A$ .

Hence, the following are the reflexive relation on $A\times A$ :

$\{(1, 1), (2, 2)\} \\ \{(1, 1), (2, 2), (1, 2)\} \\ \{(1, 1), (2, 2), (1, 2), (2, 1)\} \\ \{(1, 1), (2, 2), (2, 1)\}$ .

A relation has ordered pairs (a,b). Now a can be chosen in n ways and same for b. So set of ordered pairs contains n² pairs. Now for a reflexive relation, (a,a) must be present in these ordered pairs. And there will be total n pairs of (a,a), so number of ordered pairs will be n²-n pairs. So total number of reflexive relations is equal to 2^n(n-1).

Formulas of the number of reflexive relations on an n-element set is $2^{n^2-n}$ .

Hence, the number of reflexive relation on A={1,2,3,4,5} are $2^{5^2-5} = 2^{25-5}=2^{20}$ = 1048576.