1
$\begingroup$

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.

$\endgroup$

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.