22.1.6. Applications of the Alternate Form

Now what we will do is, we will look into an alternate form of inclusion-exclusion which is very powerful and it is this alternate form of inclusion-exclusion which we use in varieties of problems. So, what happens in this alternate form is that we will be facing scenarios where we want to count the number of elements from a set A which has n number of elements and we will be interested to count the number of elements in this set which has none of the properties say P₁, P₂, ..., Pₙ. So, P₁, P₂, ..., Pₙ will be some abstract properties and we will be interested to find out the number of elements in the set A which neither have the property P nor the property P₂, nor the property Pₙ and so on.

This chunk introduces the alternate form of the principle of inclusion-exclusion, which is particularly useful in enumerative combinatorics. The focus is on counting elements in a set A that do not possess certain properties (P₁ to Pₙ). Here, we start by defining set A, which contains n elements. The goal is to find elements that lack specific characteristics without directly counting those properties. By understanding that the total count can be derived by subtracting those that have at least one of the properties from the total, we set up a framework for applying inclusion-exclusion.

Imagine you have a class of students and want to count those who don't play any sports. Each sport (like basketball, soccer, etc.) represents a property (P₁, P₂, ...). Instead of counting students who play one or more sports directly (which can be tricky due to overlaps), you first note the total number of students and then count those who play at least one sport, subtracting this from the total to find those who don't participate in any sports.

Now, let me demonstrate this alternate form of inclusion-exclusion through some examples. Suppose we want to find out the number of solutions for this equation: x₁ + x₂ + x₃ = 11; number of integer solutions. And my restrictions are x₁ should be in the range 0 to 3, x₂ should be in the range 0 to 4, and x₃ should be in the range 0 to 6. Now using the methods that we have seen till now we cannot find it directly. But what we will do is the following: we will use the alternate form of inclusion-exclusion.

This chunk presents a specific counting problem involving the equation x₁ + x₂ + x₃ = 11 with constraints on each variable's maximum value. The alternate form of inclusion-exclusion is recommended for handling such restrictions. The first step involves determining the number of unrestricted solutions. Next, you define sets for solutions that violate each restriction. By calculating the sizes of these sets and their intersections, you manage how many total solutions violate at least one restriction. Ultimately, the desired count is found by subtracting the number of violating sets from the unrestricted count.

Consider you are baking cookies with certain ingredients. You have a recipe that requires a total of 11 scoops of flour, sugar, and chocolate chips, but you are limited: maximum 3 scoops of flour, 4 of sugar, and 6 of chocolate chips. The challenge is to figure out how many ways you can combine these ingredients without exceeding the limits, similar to counting the valid combinations of x₁, x₂, and x₃ while adhering to the maximums.

To find out the cardinality of the union of the n sets because we know how to find that. So, this is the alternate form of inclusion-exclusion. For that, what we will do is we will first find out the cardinality of the universal set. Universal set in this context will be the set of all solutions where I do not put any restrictions on x₁, x₂, x₃.

In this part, the process of calculating the cardinality of the universal set is highlighted, which is essential for employing the alternate form. This universal set includes all possible combinations of solutions for x₁, x₂, and x₃ without any constraints. The method uses Venn diagrams to visualize how the intersections of sets correlate with the inclusion-exclusion principle, where the aim is to find the total scenarios that either meet the constraints or violate them. The formula thus developed allows us to conclude how many solutions fit all criteria by systematically removing the invalid cases rather than counting them directly.

Returning to our cookie example, the universal set represents all possible ways to mix 11 scoops of flour, sugar, and chocolate chips without strategy. By visualizing scenarios where certain limits are broken (like exceeding scoops of sugar), and how they intersect with others (e.g., restrictions on flour), one can easily deduce the total valid recipes by eliminating bad combinations from the initial guess of all possibilities.

So now you can see that how I use the alternate form of inclusion-exclusion for solving this problem. We can generalize this formula, so in the previous case we had the case where the first set has 6 elements and the set of possible images has 3 elements.

Here, we extend the previous example into a generalized form for any number of elements in sets A and B. The discussion points toward calculating the total number of onto functions from one set to another using the alternate form of inclusion-exclusion. This allows for clearer functions to count valid output arrangements while avoiding repetitions or missing permutations that might lead to incorrect totals. Understanding this generalized formula not only reinforces the concept but also opens up pathways for solving larger, more complex problems efficiently.

For instance, consider a school trying to assign 3 teachers (first set with 6 elements) to 2 classrooms (second set with 3 elements). Each teacher must teach at least one class (onto function), and using the methods outlined, the school can systematically determine the different valid class assignments while ensuring each class has at least one teacher using inclusion-exclusion.

--