We are given n disjoint, finite sets.
We would like to count the amount of all possible subsets, while having the following restriction: we are only allowed to include a max of one element each out of every of our n disjoint sets.
My initial thought was to count all possible subsets of size {0, 1, ..., n} and sum them up.
Code
There is probably a much more elegant and efficient solution out there.
Feel free to share your ideas!
Link?
Unfortunately this is from a Discrete Math exercise collection. While this may turn out to be a future contest problem, I'm not aware of any concrete link having this exact same problem.
But as this boils down to the same idea like the problem of counting the number of divisors (lookup the comment from nikilrselvam for explanation). The best link I could provide would be CSES Counting Divisors.
Well, i was going to say exactly that :D.
If all the sets are pairwise disjoint and $$$s_i$$$ denotes the size of the $$$i^{th}$$$ set, then the number of possible subsets with at most one element from each is $$$\prod_{i=1}^{n} (s_i+1)$$$.
When you are building a subset, from each of the $$$n$$$ sets you can either pick some element ($$$s_i$$$ choices) or pick none at all (1 choice). There are are a total of $$$s_i+1$$$ choices for each set, leading to the final answer.
Given a positive integer and its prime factorization, can you now count the number of divisors?
nikilrselvam thank you very much. I'd give you 100 upvotes if I could.
Elegant ideas like this, make Competitive Programming really enjoyable and fascinating.