Math Dopers: a reference question about set theory

Factual Questions
21

[QUOTE=tim314]
Assuming I haven’t made a mistake in my reasoning above, it shouldn’t be hard to turn that into a formal proof for the k = 2 case. For k > 2, I’d think you could define T[sub]0/sub as {All t in T(n, k) such that t contains the nullset} and then work out a recursion relation for T[sub]0/sub, use this to determine T[sub]0/sub in closed form, and plug that into your recursion relation for T(n,k)
[/QUOTE]

T[sub]0[/sub](n, k) is just S(n+1, k) (Stirling number of the second kind, as in my previous post): the “partial partitions” of [1..n] with k many classes which do contain an empty set are in bijection with the “partial partitions” of [1..n] with (k-1) many classes which do not contain an empty set, which, by your observation from before, is in bijection with the “full partitions” of [1..n+1] with k many classes which do not contain an empty set, the cardinality of which is the definition of S(n+1, k).

I don’t know of any good closed form for T[sub]0[/sub](n, k) = S(n+1, k), but the Wikipedia link gives various facts, including a straightforward recurrence relation.

22

[QUOTE=scotandrsn]
Nothing spoiled but my conceit that perhaps I was onto something fresh that I needed to be cagey about. But then that 's what always happens. :slight_smile:

I was moved to examine the set T(n, 2) by a problem in social networking theory I’m looking at. I discovered that:

card(T(1,2)) = 1
card(T(2,2)) = 4
card(T(3,2)) = 13
card(T(4,2)) = 40
card(T(5,2)) = 121

simply by generating the second power sets for each n and counting. Why yes, the last one DID take several hours, why do you ask? What, I had to be SURE!!!

So the principle seems to be that card(T(n+1, 2)) = 3(card(T(n, 2)) +1 = 3^n + card(T(n, 2)).

So I’m looking for how to construct an inductive proof of this.
[/QUOTE]

Incidentally, for the particular case of T(n, 2), as you’ve probably already realized, the value is always equal to (3^n-1)/2. There’s an easy way to see why, without any recurrence related reasoning: suppose you actually cared about the ordering of the two sets in your sub-partition; hell, let’s go even further and suppose you were cool with having the empty set in there twice. The number of ways of doing it would then be equal to the number of ways of assigning one of three values to each number in [1, n], the three values being “I’m in the first part of the ordered partial partition”, “I’m in the second part”, and “I’m not in any part”. This number is clearly 3^n. Since you’re not actually cool with having the empty set in there twice, we move down to 3^n - 1. And since you do actually care about the ordering, we have to remove the repeat counting. Each set you care about is exactly double counted because it can be given precisely two orders. Thus, we end up with the number (3^n - 1)/2 for what you actually want.

This would pretty straightforwardly generalize to T(n, k) for arbitrary k, except for all the trickiness dealing with the possibility of having the empty set in the ordered partial partition more than once. The hairiness of that part is what seems to prevent any nice closed form, and compel the use of something like Stirling numbers.

23

[QUOTE=Indistinguishable]
Incidentally, for the particular case of T(n, 2), as you’ve probably already realized, the value is always equal to (3^n-1)/2…
[/QUOTE]

No, I hadn’t. I’m really not very good with this sort of thing. Thanks for the insight.