Número de relaciones que no son reflexivas ni irreflexivas en un conjunto

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es encontrar el número de relaciones que no son ni reflexivas ni irreflexivas en un conjunto de primeros N números naturales . Dado que el recuento de relaciones puede ser muy grande, imprímalo en módulo 10 9 + 7 .

Una relación R sobre un conjunto A se llama reflexiva si no se cumple (a, a) € R para todo elemento a € A .
Por ejemplo: si el conjunto A = {a, b} entonces R = {(a, b), (b, a)} es una relación irreflexiva.

Ejemplos:

Entrada: N = 2
Salida: 8
Explicación: Considerando el conjunto {1, 2}, el total de relaciones posibles que no son ni reflexivas ni irreflexivas son:

  1. {(1, 1)}
  2. {(1, 1), (1, 2)}
  3. {(1, 1), (2, 1)}
  4. {(1, 1), (1, 2), (2, 1)}
  5. {(2, 2)}
  6. {(2, 2), (2, 1)}
  7. {(2, 2), (1, 2)}
  8. {(2, 2), (2, 1), (1, 2)}

Por lo tanto, la cuenta total es 8.

Entrada: N = 3
Salida: 384

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

  • Una relación R sobre un conjunto A es un subconjunto del producto cartesiano de un conjunto , es decir, A * A con  N 2  elementos.
  • Una relación será no reflexiva si no contiene al menos un par de (x, x) y la relación será no reflexiva si contiene al menos un par de (x, x) donde x € R .
  • Se puede concluir que la relación será no reflexiva y no irreflexiva si contiene al menos un par de (x, x) y como máximo (N – 1) pares de (x, x) .
  • Entre N pares de (x, x) , el número total de posibilidades de elegir cualquier número de pares excepto 0 y N – 1 es (2 N – 2) . Para los elementos restantes  (N 2 – N)  , cada elemento tiene dos opciones, es decir, incluirlo o excluirlo del subconjunto.

De las observaciones anteriores, el número total de relaciones que no son ni reflexivas ni irreflexivas en un conjunto de primeros N números naturales está dado por  (2^N - 2)*(2^{N^2 - N}) .

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

8

 

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *