If I may, I would like to verify my solution of a couple of homework questions, and by doing so asking a few questions about these topics.

  1. Let $X$ be a set of size $n$. How many distinct triplets $(A, B, C)$ are there such that A, B and C are non-empty disjoint subsets of X? (I hope I'm using the right terminology)

My idea was to associate a function from $X$ to $\{0, 1, 2, 3\}$ so that for each $x \in X$, for example if $x \in A$ then $f(x) = 1$, etc... and if $x$ is not element of neither $A$, $B$ nor $C$ then $f(x) = 0$. So in total without restrictions there are $4^n$ such functions, we'll call that group $U$.

Since $A, B, C$ must not be empty, I used inclusion-exclusion to reach this answer: $4^n - 3 \cdot 3^n + 3 \cdot 2^n - 1$ Because there are $3^n$ functions where one of $A, B, C$ is empty, $2^n$ where two of them are empty and one function where they are all empty. Is this right?

  1. How many ways are there to select $3$ non-empty disjoint subsets of $X$ if they are non-distinguishable?

Here I'm less certain of my answer and also it isn't simplified enough. Also, Stirling numbers are not included in my course subjects.

We can choose to partition all the $n$ elements to $3$ sets, there are $S(n, 3)$ to do that. We can choose $n-1$ elements out of $n$ and partition them to $3$ sets, so $$\frac{n(n-1)(n-2) \cdot S(n-1, 3)}{6}$$ ways, and so on. The answer is the sum of this series.

Is this solution correct? How to simplify this series sum? What is a simpler solution, maybe without using Stirling number?

Thank you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.