Ask Me Help Desk - combination and probability

You asked: "What is the probability that any two sets will have at least one element common," but that doesn't seem like what you were trying to actually figure out. It seems you want to determine is many combinations of digits you can get where (a) there are no repeated digits in the number, and (b) order is ignored. Thus the number 1234 is considered to be the same as 2134, and hence one of those is discounted - correct? Once you have this number you easily calculate the probability that you're looking for.

I don't think there is a single formula for this. To find out how many unique sets there are you need to use a series of nested sums that would look like this:

$ N = \displaystyle \sum_{a=0} ^{m_1}\ ( \displaystyle \sum_{b=a+1} ^{m_2}\ ( \displaystyle \sum_{c=b+1} ^{m_3}\ ... \ ( \displaystyle \sum_{j=i+1} ^{m_k} 1)...)) $

where there is a nested sum for each of the k sets. Here's an example: if you have four sets of numbers like this:

01
0123
01234
0123456

Then m1=1, m2=3, m3=4 and m4=6, so you have:

$ N = \displaystyle \sum_{a=0} ^{1}\ ( \displaystyle \sum_{b=a+1} ^{3} \ ( \displaystyle \sum_{c=b+1} ^{4}\ ( \displaystyle \sum_{d=c+1} ^{6} 1)) $

As a, b, c and d cycle through their ranges you get this:

$ \begin{matrix} a & b & c & d & sum\\ - & - & - & --- & -\\ 0 & 1 & 2 & 3 - 6 & 4\\ 0 & 1 & 3 & 4-6 & 3\\ 0 & 1 & 4 & 5-6 & 2\\ 0 & 2 & 3& 4-6& 3\\ 0 & 2 & 4 & 5-6 & 2\\ 0 & 3 & 4 & 5-6& 2\\ 1 & 2 & 3 & 4-6 & 3\\ 1 & 2 & 4 & 5-6 & 2\\ 1 & 3 & 4 & 5-6 & 2 \\ &&&& ---\\ &&&&Total: 23 \end{matrix} $

Hence a total of N=23 possibilities of unique combinations with no repeated digits. The specific combinations are:
0123, 0124, 0125, 0126, 0134, 0135, 0136, 0145, 0146, 0234, 0235, 0236, 0245, 0246, 0345, 0346, 1234, 1235, 1236, 1245, 1246, 1345, 1346