Dado un conjunto que contiene N elementos. Si se eligieron dos subconjuntos X e Y , encuentre la probabilidad de que ambos contengan el mismo número de elementos.
Ejemplos:
Entrada: 4
Salida: 35/128
Entrada: 2
Salida: 3/8
Enfoque:
Elijamos un subconjunto X que tenga r número de elementos, luego Y debe contener r número de elementos. Un subconjunto puede tener un mínimo de 0 elementos y un máximo de N elementos.
El número total de subconjuntos de un conjunto contiene N número de elementos es
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
, La forma total posible de elegir X e Y simultáneamente será
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
=
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
=
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
.
Sea, P = Total de formas posibles de elegir X e Y de modo que ambos tengan el mismo número de elementos.
Entonces P = 
= 
= 
Así que la probabilidad requerida será 
.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Returns value of Binomial
// Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Iterative Function to
// calculate (x^y) in O(log y)
int power(int x, unsigned int y)
{
// Initialize result
int res = 1;
while (y > 0) {
// If y is odd, multiply
// x with result
if (y & 1)
res = res * x;
// y must be even now
// y = y/2
y = y >> 1;
// Change x to x^2
x = x * x;
}
return res;
}
// Function to find probability
void FindProbability(int n)
{
// Calculate total possible
// ways and favourable ways.
int up = binomialCoeff(2 * n, n);
int down = power(2, 2 * n);
// Divide by gcd such that
// they become relatively coprime
int g = __gcd(up, down);
up /= g, down /= g;
cout << up << "/" << down << endl;
}
// Driver code
int main()
{
int N = 8;
FindProbability(N);
return 0;
}
Java
// Java implementation of
// the above approach
class GFG
{
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Iterative Function to
// calculate (x^y) in O(log y)
static int power(int x, int y)
{
// Initialize result
int res = 1;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = res * x;
// y must be even now
// y = y/2
y = y >> 1;
// Change x to x^2
x = x * x;
}
return res;
}
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find probability
static void FindProbability(int n)
{
// Calculate total possible
// ways and favourable ways.
int up = binomialCoeff(2 * n, n);
int down = power(2, 2 * n);
// Divide by gcd such that
// they become relatively coprime
int g = gcd(up, down);
up /= g;
down /= g;
System.out.println(up + "/" + down);
}
// Driver code
public static void main (String[] args)
{
int N = 8;
FindProbability(N);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of # the above approach import math # Returns value of Binomial # Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k # Calculate value of for i in range(0, k): res = res * (n - i) res = res // (i + 1) return res # Iterative Function to # calculate (x^y) in O(log y) def power(x, y): # Initialize result res = 1 while (y > 0): # If y is odd, multiply # x with result if (y & 1): res = res * x # y must be even now # y = y/2 y = y // 2 # Change x to x^2 x = x * x return res # Function to find probability def FindProbability(n): # Calculate total possible # ways and favourable ways. up = binomialCoeff(2 * n, n) down = power(2, 2 * n) # Divide by gcd such that # they become relatively coprime g = math.gcd(up,down) up = up // g down = down // g print(up, "/", down) # Driver code N = 8 FindProbability(N) # This code is contributed by Sanjit_Prasad
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Iterative Function to
// calculate (x^y) in O(log y)
static int power(int x, int y)
{
// Initialize result
int res = 1;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = res * x;
// y must be even now
// y = y/2
y = y >> 1;
// Change x to x^2
x = x * x;
}
return res;
}
// Recursive function to
// return gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find probability
static void FindProbability(int n)
{
// Calculate total possible
// ways and favourable ways.
int up = binomialCoeff(2 * n, n);
int down = power(2, 2 * n);
// Divide by gcd such that
// they become relatively coprime
int g = gcd(up, down);
up /= g;
down /= g;
Console.WriteLine(up + "/" + down);
}
// Driver code
public static void Main (String[] args)
{
int N = 8;
FindProbability(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of
// the above approach
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
let res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of
for (let i = 0; i < k; ++i) {
res *= (n - i);
res = parseInt(res / (i + 1));
}
return res;
}
// Iterative Function to
// calculate (x^y) in O(log y)
function power(x, y)
{
// Initialize result
let res = 1;
while (y > 0) {
// If y is odd, multiply
// x with result
if (y & 1)
res = res * x;
// y must be even now
// y = y/2
y = y >> 1;
// Change x to x^2
x = x * x;
}
return res;
}
// Recursive function to
// return gcd of a and b
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find probability
function FindProbability(n)
{
// Calculate total possible
// ways and favourable ways.
let up = binomialCoeff(2 * n, n);
let down = power(2, 2 * n);
// Divide by gcd such that
// they become relatively coprime
let g = gcd(up, down);
up = parseInt(up / g), down = parseInt(down / g);
document.write(up + "/" + down + "<br>");
}
// Driver code
let N = 8;
FindProbability(N);
</script>
Producción:
6435/32768