1
$\begingroup$

I am a newbie Mathematica user

I wanted to know, using brute force, how many non empty triplets $\{A_1,A_2,A_3\}$ of subsets of $$AA=\{1,2,3,4,5,6,7,8,9,10\}$$ satisfy the conditions

  • $A_1\cup A_2\cup A_3=AA$
  • $A_i\cap A_j=\emptyset, j\ne j$

I thought to use

AAA = Subsets[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}];
Select[Flatten[
  Table[{Union[a, b, c] == AA && Intersection[a, b] == {} && 
     Intersection[b, c] == {} && Intersection[a, c] == {}, a, b, 
    c}, {a, AAA}, {b, AAA}, {c, AAA}], 2], #[[1]] &]

Then I realized that I was building a Table containing $2^{30}$ elements and that it was useless because I just needed to know if the element of the table satisfy or not the conditions.

This kind of problem happened many times before, so I am looking for an advice to program properly this kind of query.

Thank you for your attention

$\endgroup$
1
  • $\begingroup$ Am I missing something here? 3-3 2^z+3^z for integer z>=3 length of AA (10 in your case)... $\endgroup$
    – ciao
    Nov 26, 2020 at 1:42

1 Answer 1

1
$\begingroup$

Imagine the numbers 1..10 in a row. There are 9 gaps. Dividing these numbers into 3 non-empty triplets can be done by choosing two gaps i1 and i2 with: i1<i2, 1<=i1<=8, i1+1<=i2<=9.

To get all different triplets we must permute the numbers between triplets. This can be done by: Permuting all numbers: 10! And then dividing by the number of permutations of the numbers in the first, second and third triplet: 10! /(i1! (i2-i1)! (10-i2)!):

Sum[10!/(i1! (i2 - i1)!  (10 - i2)!), {i1, 1, 8}, {i2, i1 + 1, 9}]
(*55980*)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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