# Number of relations that are neither Reflexive nor Irreflexive on a Set

Given a positive intege **N**, the task is to find the number of relations that are neither reflexive nor irreflexive on a set of first **N** natural numbers. Since the count of relations can be very large, print it to modulo 10^{9} + 7.

A relation

Ron a setAis called reflexive, if no(a, a)€Rholds for every elementa € A.

For Example: If set A = {a, b} then R = {(a, b), (b, a)} is irreflexive relation.

**Examples:**

Input:N = 2Output:8Explanation:Considering the set {1, 2}, the total possible relations that are neither reflexive nor irreflexive are:

- {(1, 1)}
- {(1, 1), (1, 2)}
- {(1, 1), (2, 1)}
- {(1, 1), (1, 2), (2, 1)}
- {(2, 2)}
- {(2, 2), (2, 1)}
- {(2, 2), (1, 2)}
- {(2, 2), (2, 1), (1, 2)}
Therefore, the total count is 8.

Input:N = 3Output:384

**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**A * A**with**N**elements.^{2} - A relation will be
**non-reflexive**if it doesn’t contain at least one pair of**(x, x)**and relation will be non-irreflexive if it contains at least one pair of**(x, x)**where**x € R**. - It can be concluded that the relation will be non-reflexive and non-irreflexive if it contains at least one pair of
**(x, x)**and at most**(N – 1)**pairs of**(x, x)**. - Among
**N**pairs of**(x, x)**, the total number of possibilities of choosing any number of pairs except**0**and**N – 1**is**(2**. For the remaining^{N }– 2)**(N**elements, each element has two choices i.e., either to include or exclude it in the subset.^{2 }– N)

From the above observations, the total number of relations that are neither reflexive nor irreflexive on a set of first **N** natural numbers** **is given by .

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `mod = 1000000007;` `// Function to calculate x^y` `// modulo 10^9 + 7 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;` ` ` `// If x is divisible by mod` ` ` `if` `(x == 0)` ` ` `return` `0;` ` ` `while` `(y > 0) {` ` ` `// If y is odd, then` ` ` `// multiply x with res` ` ` `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 value of x^y` ` ` `return` `res;` `}` `// Function to count the number` `// of relations that are neither` `// reflexive nor irreflexive` `void` `countRelations(` `int` `N)` `{` ` ` `// Return the resultant count` ` ` `cout << (power(2, N) - 2)` ` ` `* power(2, N * N - N);` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 2;` ` ` `countRelations(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;` `class` `GFG{` `static` `int` `mod = ` `1000000007` `;` `// Function to calculate x^y` `// modulo 10^9 + 7 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;` ` ` `// If x is divisible by mod` ` ` `if` `(x == ` `0` `)` ` ` `return` `0` `;` ` ` `while` `(y > ` `0` `)` ` ` `{` ` ` ` ` `// If y is odd, then` ` ` `// multiply x with res` ` ` `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 value of x^y` ` ` `return` `res;` `}` `// Function to count the number` `// of relations that are neither` `// reflexive nor irreflexive` `static` `void` `countRelations(` `int` `N)` `{` ` ` ` ` `// Return the resultant count` ` ` `System.out.print((power(` `2` `, N) - ` `2` `) *` ` ` `power(` `2` `, N * N - N));` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `2` `;` ` ` ` ` `countRelations(N);` `}` `}` `// This code is contributed by susmitakundugoaldanga` |

## Python3

`# Python program for the above approach` `mod ` `=` `1000000007` `# Function to calculate x^y` `# modulo 10^9 + 7 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` ` ` `# If x is divisible by mod` ` ` `if` `(x ` `=` `=` `0` `):` ` ` `return` `0` ` ` `while` `(y > ` `0` `):` ` ` `# If y is odd, then` ` ` `# multiply x with res` ` ` `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 value of x^y` ` ` `return` `res` `# Function to count the number` `# of relations that are neither` `# reflexive nor irreflexive` `def` `countRelations(N):` ` ` `# Return the resultant count` ` ` `print` `((power(` `2` `, N) ` `-` `2` `) ` `*` `power(` `2` `, N ` `*` `N ` `-` `N))` `# Driver Code` `N ` `=` `2` `countRelations(N)` `# This code is contributed by abhinavjain194` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `static` `int` `mod = 1000000007;` `// Function to calculate x^y` `// modulo 10^9 + 7 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;` ` ` `// If x is divisible by mod` ` ` `if` `(x == 0)` ` ` `return` `0;` ` ` `while` `(y > 0)` ` ` `{` ` ` ` ` `// If y is odd, then` ` ` `// multiply x with res` ` ` `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 value of x^y` ` ` `return` `res;` `}` `// Function to count the number` `// of relations that are neither` `// reflexive nor irreflexive` `static` `void` `countRelations(` `int` `N)` `{` ` ` ` ` `// Return the resultant count` ` ` `Console.Write((power(2, N) - 2) *` ` ` `power(2, N * N - N));` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 2;` ` ` `countRelations(N);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript program for the above approach` `var` `mod = 1000000007;` `// Function to calculate x^y` `// modulo 10^9 + 7 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;` ` ` `// If x is divisible by mod` ` ` `if` `(x == 0)` ` ` `return` `0;` ` ` `while` `(y > 0) {` ` ` `// If y is odd, then` ` ` `// multiply x with res` ` ` `if` `(y %2 != 0)` ` ` `res = (res * x) % mod;` ` ` `// Divide y by 2` ` ` `y = y >> 1;` ` ` `// Update the value of x` ` ` `x = (x * x) % mod;` ` ` `}` ` ` `// Return the value of x^y` ` ` `return` `res;` `}` `// Function to count the number` `// of relations that are neither` `// reflexive nor irreflexive` `function` `countRelations(N)` `{` ` ` `// Return the resultant count` ` ` `document.write((power(2, N) - 2)` ` ` `* power(2, (N * N) - N));` `}` `// Driver Code` `var` `N = 2;` `countRelations(N);` `</script>` |

**Output:**

8

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.