# Find all possible two-way associations/relations between four numbers

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

• 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. – TravisJ Apr 16 '15 at 1:34
• 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. – Joarder Kamal Apr 16 '15 at 2:30

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: