3 ms·
> I don’t know the size of PP(n) There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a single
by robinhouston 4y ago
> I don’t know the size of PP(n)
There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are:
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
{1, 2} | {3}
{1, 3} | {2}
{1} | {2, 3}
{1} | {2} | {3}
but most of these contain a part that only has one element. For example {1} | {2, 3} has the singleton part {1}. Only five of them have no singleton part:
{}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
(In fact all five of these consist of just a single part, but that’s just an artifact of using such a small example. If there are more than three elements then we can have things like {1, 2} | {3, 4}.)
In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial.
[0] https://en.wikipedia.org/wiki/Bell_number https://en.wikipedia.org/wiki/Bell_number