How avoid to memorize 1 billion useless data

Question

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

Answer 1

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*)