This is supposed to be a rather rudimentary combinatorics problem, however, I can't seem to wrap my head around it.

The Problem

There are 40 distinct items, one person can pick (up to) 3 items. To reduce complexity, one could also assume that each person will pick exactly 3 items. For any single pair of items, I would like to calculate the probability of it to be contained in the itemset of three.

The general idea is to use this as the min-support for the rule learner.

My calculation, so far (simple case):

$$ \begin{align*} A &:= \text{Pair of Items in Itemset}\\ \\ P(A) &= {{\text{Combinations 2 in 3}\cdot \text{Possible values for 3rd item}}\over{\text{Number of itemsets of 3}}} \\ &= {{\binom{3}{2}\cdot38}\over{\binom{40}{3}}}\\ &= 0.01153846153 \end{align*} $$

However, I feel like I might be missing something. Can you verify/falsify/correct my approach? Also, comments on the goal would be much appreciated.

  • $\begingroup$ You're close. One of your factors is useless. Look at each of the three factors and ask yourself why you're including them. $\endgroup$ Jun 6, 2017 at 16:44
  • $\begingroup$ @Bridgeburners Thanks a lot for your reply and the hint. I think that Combinations 2 in 3 must be dropped, because the itemset either contains the pair of items or it doesn't. Each itemset of three which contains the pair is then only destinguished by the 3rd item. Is that correct? $\endgroup$
    – daveknave
    Jun 6, 2017 at 19:16
  • $\begingroup$ Yes that's right. $\endgroup$ Jun 6, 2017 at 19:38
  • $\begingroup$ A physical model might help you think through this. Let the 40 items be white. Paint the three chosen items red. Put the 37 remaining white items and the three red items into a box. Mix them thoroughly. Model the selection of a pair of items by drawing two items blindly out of the box. What is the chance that both those items are red? $\endgroup$
    – whuber
    Jun 6, 2017 at 20:17
  • 1
    $\begingroup$ The first ball has probability 3/40 to be red, the second 2/39, thus, 3/40 * 2/39 = (38C1) / (40C3) = 0.003846 $\endgroup$
    – daveknave
    Jun 6, 2017 at 21:14

2 Answers 2


To sum up the helpfull comments, I put this into a formal model:

$$ \begin{align*} I &: \text{Set of selectable items of size }n\\ S &: \text{Selection set of size }k &\quad(s_i \in S \subset I)\\ R &: \text{Selection set (Association Rule) of size }v &\quad(r_j \in R \subset I) \end{align*} \\ P(R \subset S) = {{\binom{n-v}{k-v}} \over {\binom{n}{k}}} $$


I think a valid argument could be to say: Imagine you are given a 3 item subset from the 40 items. Conditioning on this, there are (3 choose 2) pairs in the triple, and (40 choose 2) possible pairs in the entire sample. Thus, for each triple there are (3 choose 2) / (40 choose 2) chance of hitting any single pair. Since it is 1/(40 choose 3) chance of selecting the triple you conditioned on, and (40 choose 3) possibilities, they cancel out, and you are left with (3 choose 2) / (40 choose 2) = 1/260

  • $\begingroup$ Yeah, I think, in my mind, I tried to blend this approach with my answer. $\endgroup$
    – daveknave
    Jun 9, 2017 at 8:00

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.