Written in C++, find the number of reflexive relations on a set

In this article, we will explain ways to find reflexive relationships on a set. In this problem, we are given a number n, and a set of n natural numbers, and we must determine the number of reflexive relations.

Reflexive relation - If for every 'a' in set A, (a, a) belongs to relation R, then relation R is said to be a reflexive relation on set A. For example -

Input : x = 1
Output : 1
Explanation : set = { 1 }, reflexive relations on A * A :
{ { 1 } }

Input : x = 2
Output : 4
Explanation : set = { 1,2 }, reflexive relations on A * 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 ) }

Thus, if for every element a ∈ A, there is (a, a) ∈ R, then the relation R is reflexive.

Solution method

The number of reflexive relations on the element set can be calculated through the formula 2n2−n. This general formula is obtained by counting the number of reflexive relations of integers.

Example

#include <iostream>
using namespace std;
int countReflexive(int n){
    int ans = 1 << (n*n - n);
    return ans;
}
int main(){
    int n ;
     cin >> n ; // taking input n from the user using std cin.
    int result = countReflexive(n); // calling function to calculate number of reflexive relations
    cout << "Number of reflexive relations on set: " << result ; // printing the answer
    return 0;
}

Output

Number of reflexive relations on set: 1

Explanation of the above program

This program is easy to understand because we just Get the input from the user and put it into the formula 2n2−n. We use the left shift operator "

Conclusion

In this paper, we addressed a problem about the number of reflexive relations on sets. We discussed simple ways to solve a given problem, and mathematicians derived a formula for counting the number of reflexive relations.

We also learned to write a program for this problem in C, with a time complexity of O(1). We can write the same program in other languages ​​like C, Java, Python and others.

The above is the detailed content of Written in C++, find the number of reflexive relations on a set. For more information, please follow other related articles on the PHP Chinese website!