# Basic combinatorics for rule learning

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.

• You're close. One of your factors is useless. Look at each of the three factors and ask yourself why you're including them. Jun 6, 2017 at 16:44
• @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? Jun 6, 2017 at 19:16
• Yes that's right. Jun 6, 2017 at 19:38
• 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?
– whuber
Jun 6, 2017 at 20:17
• The first ball has probability 3/40 to be red, the second 2/39, thus, 3/40 * 2/39 = (38C1) / (40C3) = 0.003846 Jun 6, 2017 at 21:14

\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}}}