I have a set of x number of 'A' type object, y number of 'B' type object and z number of 'C' type object. Now, I need to find the number of subsets of atmost 'k' size that can be made such that all the objects in subsets are distinct. No two same type of object will be in the same subset. The elements are same but their combinations are considered different.

Eg:- [1,1,5,5,4] and k = 3

Output:- 17


[1], [1], [5], [5], [4] => 5

[1,5], [1,5], [1,5], [1,5], [1,4], [1,4], [5,4], [5,4] => 8

[1,5,4], [1,5,4], [1,5,4], [1,5,4] => 4


The number of subsets with one element is $x+y+z$. The number with two elements is $xy+xz+yz$. The number with three elements is $xyz$. The number with more than three elements is $0$.

  • $\begingroup$ What will be a general formula for size up to "k" . $\endgroup$ – learner-coder Sep 9 '19 at 10:56
  • $\begingroup$ Its basically (x+1) * (y+1) * (z+1) .This gives all subsets but I want to find the subsets of at most "k" size. So, what approach can be taken? As we have x,y, and z only 3 elements but there can be more like A,B,C,D........X,Y. $\endgroup$ – learner-coder Sep 9 '19 at 11:23
  • $\begingroup$ @Kamesh-Bakshi It's just the sum of the products of the numbers of elements of each type, taken $k$ at a time. Don't you see the pattern? $\endgroup$ – saulspatz Sep 9 '19 at 13:17
  • $\begingroup$ Yes, I can see that. But I was just thinking to make formula as I mentioned in my previous comment by considering the size "k" $\endgroup$ – learner-coder Sep 9 '19 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.