# Number of combinations for creating subsets including all items

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.

## 1 Answer

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

• 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. – Aart Stuurman Feb 12 '18 at 23:01