# Number of $3$ distinct subsets of an $n$-element set with nonempty pairwise intersection

The question I'm facing is a combinatorial one. Assuming there is an $n$-element set (for the sake of simplicity $\{1,2,...,n\}$) I'm asked to count the number of ways of choosing $3$ subsets of this set with the property that every $2$ have at least one element in their intersection.

My answer would be $\binom{n}{3}8^{n-3}$ -- I am first forced to choose 3 elements which will fulfill the requirement of nonempty pairwise intersection (I put each of the chosen elements in one such intersection) and then the rest of the elements have 8 choices. They can be in every subset, none of them, in just one (3 options) or in an intersection (3 choices).

I'm wondering, is that a correct approach?

Edit: Ok, I know it's not now, as I count some choices more than once (i.e. when I first choose say $1,2,3$ and then $4,5,6$ to each of the $3$ subsets and the other way round). Additioanlly there should be $3!$ before the binomial sign. Anyways it's incorrect.

I'm starting to think this can be done with the use of inclusion-exlusion principle. I jus't don't know how...

Please guys, do you have some hints?

• I like the approach, but haven't you counted the same trio of sets in more than one way? (problem being: which set is which?) – Justin Benfield Mar 12 '16 at 10:15
• Be careful. All three sets could share exactly one element. – N. F. Taussig Mar 12 '16 at 10:18
• @JustinBenfield yeah, you're right... Dang it. – Jules Mar 12 '16 at 10:20
• I've always found problems like these really hard, and I even took a Topics in Combinatorics class and did well in it. The challenge is always in devising the right counting scheme. – Justin Benfield Mar 12 '16 at 10:24

Alrighty, I'm going to answer my own question. The answer would be $$8^n-3\cdot 6^n + 3\cdot 5^n - 4^n$$ and the inteterpretation is following: once again there are $8$ choices in total, so there are $8^n$ possibilities of choosing $3$ subsets of an $n$-element set. However, one must deduct all such possibilities, where no element is in the intersection of some two sets ($3$ such situations and if it is not in an intersection of a pair then in particular it is not in the intersection of all of the sets, so we're left with $6$ choices). But then, note we have deducted all the sets which have unempty intersection in general, and we did it $3$ times! So we add them back up. Finally, we remove completely disjoint sets.
• Hi, I was reading your answer, can you please explain from where the 8 comes for, I know that if you need to divide set into 3 subsets isn't every element have 3 choices so we will have $3^n$ possibilities in total? – misha312 Aug 27 '17 at 12:51
• The subsets need not to be exclusive. So we map an element to $1$ if it's in the subset and $0$ if it is not. That gives us $2^n$ possible subsets (and we do it $3$ times). – Jules Aug 27 '17 at 14:16