Рубрики

Количество симметричных отношений на множестве

По заданному числу n выяснить число симметричных отношений на множестве первых n натуральных чисел {1, 2, ..n}.

Примеры:

Input  : n = 2
Output : 8
Given set is {1, 2}. Below are all symmetric relation.
{}
{(1, 1)}, 
{(2, 2)},
{(1, 1), (2, 2)}, 
{(1, 2), (2, 1)} 
{(1, 1), (1, 2), (2, 1)},
{(2, 2), (1, 2), (2, 1)}, 
{(1, 1), (1, 2), (2, 1), (1, 2)} 

Input  : n = 3
Output : 64

Отношение 'R' на множестве A называется симметричным, если xRy, тогда yRx для каждого x, y ∈ A
или если (x, y) ∈ R, то (y, x) ∈ R для любого x, y? A

Total number of symmetric relations is 2n(n+1)/2.

How does this formula work?

A relation R is symmetric if the value of every cell (i, j) is same as that cell (j, i). The diagonals can have any value.

There are n diagonal values, total possible combination of diagonal values = 2n
There are n2 – n non-diagonal values. We can only choose different value for half of them, because when we choose a value for cell (i, j), cell (j, i) gets same value.
So combination of non-diagonal values = 2(n2 – n)/2

Overall combination = 2n * 2(n2 – n)/2 = 2n(n+1)/2

C ++

// C ++ программа для подсчета общих симметричных отношений
// на множестве натуральных чисел.
#include <bits/stdc++.h>

  
// функция найти квадрат n

unsigned int countSymmetric(unsigned int n)

{

    // Базовый вариант

    if (n == 0)

        return 1;

  

   // Возвращаем 2 ^ (n (n + 1) / 2)

   return 1 << ((n * (n + 1))/2);

}

  
// Код драйвера

int main()

{

    unsigned int n = 3;

  

    printf("%u", countSymmetric(n));

    return 0;

}

Джава

// Java-программа для подсчета общей симметрии
// отношения на множестве натуральных чисел.

import java.io.*;

import java.util.*;

  

class GFG {

  

    // функция найти квадрат n

    static int countSymmetric(int n)

    {

        // Базовый вариант

        if (n == 0)

            return 1;

      

    // Возвращаем 2 ^ (n (n + 1) / 2)

    return 1 << ((n * (n + 1)) / 2);

    }

  

    // Код драйвера

    public static void main (String[] args) 

    {

        int n = 3;

        System.out.println(countSymmetric(n));

    }

}

  

  
// Этот код предоставлен Никитой Тивари.

python3

# Python 3 программа для подсчета
# всего симметричных отношений
# на множестве натуральных чисел.

  
# функция найти квадрат n

def countSymmetric(n) :

    # Базовый вариант

    if (n == 0) :

        return 1

   

    # Возврат 2 ^ (n (n + 1) / 2)

    return (1 << ((n * (n + 1))//2))

  

   
# Код драйвера

  

n = 3

print(countSymmetric(n))

  
# Этот код добавлен
# Никита Тивари.

C #

// C # программа для подсчета общей симметрии
// отношения на множестве натуральных чисел.

using System;

  

class GFG {

  

    // функция найти квадрат n

    static int countSymmetric(int n)

    {

        // Базовый вариант

        if (n == 0)

            return 1;

      

    // Возвращаем 2 ^ (n (n + 1) / 2)

    return 1 << ((n * (n + 1)) / 2);

    }

  

    // Код драйвера

    public static void Main () 

    {

        int n = 3;

        Console.WriteLine(countSymmetric(n));

    }

}

  

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP-программа для подсчета общей симметрии
// отношения на множестве натуральных чисел.

  
// функция найти квадрат n

function countSymmetric($n)

{

    // Базовый вариант

    if ($n == 0)

        return 1;

  

    // Возвращаем 2 ^ (n (n + 1) / 2)

    return 1 << (($n * ($n + 1))/2);

}

  

    // Код драйвера

    $n = 3;

    echo(countSymmetric($n));

      
// Этот код предоставлен vt_m.
?>

Выход:

64

Рекомендуемые посты:

Количество симметричных отношений на множестве

0.00 (0%) 0 votes