Number of Antisymmetric Relations on a set of N elements
Given a positive integer N, the task is to find the number of Antisymmetric Relations on the given set of N elements. Since the number of relations can be very large, so print it modulo 109+7.
A relation R on a set A is called Antisymmetric if and only if (a, b) € R and (b, a) € R, then a = b is called antisymmetric, i.e., the relation R = {(a, b)→ R | a ≤ b} is anti-symmetric, since a ≤ b and b ≤ a implies a = b.
Examples:
Input: N = 2
Output: 12
Explanation: Considering the set {a, b}, all possible antisymmetric relations are:
{}, {(a, b)}, {(b, a)}, {(a, a)}, {(a, a), (a, b)}, {(a, a), (b, a)}, {(b, b)}, {(b, b), (a, b)}, {(b, b), (b, a)}, {(a, a), (b, b)}, {(a, a), (b, b), (a, b)}, {(a, a), (b, b), (b, a)}.Input: N = 5
Output: 1889568
Approach: The given problem can be solved based on the following observations:
- Considering an antisymmetric relation R on set S, say a, b ∈ A with a ≠ b, then relation R must not contain both (a, b) and (b, a). It may contain one of the ordered pairs or neither of them.
- There are 3 possible choices for all pairs.
- Therefore, the count of all combinations of these choices is equal to 3(N*(N – 1))/2.
- The number of subsets of pairs of the form (a, a) is equal to 2N.
Therefore, the total count of possible antisymmetric relations is equal to 2N * 3(N*(N – 1))/2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; const int mod = 1000000007; // Function to calculate the // value of x ^ y % mod in O(log y) 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; 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 resultant // value of x^y return res; } // Function to count the number of // antisymmetric relations in a set // consisting of N elements int antisymmetricRelation( int N) { // Print the count of // antisymmetric relations return (power(2, N) * 1LL * power(3, (N * N - N) / 2)) % mod; } // Driver Code int main() { int N = 2; cout << antisymmetricRelation(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int mod = 1000000007 ; // Function to calculate the // value of x ^ y % mod in O(log y) 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; 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 resultant // value of x^y return res; } // Function to count the number of // antisymmetric relations in a set // consisting of N elements static int antisymmetricRelation( int N) { // Print the count of // antisymmetric relations return (power( 2 , N) * power( 3 , (N * N - N) / 2 )) % mod; } // Driver Code public static void main(String []args) { int N = 2 ; System.out.print(antisymmetricRelation(N)); } } // This code is contributed by ipg2016107 |
Python3
# Python3 program for the above approach mod = 1000000007 # Function to calculate the # value of x ^ y % mod in O(log y) def power(x, y): # Stores the result of x^y res = 1 # Update x if it exceeds mod x = x % mod 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 resultant # value of x^y return res # Function to count the number of # antisymmetric relations in a set # consisting of N elements def antisymmetricRelation(N): # Print the count of # antisymmetric relations return (power( 2 , N) * power( 3 , (N * N - N) / / 2 )) % mod # Driver Code if __name__ = = "__main__" : N = 2 print (antisymmetricRelation(N)) # This code is contributed by ukasp |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int mod = 1000000007; // Function to calculate the // value of x ^ y % mod in O(log y) 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; 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 resultant // value of x^y return res; } // Function to count the number of // antisymmetric relations in a set // consisting of N elements static int antisymmetricRelation( int N) { // Print the count of // antisymmetric relations return (power(2, N) * power(3, (N * N - N) / 2)) % mod; } // Driver Code public static void Main() { int N = 2; Console.Write(antisymmetricRelation(N)); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // Javascript program for the above approach var mod = 1000000007; // Function to calculate the // value of x ^ y % mod in O(log y) function power(x, y) { // Stores the result of x^y var res = 1; // Update x if it exceeds mod x = x % mod; 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 resultant // value of x^y return res; } // Function to count the number of // antisymmetric relations in a set // consisting of N elements function antisymmetricRelation(N) { // Print the count of // antisymmetric relations return (power(2, N) * power(3, (N * N - N) / 2)) % mod; } // Driver Code var N = 2; document.write( antisymmetricRelation(N)); </script> |
12
Time Complexity: O(log N)
Auxiliary Space: O(1)
Contact Us