Number of Asymmetric Relations on a set of N elements
The number of asymmetric relations on a set of ? elements can be calculated using combinatorial principles. An asymmetric relation is a relation that satisfies the condition that if an element ? is related to ?, then ? is not related to ? (formally, ?(?,?) implies not ?(?,?) for all ?≠? in the set).
Let’s define the set ? as having ? elements. For each pair of distinct elements (?,?) in ? where ?≠?, there are three possibilities for an asymmetric relation:
- ? is related to ? (and ? is not related to ?),
- ? is related to ? (and ? is not related to ?),
- Neither ? is related to ? nor ? is related to ?.
For example, Given a positive integer N, the task is to find the number of Asymmetric Relations in a set of N elements. Since the number of relations can be very large, print it modulo 109+7.
A relation R on a set A is called Asymmetric if and only if x R y exists, then y
Rx for every (x, y) € A.
For Example: If set A = {a, b}, then R = {(a, b)} is asymmetric relation.
Examples:
Input: N = 2
Output: 3
Explanation: Considering the set {1, 2}, the total number of possible asymmetric relations are {{}, {(1, 2)}, {(2, 1)}}.Input: N = 5
Output: 59049
Approach: The given problem can be solved based on the following observations:
- A relation R on a set A is a subset of the Cartesian product of a set, i.e. A * A with N2 elements.
- There are total N pairs of type (x, x) that are present in the Cartesian product, where any of (x, x) should not be included in the subset.
- Now, one is left with (N2 – N) elements of the Cartesian product.
- To satisfy the property of asymmetric relation, one has three possibilities of either to include only of type (x, y) or only of type (y, x) or none from a single group into the subset.
- Hence, the total number of possible asymmetric relations is equal to 3 (N2 – N) / 2.
Therefore, the idea is to print the value of 3(N2 – N)/2 modulo 109 + 7 as the result.
Below is the implementation of the above approach:
// C++ program for the above approach
#include <iostream>
using namespace std;
const int mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
int power(long long x,
unsigned int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
// If x is divisible by mod
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, then
// multiply x with result
if (y & 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
int asymmetricRelation(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
int main()
{
int N = 2;
cout << asymmetricRelation(N);
return 0;
}
// Java program for the above approach
import java.io.*;
class GFG{
final static int mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
public static int power(int x, int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
// If x is divisible by mod
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, then
// multiply x with result
if (y % 2 == 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
public static int asymmetricRelation(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver code
public static void main (String[] args)
{
int N = 2;
System.out.print(asymmetricRelation(N));
}
}
// This code is contributed by user_qa7r
# Python3 program for the above approach
mod = 1000000007
# Function to calculate
# x^y modulo (10^9 + 7)
def power(x, y):
# Stores the result of x^y
res = 1
# Update x if it exceeds mod
x = x % mod
# If x is divisible by mod
if (x == 0):
return 0
while (y > 0):
# If y is odd, then
# multiply x with result
if (y & 1):
res = (res * x) % mod;
# Divide y by 2
y = y >> 1
# Update the value of x
x = (x * x) % mod
# Return the final
# value of x ^ y
return res
# Function to count the number of
# asymmetric relations in a set
# consisting of N elements
def asymmetricRelation(N):
# Return the resultant count
return power(3, (N * N - N) // 2)
# Driver Code
if __name__ == '__main__':
N = 2
print(asymmetricRelation(N))
# This code is contributed by SURENDRA_GANGWAR
// C# program for the above approach
using System;
class GFG{
const int mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
static int power(int x, int y)
{
// Stores the result of x^y
int res = 1;
// Update x if it exceeds mod
x = x % mod;
// If x is divisible by mod
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, then
// multiply x with result
if ((y & 1) != 0)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
static int asymmetricRelation(int N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
public static void Main(string[] args)
{
int N = 2;
Console.WriteLine(asymmetricRelation(N));
}
}
// This code is contributed by ukasp
<script>
// Javascript program for the above approach
var mod = 1000000007;
// Function to calculate
// x^y modulo (10^9 + 7)
function power(x, y)
{
// Stores the result of x^y
var res = 1;
// Update x if it exceeds mod
x = x % mod;
// If x is divisible by mod
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, then
// multiply x with result
if (y & 1)
res = (res * x) % mod;
// Divide y by 2
y = y >> 1;
// Update the value of x
x = (x * x) % mod;
}
// Return the final
// value of x ^ y
return res;
}
// Function to count the number of
// asymmetric relations in a set
// consisting of N elements
function asymmetricRelation( N)
{
// Return the resultant count
return power(3, (N * N - N) / 2);
}
// Driver Code
var N = 2;
document.write( asymmetricRelation(N));
</script>
Output
3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Contact Us