### dimiTree's blog

By dimiTree, history, 5 weeks ago, 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!  Comments (5)
 » 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)$. ExplanationWhen 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. Follow-upGiven a positive integer and its prime factorization, can you now count the number of divisors?