- Problem Statement
- Solving the inverse problem
- Inclusion Exclusion Principle
- Variations
- Conclusion
- References and Further Reading
- Appendix
Problem Statement
Let's start with the problem statement:
Count the number of permutations of digits from 0 to 9 such that the first digit is greater than 1, and the last digit is less than 8.
Solving the inverse problem
We will try to solve for the inverse problem instead. i.e. finding all permutations where the first digit is greater than 1, OR the last digit is less than 8
If we define X and Y as follows:
X: The set of permutations where the first digit is less than or equal to 1.
Y: The set of permutations where the last digit is greater than or equal to 8.
From venn diagram:
|X ∪ Y|
|X ∩ Y|:
it follows:
i.e.
|X ∪ Y| : Count of permutations with "first digit is less than or equal to 1" OR "last digit is greater than or equal to 8".
|X ∩ Y|: Count of permutations with "first digit is less than or equal to 1" AND "last digit is greater than or equal to 8".
|X ∪ Y| : Represents all the bad permutations.
This is the solution to the "inverse" problem.
So,
Our answer = All Permutations of [O, 9] - All Bad permutations
=> answer = All Permutations of [O, 9] - |X ∪ Y|
Since, `|X ∪ Y| = |X| + |Y| - |X ∩ Y|`
Answer = `Total Permutations of [O, 9] - (|X| + |Y| - |X ∩ Y|)`
Here is the code:
from math import factorial
def count_permutations_ie():
total_permutations = factorial(10)
bad_first_digit = 2 * factorial(9) # 2 options (0 or 1) for the first digit
bad_last_digit = 2 * factorial(9) # 2 options (8 or 9) for the last digit
bad_first_and_last = 2 * 2 * factorial(8) # 2 options for first, 2 for last
bad_permutations = bad_first_digit + bad_last_digit - bad_first_and_last
good_permutations = total_permutations - bad_permutations
return good_permutations
print(f"Number of permutations (IE): {count_permutations_ie()}")
This can also be solved via dynamic programming. See section Appendix.
Inclusion Exclusion Principle
What we observed above was basically the Inclusion Exclusion Principle.
To find |X ∪ Y|, we used |X| + |Y| - |X ∩ Y|.
Here is a more complete definition:
The Inclusion-Exclusion Principle is a counting technique that allows us to find the cardinality (size) of the union of multiple sets by considering their individual cardinalities, their intersections, and their complements. The principle states that:
|A_1 ∪ A_2 ∪ ... ∪ A_n| = Σ(|A_i|) - Σ(|A_i ∩ A_j|) + Σ(|A_i ∩ A_j ∩ A_k|) - ... + (-1)^(n-1) * |A_1 ∩ A_2 ∩ ... ∩ A_n|
In simpler terms, the principle says that to find the cardinality of the union of sets, we need to:
- Add the cardinalities of all the individual sets.
- Subtract the cardinalities of all pairwise intersections of the sets.
- Add the cardinalities of all triple intersections of the sets.
- Subtract the cardinalities of all quadruple intersections of the sets, and so on, alternating the signs.
This formula might seem intimidating at first, but it becomes more intuitive with examples and practice.
Variations
Variation 1: Counting Sequences with Required Elements
Consider a problem where we need to count the number of sequences of length n consisting of only 0, 1, and 2, such that each number occurs at least once.
We can represent the set of "bad" sequences (those that don't satisfy the constraint) as the union of three sets:
A_0: The set of sequences that don't contain 0.
A_1: The set of sequences that don't contain 1.
A_2: The set of sequences that don't contain 2.
Using the Inclusion-Exclusion Principle, we can find the cardinality of the "bad" sequences as:
|A_0 ∪ A_1 ∪ A_2| = |A_0| + |A_1| + |A_2| - |A_0 ∩ A_1| - |A_0 ∩ A_2| - |A_1 ∩ A_2| + |A_0 ∩ A_1 ∩ A_2|
We can calculate the cardinalities as follows:
def count_sequences(n):
total_sequences = 3 ** n
bad_sequences = 3 * (2 ** n) - 3 * (1) + 0
good_sequences = total_sequences - bad_sequences
return good_sequences
n = 5
print(f"Number of good sequences of length {n}: {count_sequences(n)}")
This code will output the number of sequences of length n that contain all three elements (0, 1, and 2) at least once.
Variation 2: Number of upper-bound integer sums
For x1 + x2 + x3 + x4 + x5 + x6 = 20, where 0 <= xi <= 8, find the number of solutions.
- Let's define the set of
"good"solutions as the set of all tuples(x1, x2, x3, x4, x5, x6)that satisfy the equationx1 + x2 + x3 + x4 + x5 + x6 = 20and the constraint0 ≤ xi ≤ 8for all i. - Also, let's define the set of
"bad"solutions as the set of tuples that violate the constraint0 ≤ xi ≤ 8for at least one value of i.
Now, we can use the Inclusion-Exclusion Principle to count the number of "bad" solutions and then subtract it from the total number of solutions to get the count of "good" solutions.
Here is the code:
from functools import lru_cache
@lru_cache(maxsize=None)
def count_solutions(target, num_vars, lower_bound=0, upper_bound=8):
"""
Count the number of solutions to the equation x1 + x2 + ... + xn = target,
where lower_bound <= xi <= upper_bound for all i.
"""
if num_vars == 1:
return 1 if lower_bound <= target <= upper_bound else 0
solutions = 0
for x in range(lower_bound, upper_bound + 1):
remaining_target = target - x
solutions += count_solutions(remaining_target, num_vars - 1, lower_bound, upper_bound)
return solutions
def count_solutions_with_inclusion_exclusion(target, num_vars, lower_bound=0, upper_bound=8):
total_solutions = count_solutions(target, num_vars, 0, upper_bound)
bad_solutions = 0
for k in range(1, num_vars + 1):
invalid_values = [0] * k + [-1] * (num_vars - k)
bad_solutions += (-1) ** k * count_solutions(target, num_vars, lower_bound, upper_bound - 1, invalid_values)
return total_solutions - bad_solutions
# Example usage
target = 20
num_vars = 6
print(f"Number of solutions: {count_solutions_with_inclusion_exclusion(target, num_vars)}")
Variation 3: Leetcode Problem Ugly Number III
This is a bit advanced. Here, the
Inclusion Exclusion Principlehelps us break down the problem so that we can apply binary search, and find the solution.
An ugly number is a positive integer that is divisible by a, b, OR c.
Given four integers n, a, b, and c, return the nth ugly number.
Basically, we can find count of such ugly numbers from 1...N by doing this:
+ count of numbers from 1..n which are divisible by a
+ count of numbers from 1..n which are divisible by b
+ count of numbers from 1..n which are divisible by c
- count of numbers from 1..n which are divisible by a AND b
- count of numbers from 1..n which are divisible by b AND c
- count of numbers from 1..n which are divisible by a AND c
+ count of numbers from 1..n which are divisible by a,b AND c
Let's call this f(K). Now the task is to find out the least K such that f(K) >= N.
We can do a binary search.
class Solution:
def gcd(self, a, b):
if b == 0:
return a
return self.gcd(b, a%b)
def lcm(self, a, b):
return (a * b) // self.gcd(a,b)
def uglyCountFrom1toN(self, a, b, c, n):
return n // a + n // b + n // c - n // self.lcm(a,b) - n // self.lcm(b,c) - n // self.lcm(a,c) + n // self.lcm(a,self.lcm(b,c))
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
lo = min(a,b,c)
hi = max(a*b*c, 2*pow(10,9))
while lo < hi:
mid = lo + (hi-lo)//2
count = self.uglyCountFrom1toN(a,b,c,mid)
# print(lo, hi, mid, count, n)
if count < n:
lo = mid+1
else:
hi = mid
# print(lo, hi)
return lo
Other Variations
You can find several other variations in this wonderful detailed article.
Conclusion
The Inclusion-Exclusion Principle is a powerful combinatorics technique that can be applied to a wide range of counting problems. While the principle's formula might seem daunting at first, its systematic approach can simplify complex counting scenarios by breaking them down into manageable parts.
By understanding the Inclusion-Exclusion Principle and practicing its application, developers can enhance their problem-solving skills and tackle intricate counting problems more effectively. Whether you're working on algorithms, probability theory, or combinatorics-related challenges, mastering this technique can be a valuable asset in your programming toolbox.
References and Further Reading
- https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#the-formulation-using-venn-diagrams
- https://codeforces.com/topic/65035
- https://leetcode.com/problems/ugly-number-iii/discuss/387539/cpp-Binary-Search-with-picture-and-Binary-Search-Template
Appendix
Can this be solved using Dynamic Programming ?
Yes.
Let's define dp[i][j] that stores the count of permutations of length i where the first digit is j.
from math import factorial
def count_permutations_dp(n):
dp = [[0] * 10 for _ in range(n + 1)]
# Base case: For permutations of length 1, there's 1 permutation for each digit
for j in range(10):
dp[1][j] = 1
# Fill the dp table
for i in range(2, n + 1):
for j in range(10):
if j > 1: # Include permutations where the first digit is greater than 1
dp[i][j] = 9 * dp[i - 1][j] + factorial(9)
else:
dp[i][j] = 8 * dp[i - 1][j]
# Calculate the desired result
result = sum(dp[n][j] for j in range(2, 8))
return result
print(f"Number of permutations (DP): {count_permutations_dp(10)}")
Time complexity: O(n * 10)
Space complexity:O(n * 10), where n is the number of digits (10 in this case).
This article was originally published on my blog at https://wewake.dev/posts/inclusion-exclusion-principle/
Find more of my content of my blog, where I share my software development experiences and learnings: https://wewake.dev
Top comments (0)