0
$\begingroup$

Say I have n items. How can I find the amount of combinations possible of subset sets covering all items, when order does not matter. This is maybe badly worded, so allow me to give an example:

n=3, so we have items A,B, and C. All possible subset sets covering all items would be - [A B C] - [A BC] - [AC B] - [AB C] - [ABC] That makes for 5 possibilities.

Say the function to calculate this is f(n) and the total amount of subsets in all sets is g(n) (that would mean g(3) as in the example is 10). I managed to figure out f(n)=f(n-1)+g(n-1). However, this is where I am kind of stuck.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

These are counted by Bell Numbers. Unfortunately there is no explicit formula for $f(n)$, but there are plenty of recursions. For example:

$$f(n+1)=\sum_{k=0}^n\binom{n}{k}f(k).$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ I just found out about that using oeis.org, which apparently is a pretty great site for finding out this kind of stuff. It's a shame that there is no explicit, but I guess recursive is alright for the problem I'm trying to solve. $\endgroup$
    – Aart Stuurman
    Feb 12, 2018 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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