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} --> {2,3}, {2,3} --> {1},
{1} --> {2,3,4}, {2,3,4} --> {1},
{1, 2} --> {3, 4}, {3, 4} --> {1, 2},
Asaf Karagila♦
Joarder KamalJoarder Kamal
$\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
$\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
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*}
TravisJTravisJ
Not the answer you're looking for? Browse other questions tagged combinatorics or ask your own question.
How many algebras are there of finite-sized $\Omega$?
combinatorics problem: find all possible ordered permutations in a tuple
Number of ways to put n labeled balls distributed among k unlabeled boxes. All boxes should be non-empty.
Finding number of subsets of set S that have r elements in common with set T
How many unordered partitions of $[n]$ are there, and how to enumerate?
Matlab Question: How to compute all partitions of [1,2,...,n] for a fixed number of parts?
Intersection of size at least two
Calculating number of functions with a power set
How to create subsequences from a set of ordered integers given the specified constraints.
Permutations and number of lists