1
$\begingroup$

Given four numbers {1,2,3,4}, how to find all possible two-way associations/relations between them? I calculate them manually as in below (50 in total) but I would like to know whether a mathematical formula exists to find them? And how about generalizing the formula for n given numbers?

{1} --> {2}, {2} --> {1},

{1} --> {3}, {3} --> {1}

{1} --> {4}, {4} --> {1}

{2} --> {3}, {3} --> {2}

{2} --> {4}, {4} --> {2}

{3} --> {4}, {4} --> {3}


{1} --> {2,3}, {2,3} --> {1},

{1} --> {2,4}, {2,4} --> {1},

{1} --> {3,4}, {3,4} --> {1},

{2} --> {1,3}, {1,3} --> {2},

{2} --> {1,4}, {1,4} --> {2},

{2} --> {3,4}, {3,4} --> {2},

{3} --> {1,2}, {1,2} --> {3},

{3} --> {1,4}, {1,4} --> {3},

{3} --> {2,4}, {2,4} --> {3},

{4} --> {1,2}, {1,2} --> {4},

{4} --> {1,3}, {1,3} --> {4},

{4} --> {2,3}, {2,3} --> {4},


{1} --> {2,3,4}, {2,3,4} --> {1},

{2} --> {1,3,4}, {1,3,4} --> {2},

{3} --> {1,2,4}, {1,2,4} --> {3},

{4} --> {1,2,3}, {1,2,3} --> {4},


{1, 2} --> {3, 4}, {3, 4} --> {1, 2},

{1, 3} --> {2, 4}, {2, 4} --> {1, 3},

{1, 4} --> {2, 3}, {2, 3} --> {1, 4},


$\endgroup$
  • 2
    $\begingroup$ It would help if you could carefully say what you mean by a two-way relation. From your examples, it seems like you've partitioned the set $\{1, 2, 3, ..., n\}$ into three sets $A, B, C$ where $A, B\neq \emptyset$ and $C$ could be empty. Then your relation is $A\to B$, $B\to A$. If that's the case, then the question is how to count the number of these partitions. $\endgroup$ – TravisJ Apr 16 '15 at 1:34
  • $\begingroup$ Thanks for the comment. I agrees with it. After posting it seems to me the problem is how to partition a set of elements into two disjoint subsets. $\endgroup$ – Joarder Kamal Apr 16 '15 at 2:30
2
$\begingroup$

Create the set $A$ by choosing at least $1$ element from $\{1, 2, 3, ..., n\}$ and leaving at least one for $B$. Suppose we chose $k$ elements ($1\leq k\leq n-1$). Now, from the remaining elements, we need to choose elements for $B$. There are $n-k\geq 1$ elements left and we must choose at least one of them. Say we choose $\ell\geq 1$ of them. There are $\binom{n}{k}\binom{n-k}{\ell}$ ways to do it as described. Now, we just need to vary $k$ and $\ell$ over the possible values they could take on (keeping in mind that the possibilities for $\ell$ depend on the choice of $k$). We end up with:

$$ \sum_{k=1}^{n-1} \binom{n}{k}\sum_{\ell=1}^{n-k}\binom{n-k}{\ell}.$$

To check that this works with $n=4$ as you gave, we have:

\begin{align*} &\binom{4}{1}\left(\binom{3}{1}+\binom{3}{2}+\binom{3}{3}\right)+\binom{4}{2}\left(\binom{2}{1}+\binom{2}{2}\right) + \binom{4}{3}\binom{1}{1} \\ &= 4(3+3+1)+6(2+1)+4(1) \\ &=4(7)+6(3)+4 \\ &=28+18+4 \\ &= 50 \end{align*}

$\endgroup$

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.