How many one-to-one relations $A\rightarrow{A}$ are possible for a set $A$?

Question

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

Answer 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.

Answer 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!