Determine, with proof, the number of ordered triples (A_1,A_2,A_3) of sets which have the property that $$(i) A_1 \cup A_2 \cup A_3 = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\},$$ and $$(ii) A_1 \cap A_2 \cap A_3 = \emptyset,$$ where $\emptyset$ denotes the empty set. Express the answer in the form $$2^{a}3^{b}5^{c}7^{d},$$ where a, b, c, and d are nonnegative integers.

Hello, first, I want to say that I know the problem is well known and there are questions here about the problem. But, I don't want to see how to solve it too early, so I am posting this question to show my work, which actually is wrong. So, it is not a duplicate and is not a homework check, because I already know it is wrong. I would appreciate knowing where it is wrong.

I am not sure if I am interpreting the problem right, but what I imagine they are asking is, for example the number of ways to do things like this: (1234567,8,9 10).

So, following it, I thought that would be a nice way to attack the problem considering $12$ empty spaces. So we will need to fill the 12 empty spaces with $10$ numbers plus two commas.

The first and the last space can not have comma (it would represent $A_1$ or $A_3$ equal the empty space), so we can have in the first space $10$ numbers, in the last space $9$ numbers. Having done that, we yet have $10$ characters to distribute between the spaces. Since the order matters, it means that we have $10!$ possible ways to do it.

Summarizing, we have $$10 \cdot 9 \cdot 10!$$ way.

(What I am doing here is considering the space before the first comma as $A_1$, between commas $A_2$, and after the second comma $A_3$)

What is the problem??

  • $\begingroup$ Can any $A_i$ be empty? $\endgroup$ – cosmo5 Nov 25 '20 at 13:27
  • 1
    $\begingroup$ @cosmo5 given the way the problem is worded, yes. Otherwise the answer would involve the second stirling number ${{10}\brace 3} = 9330 = 2\cdot 3\cdot 5\cdot 311$ which can not be expressed as a $7$-smooth number. $\endgroup$ – JMoravitz Nov 25 '20 at 14:53

You are not counting partitions like $A_1=\{4\},A_2=\{8\},A_3=\{1,2,3,5,6,7,9,10\}$ that have their numbers out of order. The sets can be empty too since the question did not rule it out.

  • 1
    $\begingroup$ I think you misunderstood what the OP's (incorrect) solution was intending to do. They are really just counting various strings with 12 symbols (treating 10 as a single symbol, and also the two commas as symbols). So where it says spaces, it really means locations where a symbol should go (and not the space between the numbers). $\endgroup$ – Jaap Scherphuis Nov 25 '20 at 14:32


Each of the numbers $1,2,3,4,\dots,10$ will fall into exactly one of the following six cases:

  • In $A_1$ only and not $A_2$ or $A_3$
  • In $A_2$ only and not $A_1$ or $A_3$
  • In $A_3$ only and not $A_1$ or $A_2$
  • In both $A_1$ and $A_2$ but not in $A_3$
  • In both $A_1$ and $A_3$ but not in $A_2$
  • In both $A_2$ and $A_3$ but not in $A_1$

The condition that $A_1\cup A_2\cup A_3 = \{1,2,3,\dots,10\}$ implies that it is never the case that there are values who are in none of $A_1,A_2,A_3$. The condition that $A_1\cap A_2\cap A_3=\emptyset$ implies that it is never the case that there are values who are in all of $A_1,A_2,A_3$ simultaneously.

Apply rule of product (multiplication principle). Pick which case the element $1$ falls under. Pick which case the element $2$ falls under. Continue in this fashion deciding which case each element falls under.


$6^{10}=2^{10}\cdot 3^{10}$


Your main problem is that the order within a set $A_i$ does not matter, so for example the list $12345678,9,10$ is the same as $87654321,9,10$, but you are counting those as different.

Another more minor problem is that you are treating the two commas as distinct, so are double counting every string. Lastly, you are not allowing $A_1$ and $A_3$ to be empty but are allowing $A_2$ to be empty, which is inconsistent. As Parcly points out, there is nothing in the question that says they are not allowed to be empty.

There is another problem with your approach that I also missed until I saw JMoravitz's solution. A number can be an element of two of the three sets $A_i$. The requirement that $A_1\cap A_2\cap A_3 = \emptyset$ only rules out that a number is in all three sets simultaneously.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.