dimiTree's blog

By dimiTree, history, 4 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Link?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, i was going to say exactly that :D.

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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)$$$.

Explanation
Follow-up
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.