Count of all possible pairs of disjoint subsets of integers from 1 to N

0 0 5 minutes read

Given an integer, N. Consider the set of first N natural numbers A = {1, 2, 3, …, N}. Let M and P be two non-empty subsets of A. The task is to count the number of unordered pairs of (M, P) such that M and P are disjoint sets. Note that the order of M and P doesn’t matter. Examples:

Input: N = 3
Output: 6
Explanation: The unordered pairs are ({1}, {2}), ({1}, {3}), ({2}, {3}), ({1}, {2, 3}), ({2}, {1, 3}), ({3}, {1, 2}).

Input: N = 2
Output: 1

Input: N = 10
Output: 28501

Approach:

Lets assume there are only 6 elements in the set {1, 2, 3, 4, 5, 6}.
When you count the number of subsets with 1 as one of the element of first subset, it comes out to be 211.
Counting number of subsets with 2 being one of the element of first subset, it comes out to be 65, because 1’s not included as order of sets doesn’t matter.
Counting number of subset with 3 being one of the element of first set it comes out to be 65, here a pattern can be observed.
Pattern:

5 = 3 * 1 + 2 19 = 3 * 5 + 4 65 = 3 * 19 + 8 211 = 3 * 65 + 16 S(n) = 3 * S(n-1) + 2^{(n – 2)}

Expanding it until n->2 (means numbers of elements n-2+1=n-1) 2^(n-2) * 3⁽⁰⁾ + 2^{(n – 3)} * 3¹ + 2^{(n – 4)} * 3² + 2^{(n – 5)} * 3³ + … + 2⁽⁰⁾ * 3^{(n – 2)} From Geometric progression, a + a * r⁰ + a * r¹ + … + a * r^{(n – 1)} = a * (rⁿ – 1) / (r – 1)
S(n) = 3^{(n – 1)} – 2^{(n – 1)}. Remember S(n) is number of subsets with 1 as a one of the elements of first subset but to get the required result, Denoted by T(n) = S(1) + S(2) + S(3) + … +S(n)
It also forms a Geometric progression, so we calculate it by formula of sum of GP T(n) = (3ⁿ – 2^{n + 1} + 1)/2
As we require T(n) % p where p = 10⁹ + 7 We have to use Fermat’s little theorem a^-1 = a^{(m – 2)} (mod m) for modular division

C++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
#define p 1000000007
 
// Modulo exponentiation function
long long power(long long x, long long y)
{
    // Function to calculate (x^y)%p in O(log(y))
    long long res = 1;
    x = x % p;
 
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
 
    return res % p;
}
 
// Driver function
int main()
{
    long long n = 3;
 
    // Evaluating ((3^n-2^(n+1)+1)/2)%p
    long long x = (power(3, n) % p + 1) % p;
 
    x = (x - power(2, n + 1) + p) % p;
 
    // From Fermats’s little theorem
    // a^-1 ? a^(m-2) (mod m)
 
    x = (x * power(2, p - 2)) % p;
    cout << x << "\n";
}

Java

// Java implementation of the approach
class GFG
{
static int p = 1000000007;
 
// Modulo exponentiation function
static long power(long x, long y)
{
    // Function to calculate (x^y)%p in O(log(y))
    long res = 1;
    x = x % p;
 
    while (y > 0)
    {
        if (y % 2 == 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
 
// Driver Code
public static void main(String[] args)
{
    long n = 3;
 
    // Evaluating ((3^n-2^(n+1)+1)/2)%p
    long x = (power(3, n) % p + 1) % p;
 
    x = (x - power(2, n + 1) + p) % p;
 
    // From Fermats's little theorem
    // a^-1 ? a^(m-2) (mod m)
 
    x = (x * power(2, p - 2)) % p;
    System.out.println(x);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach
p = 1000000007
 
# Modulo exponentiation function
def power(x, y):
     
    # Function to calculate (x^y)%p in O(log(y))
    res = 1
    x = x % p
 
    while (y > 0):
        if (y & 1):
            res = (res * x) % p;
        y = y >> 1
        x = (x * x) % p
 
    return res % p
 
# Driver Code
n = 3
 
# Evaluating ((3^n-2^(n+1)+1)/2)%p
x = (power(3, n) % p + 1) % p
 
x = (x - power(2, n + 1) + p) % p
 
# From Fermats’s little theorem
# a^-1 ? a^(m-2) (mod m)
x = (x * power(2, p - 2)) % p
 
print(x)
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
static int p = 1000000007;
 
// Modulo exponentiation function
static long power(long x, long y)
{
    // Function to calculate (x^y)%p in O(log(y))
    long res = 1;
    x = x % p;
 
    while (y > 0)
    {
        if (y % 2 == 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
 
// Driver Code
static public void Main ()
{
    long n = 3;
     
    // Evaluating ((3^n-2^(n+1)+1)/2)%p
    long x = (power(3, n) % p + 1) % p;
     
    x = (x - power(2, n + 1) + p) % p;
     
    // From Fermats's little theorem
    // a^-1 ? a^(m-2) (mod m)
     
    x = (x * power(2, p - 2)) % p;
    Console.Write(x);
}
}
 
// This code is contributed by ajit.

Javascript

// JS implementation of the approach
 
let p = 1000000007n
 
// Modulo exponentiation function
function power(x, y)
{
    // Function to calculate (x^y)%p in O(log(y))
    let res = 1n;
    x = x % p;
 
    while (y > 0n) {
        if (y & 1n)
            res = (res * x) % p;
        y = y >> 1n;
        x = (x * x) % p;
    }
 
    return res % p;
}
 
// Driver function
let n = 3n;
 
// Evaluating ((3^n-2^(n+1)+1)/2)%p
let x = (power(3n, n) % p + 1n) % p;
 
x = (x - power(2n, n + 1n) + p) % p;
 
// From Fermats’s little theorem
// a^-1 ? a^(m-2) (mod m)
 
x = (x * power(2n, p - 2n)) % p;
console.log(x)
 
 
// This code is contributed by phasing17

Time Complexity: O(log(n)+log(p))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!