How to find all possible non-repeating intersections of sets?

Question

Mathematics

I need to calculate the number of possible combinations that can be obtained by combining sets (as I understand it, a mixture from combinatorics and a Cartesian product). I know how to calculate the number of combinations without repetitions for one set: n!/m!*(nm)!, where n is the number of elements of the given set, m is the number of combinations (digits). But what if you want to combine multiple sets?
Example. The first set X={1,2,3}, the second set Y={4,5}, the third set Z={6,7}. I want to get all possible combinations in single, double and triple combination. If you count by hand, it turns out (the order in the combination does not matter, there should be no repetitions, all elements of the sets are unique):
m=1: {1}, {2}, {3}, {4}, {5}, {6} , {7}, i.e. 7 combinations
m=2: {1.4}, {1.5}, {1.6}, {1.7}, {2.4}, {2.5}, {2.6}, {2.7 }, {3,4}, {3,5}, {3,6}, {3,7}, {4,6}, {4,7}, {5,6}, {5,7}, those. 16 combinations
m=3: {1,4,6}, {1,4,7}, {1,5,6}, {1,5,7}, {2,4,6}, {2,4 ,7}, {2,5,6}, {2,5,7}, {3,4,6}, {3,4,7}, {3,5,6}, {3,5,7 }, i.e. 12 combinations
In total, you can get 7+16+12=35 combinations. Is there a universal calculation formula for such a problem?

Answer 1

As I understand it, there are no common elements.
On the example of 3 sets with cardinalities a, b and c.
m=0: 1 combination
m=1: a + b + c combinations
m=2: a*b + b*c + a*c combinations
m=3: a*b*c combinations
Total
1 + a + b + c + ab + bc + ca + abc
1 + a + b + ab + c*(1 + a + b + ab)
(1 + a + b + ab)(1 + c)
...
(1 + a)( 1 + b)(1 + c)
On your data, we get 4 * 3 * 3 = 36
The answer also suggests the principle of how to calculate it. From one set, you can choose 1 + a ways: either do not take (empty set), or take a ways.
If we add a new set to consideration, then either we do not take an element from it, or we also take it, in b ways, in total: (1+a)(1+b). Those. each set Aᵢ gives us 1+|Aᵢ| new variants, where |A| - cardinality (number of elements) of the set A.
Thus . answer: ∏(1+|Aᵢ|)
Please note that this formula also takes into account the only option to choose 0 elements (the result is an empty set), which differs from what you calculated in the question by one (36 instead of 35) .