Number of Reflexive Relations on a Set
Given a number n, find out the number of Reflexive Relation on a set of first n natural numbers {1, 2, ..n}.
Examples :
Input: n = 2
Output: 4
The given set A = {1, 2}. The following are 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)}Input: n = 3
Output: 64
Explanation :
Reflexive Relation: A Relation R on A a set A is said to be Reflexive if xRx for every element of x ? A.
The number of reflexive relations on an n-element set is 2n(n-1)
How does this formula work?
A relation R is reflexive if the matrix diagonal elements are 1.
If we take a closer look the matrix, we can notice that the size of matrix is n2. The n diagonal entries are fixed. For remaining n2 – n entries, we have choice to either fill 0 or 1. So there are total 2n(n-1) ways of filling the matrix.
Below is the code implementation of the above approach:
CPP
// C++ Program to count reflexive relations // on a set of first n natural numbers. #include <iostream> using namespace std; int countReflexive( int n) { // Return 2^(n*n - n) return (1 << (n*n - n)); } int main() { int n = 3; cout << countReflexive(n); return 0; } |
Java
// Java Program to count reflexive // relations on a set of first n // natural numbers. import java.io.*; import java.util.*; class GFG { static int countReflexive( int n) { // Return 2^(n*n - n) return ( 1 << (n*n - n)); } // Driver function public static void main (String[] args) { int n = 3 ; System.out.println(countReflexive(n)); } } // This code is contributed by Gitanjali. |
Python3
# Python3 Program to count # reflexive relations # on a set of first n # natural numbers. def countReflexive(n): # Return 2^(n*n - n) return ( 1 << (n * n - n)); # driver function n = 3 ans = countReflexive(n); print (ans) # This code is contributed by saloni1297 |
C#
// C# Program to count reflexive // relations on a set of first n // natural numbers. using System; class GFG { static int countReflexive( int n) { // Return 2^(n*n - n) return (1 << (n*n - n)); } // Driver function public static void Main () { int n = 3; Console.WriteLine(countReflexive(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Program to count // reflexive relations on a // set of first n natural numbers. function countReflexive( $n ) { // Return 2^(n * n - n) return (1 << ( $n * $n - $n )); } //Driver code $n = 3; echo countReflexive( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript Program to count reflexive // relations on a set of first n // natural numbers. function countReflexive(n) { // Return 2^(n*n - n) return (1 << (n*n - n)); } let n = 3; document.write(countReflexive(n)); // This code is contributed by divyesh072019. </script> |
64
Time Complexity: O(1)
Auxiliary Space: O(1)