Número de relaciones reflexivas en un conjunto

Dado un número n, encuentre el número de Relación Reflexiva en un conjunto de primeros n números naturales {1, 2, ..n}.
Ejemplos: 
 

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
The given set is {1, 2, 3}. There are
64 reflexive relations on A * A :

Explicación:
Relación Reflexiva: Una Relación R en A un conjunto A se dice que es Reflexiva si xRx para cada elemento de x? UNA.
 

El número de relaciones reflexivas en un conjunto de n elementos es 2 ^{n2 – n}
¿Cómo funciona esta fórmula?  
Una relación R es reflexiva si los elementos de la diagonal de la array son 1. 
 

Si observamos más de cerca la array, podemos notar que el tamaño de la array es n ² . Las n entradas diagonales son fijas. ^{Para las n 2} – n entradas restantes , tenemos la opción de llenar 0 o 1. Por lo tanto, hay un total de 2 ^{n2 – n} formas de llenar la array.

// 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 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 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# 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 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
?>

<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>

Producción : 
 

64

 Complejidad de tiempo : O(1)

Complejidad espacial : O(1)