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.

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

$\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 '18 at 23:01

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.