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
  • 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$ Commented Apr 16, 2015 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$ Commented Apr 16, 2015 at 2:30

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.