0

I have a set A of unique elements, I want to know how many one-to-one relations on itself are possible?

peterh
  • 2,683
Rishi Prakash
  • 393

2 Answers2

2

I will recall the definition of one-to-one map for $\psi: A \rightarrow A$:

Let $(a,b) \in A$. We say that the mapping $\psi$ is one-to-one if $$\forall a \in rng (\psi) \exists b: (a,b) \in \psi$$ where $rng(\psi)$ means the range of $\psi$. This can be taken as the one-to-one mapping $\psi(a_1) = \psi(a_2) \implies a_1 = a_2$, as you require the elements to be unique for their mapping.

A relation on a set is likewise an ordered pair $(a,b) \subseteq A^2$. We can have n-ary relations on a set $A$ by taking the product $A \times A \times,...,\times A$ n-many times and denote this by $A^n, n>0$.

Since we can take a relation as an ordered pair, we can investigate the set of all functions (or ordered pairs) on $A$. This can be denoted by $A^2$, but since you require they all be unique, you would need to impose some sort of structure on $A$ for your question to be more unique to a type of relation on $A^2$ or even $A^n$ as above.

Hope this helps!

cmn1
  • 280
  • :( I am not a hard-core math student, It has confused me more. – Rishi Prakash Dec 22 '14 at 17:03
  • @RishiPrakash I am sorry if I have put too much into the definition. I believe more directly your question is answered in that the cardinality (size of the set) of the set of all relations (ordered pairs) of $A^2$ is $|A^2|\leq |2^A|$ where $|2^A|$ denotes the cardinality of the set of all subsets of $A$. – cmn1 Dec 22 '14 at 17:54
1

Hint: put $A$ in some order. How many choices for f(the first one)? Having made that choice, how many choices for f(the second one)?

The above was for one-to-one functions from $A$ to $A$. Based on your response to Thomas Andrews, I will take as the definition of a one to one relation a set of ordered pairs $(b,c) \subset A \times A$ such that no element of $A$ appears more than once as the first member and no element of $A$ appears more than once as the second member. If your definition is different, please correct me. Let $a=|A|$. Then if we ask how many relations are there that consist of $k$ pairs, you can choose the left members in $a \choose k$ ways, then choose the right members in $\frac {a!}{(a-k)!}$ ways for a total of $\frac {a!^2}{k!(a-k)!^2}$ The total number of relations come from summing over $k$, giving $$\sum_{k=0}^a \frac {a!^2}{k!(a-k)!^2}$$

The sequence starts $1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729$ and is shown in OEIS 002720. Various formulas ae given.

Ross Millikan
  • 374,822