1
$\begingroup$

In how many ways can we select $4$ disjoint subsets of the set $\{1,2,\ldots,10\}$?

OK for subsets of 1 element each, there are 10C4 subsets. For subsets of $2$ elements each, there are $$\binom{10}{2}\cdot\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}$$ Then we have subsets of $3+3+3+1$: $\binom{10}{3}\cdot\binom{7}{3}\cdot\binom{4}{3}$

Also: $$ \begin{array}{cc} 1+1+1+2,&1+1+1+3,\\ 1+1+2+2,&1+2+2+2,\\ 1+1+2+3,&1+2+2+3,\\ 2+2+2+3,&1+2+3+3,\\ 2+2+3+3,&1+3+3+3,\\ 1+1+3+3,&1+2+2+2 \end{array} $$

Plus the empty subset?

And at the end we multiply all these numbers?

$\endgroup$
6
  • $\begingroup$ If $P(A,B,C,D)$ stands for $A,B,C,D$ are disjoint subsets of $\{1,\dots,10\}$ then are you asking for the cardinality of $\{\{A,B,C,D\}\mid P(A,B,C,D)\}$ or of $\{\langle A,B,C,D\rangle\mid P(A,B,C,D)\}$? $\endgroup$ Commented Oct 27, 2017 at 14:40
  • $\begingroup$ @drhab: Sorry, I am not very familiar with combinatorics so I do not understand your question: what is P? I am asking for the total possible ways to select 4 disjoint subsets from {1,2,.....,10}. For example, if S1, S2, S3 and S4 are the subsets, one way would be S1={1}, S2={2}, S3={3} and S4={4,5}. Thank you! $\endgroup$ Commented Oct 27, 2017 at 14:42
  • 1
    $\begingroup$ I only used $P$ to make it myself easy with notation. It is the P of Property. I started my comment with mentioning the meaning: "$P(A,B,C,D)$ stands for..." $\endgroup$ Commented Oct 27, 2017 at 14:44
  • $\begingroup$ What you did is one way of solving the question. At the end you should just add all these numbers as these are all different events. The event that you get 4 subsets of size 1,1,1,2 cannot be multiplied by the event that you get 4 subsets of size 1,1,1,3, that makes no sense whatsoever. $\endgroup$ Commented Oct 27, 2017 at 14:55
  • $\begingroup$ OK understood. Question: Is {1},{2},{3},{4} different from {1},{2},{4},{3}? $\endgroup$ Commented Oct 27, 2017 at 15:02

1 Answer 1

Reset to default
2
$\begingroup$

[2017-10-29]: Answer revised thanks to OP's comment below.

Note: The problem is somewhat ambiguously formulated. Here we consider an interpretation the author had presumably in mind.

At first let's have a look at the problem again and check the formulation:

  • Select four disjoint subsets of $\{1,2,\ldots,10\}$: The empty set $\emptyset$ is a valid subset of $\{1,2,\ldots,10\}$ and since there is no other requirement to the four subsets than being disjoint, we have to consider it as well as any other subset.

  • The phrase four disjoint subsets is somewhat unprecise. If we consider four subsets $A_1,A_2,A_3,A_4$ then it could mean either the intersection of all four subsets is empty or it could mean the intersection of each pair of the four subsets is empty. This is not the same. In the first case \begin{align*} A_1=\{1\},A_2=\{1,2\},A_3=\{1\},A_4=\{10\} \end{align*} is a valid selection, since $A_1\cap A_2 \cap A_3 \cap A_4=\emptyset$ . In the second case this is not a valid selection, since e.g. $A_1\cap A_2=\{1\}\ne \emptyset$. Here we consider the second case which is usually meant with this phrase. Observe that in this case the number of empty sets may vary between zero and four within a selection of four subsets.

  • Order of subsets: A statement if the order of subsets is relevant is missing in the problem. It is not clear for instance if the selections $(A_1,A_2,A_3,A_4)$ and $(A_1,A_4,A_3,A_2)$ should be regarded the same or not. Here we consider the order as relevant.

In order to avoid ambiguities we clearly state the relevant aspects of the problem:

Problem: We consider four pairwise disjoint subsets of a set $S=\{1,2,\ldots,10\}$ including the empty set where the order of selection of subsets matters.

Solution: We can count the valid selections of four pairwise disjoint subsets $A_1,A_2,A_3,A_4$ surprisingly simple. We start with four empty subsets $A_1,A_2,A_3,A_4$ and obtain a valid selection by taking element $1\in S$ and putting it in one of four subsets or in no subset at all.This can be done in $5$ different ways. We continue this process for each of the $10$ elements and conclude:

The number of valid selections is $$\color{blue}{5^{10}=9\,765\,625}$$

That's all.

$\endgroup$
3
  • $\begingroup$ Many thanks for your solution. I have been told that the correct answer is 5^10 because the problem is equivalent to the following: In how many different ways can we place 10 balls in 5 boxes (they consider the 5th box as the one containing the balls that were not placed in the other 4). What do you think? $\endgroup$ Commented Oct 28, 2017 at 23:27
  • $\begingroup$ ...and also I think that the problem refers to pairwise disjoint subsets. $\endgroup$ Commented Oct 28, 2017 at 23:31
  • $\begingroup$ @Samuel: You're welcome. The big difference is an ambiguity regarding the order of selection of subsets. I've addressed this ambiguity and updated the answer to obtain the solution the author had presumably in mind. $\endgroup$ Commented Oct 29, 2017 at 10:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.