# Thread: Counting ordered k-tuples of subsets...

1. ## Counting ordered k-tuples of subsets...

Hi,
I would deeply appreciate any help with the following problem:

Let $\displaystyle S$ be a set with $\displaystyle n$ elements, and $\displaystyle k$ some natural number. Find the number of ordered $\displaystyle k$-tuples $\displaystyle (S_1, ..., S_k)$ of subsets of $\displaystyle S$, such that:

[problem 1] $\displaystyle S_i \cap S_j = \emptyset,(\forall i \neq j)$

[problem 2] $\displaystyle S_1 \cap ... \cap S_k = \emptyset$

[problem 3] $\displaystyle S_1 \cup ... \cup S_k = S$

[problem 4] $\displaystyle S_1 \cup ... \cup S_k = S,|S_i|=n_i,\sum_{i=1}^k n_i=n,S_i \cap S_j = \emptyset,(\forall i \neq j)$

*******

I tried to make an example; let $\displaystyle S=\{1,2,3,4,5,6,7\}$ so n=7, and let k=3. So, we have to find the number of all ordered triples $\displaystyle (S_1,S_2,S_3)$ which satisfy above properties for each problem.

Now, in [problem 1] we'd have to find the number of all ordered triples of subsets of S which are disjoint in pairs, some of them are ({1},{2,3},{6}) or ({3},{4},{7}) or ({1,2,3,4},{6},{7})...

In [problem 2] we seek triples of subsets of S the intersection of which is empty. But isn't this the same as [problem 1]? It seems that, if all subsets are pairwise disjoint, then the intersection of all of them must be empty?

In [problem 3] we look for the number of ordered triples of subsets of S which, in union, yield the whole S, such as ({1,2,3},{2,3,6,7},{1,4,5,6})

The [problem 4] is similar to the [problem 3], the only difference being the requirement that all subsets in an ordered triple must be disjoint, e.g. ({1},{2,3,4,5},{6,7})

*******

I really have no idea where to start from, so I would be really grateful for your help and your time.

2. Originally Posted by gusztav
[problem 1] $\displaystyle S_i \cap S_j = \emptyset,(\forall i \neq j)$
Let us examine $\displaystyle k=3$. Draw a Venn diagram with a square around it symbolizing the outside of $\displaystyle S_1\cup S_2\cup S_3$. Now there are $\displaystyle 2^3$ possible locations to put a number if you drew out the diagram. We need to put these $\displaystyle n$ numbers into these locations in such a way that $\displaystyle S_i \cap S_j = \emptyset$ i.e. so that no two circles intersect. That means a number can go into four remaining locations: either only into $\displaystyle S_1$ or $\displaystyle S_2$ or $\displaystyle S_3$ or completely outside the circles. Therefore we are placing $\displaystyle n$ 'objects' into $\displaystyle 4$ 'boxes' and the total number is $\displaystyle {{n-4+1}\choose 4}$

If general we would have to draw $\displaystyle k$ circles which partition the plane into $\displaystyle 2^k$ regions. The total number of places to put the numbers is $\displaystyle k+1$. The number of ways of doing this is $\displaystyle {{n-k}\choose {k+1}}$

Originally Posted by gusztav
[problem 2] $\displaystyle S_1 \cap ... \cap S_k = \emptyset$
No this is not the same as problem 1. This is included in problem 1 therefore the number would be smaller.

Again draw the Venn diagrams for $\displaystyle k$ circles. This time the numbers are being places anywhere except into the middle of where all three circles intersect. That leaves us with $\displaystyle 2^k - 1$ boxes where we place $\displaystyle n$ numbers. The total number is therefore, $\displaystyle {{n-2^k}\choose 2^k}$

Try doing the others ones.
(This is how I get out of doing all the problems when I get lazy).