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?

  • $\begingroup$ 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?) $\endgroup$ – Justin Benfield Mar 12 '16 at 10:15
  • $\begingroup$ Be careful. All three sets could share exactly one element. $\endgroup$ – N. F. Taussig Mar 12 '16 at 10:18
  • $\begingroup$ @JustinBenfield yeah, you're right... Dang it. $\endgroup$ – Jules Mar 12 '16 at 10:20
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – misha312 Aug 27 '17 at 12:51
  • $\begingroup$ 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). $\endgroup$ – Jules Aug 27 '17 at 14:16

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.