Hmm . . . let me try to reason out why that formula holds.

Start with S with n elements. Suppose we find that there are N sets of 2 disjoint subsets of S.

Now, move to S’ with n+1 element. That gives one more element to work with. Call the new element x.

So, the sets of 2 disjoint subsets of S’ will be all the sets of 2 disjoint subsets of S, plus we can take each of them again but add x to the first (inner) subset, plus we can take each of them again and add x to the second inner subset.

**So that gives ***three times* as many sets of two disjoint subsets.

Example:

If n was 2, we had:

{{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}}

and now we have:

**(1)** The original sets:

{{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}}

**(2)** The sets where x is added to the first set:

{{x},{a}}, {{x},{b}}, {{x},{a,b}}, {{a,x},{b}}

**(3)** The sets where x is added to the second set:

{{},{a,x}}, {{},{b,x}}, {{},{a,b,x}}, {{a},{b,x}}

However, what about taking sets of one disjoint subset, and then promoting them to sets of two disjoint subsets by adding the set containing x alone? It seems like this would add one set of two disjoint subsets for each of our original sets of one disjoint subset, but in fact there’s some double counting here:

Example (n=2):

We had:

{{}},{{a}},{{b}}

And now we have:

{{},{x}},{{a},{x}},{{b},{x}}

Note that the latter two of these already occured above. The key observation is this:

For every set of one set that *isn’t* the nullset, there was a set of two sets which contained that set and the nullset. Adding {x} to the set of one set then produces the same thing as adding x to the nullset within the set of two sets.

E.g.:

{{a}} → {{a},{x}}

{{a},{}} → {{a},{x}}

So, the only sets of one set that matter are those that already contain the nullset (because you can’t have a set of two sets that contains the nullset twice).

**So, we only have to ***add 1* for the set {{},{x}}, which I produced by adding {x} to to the set {{}}.

This gives:

card(T(n+1, 2)) = 3(card(T(n, 2)) +1

And it seems (but I haven’t checked carefully) that it should generalize to:

card(T(n+1, k)) = (k+1)(card(T(n, k)) + card({All t in T(n, k-1) such that t contains the nullset})

It just happens that for k = 2 there’s only *one* set in T(n,k-1) that contains the nullset (namely {{}}), making the formula a bit simpler.