I don't really know how to introduce this question, so I start defining something I needed in order to well understand the problem I met!
Let $A$, $B$ two finite sets of distinct elements, with $|A|=|B|$. If I recall correctly, all of the possible permutations of a finite set is the symmetric group on that set, thus we can define $S_A$ and $S_B$ where $|S_A| = |A|!$ and $|S_B| = |B|!$.
Having the previous definitions, I wish to create a set which contains all of the possible permutations of the elements of the two symmetric groups, that is $X = S_A \times S_B$, where an element in $X$ is a pair $\langle p_A,p_B\rangle$ where $p_A\in S_A$ and $p_B\in S_B$. $X$ should contain all of the possible permutations; however, I'm not interested in a special set of permutations. I'm not sure how to clearly express this set, so I show you an example.
Suppose $A = \{a,b,c\}$ and $B = \{x,y,z\}$. Let's take two possible permutations: $p_1 = abc$ and $p_2 = xyz$ (the identity ones?). Obviously, $\langle p_1,p_2\rangle\in X$.
Suppose I draw the two permutations one below the other, I can define a sort of vertical correspondence:
abc
xyz
where a is in correspondence with x , b with y and c with z.
Now, let's take two more permutations $p_3 = cab$ and $p_4 = zxy$. Obviously, $\langle p_3,p_4\rangle\in X$, and as you can see, these two permutations have the exactly correspondences that I just had for $p_1,p_2$.
So, here's my doubt: is there any way of compute the cardinality of the set $Y \subset X$ where $Y$ does not contain any two pair of permutations which have the same correspondences? It is not a homework, thus I do not want to ask you for the result but I could use a little help :P
(This is my first time here, feel free to comment this question if it is unclear or you need more information! And thanks!)
Edit (1):
Well, thanks for your all replies! The intuition is correct but that's not enough. In particular, there is no an induced bijection such that each indexes of the natural mapping should be the same. For example, suppose I have (from the same sets as before) the two permutations $p_1 = (abc)$ and $q_1 = (xzy)$. I want the pair $(p_1,q_1)$ in my $Y$ but I'd like to exclude all of the possible other pairs that have the same correspondence, e.g., $p_2 = (bac)$ and $q_2 = (zxy)$.
Edit (2):
Here are the $Y$ sets for each trivial case $n=1,2,3$.
For $n = 1$, $A = \{a\}$, $B = \{x\}$, thus we have $Y = \{(a,x)\}$.
For $n = 2$, $A = \{a,b\}$, $B = \{x,y\}$, thus we have $Y = \{(ab,xy), (ab,yx)\}$.
For $n = 3$, $A = \{a,b,c\}$, $B = \{x,y,z\}$, thus we have $Y = \{(abc, xyz), (abc, xzy), (abc,zxy), (abc,zyx), (abc,yxz), (abc,yzx)\}$.
Enumerating these examples, I'm starting think that the $n!$ solution is right but I'm still not sure.
First, let me see if I understood correctly:
Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ are two sets of the same cardinality $n$. Denote by $S_A$ the symmetric group in $A$, that is, the group of all possible bijections from $A$ to $A$. Similarly, define $S_B$ for $B$.
Consider now the group $X=S_A\times S_B$. Given $(p,q)\in X$, we define the "induced bijection $\sigma_{pq}$" from $A$ to $B$ given by $\sigma_{pq}(p(a_i))=q(b_i)$.
Notice that in the case that $A=\{a_1:=a,a_2:=b,a_3:=c\},B=\{b_1:=x,b_2:=y,b_3:=z\}$, and the permutations $p=(cab)=(a_3a_1a_2)$ and $q=(zxy)=(b_3b_1b_2)$ you will have the "correspondence" (induced bijection) $\sigma_{pq}:A\to B$ sending $a_3\mapsto b_3,a_1\mapsto b_1,a_2\mapsto b_2$. Which corresponds to the function from $A$ to $B$ that sends each $a_i$ to $b_i$.
Then, you are saying that two pairs $(p,q),(p',q')$ are equivalent if $\sigma_{pq}=\sigma_{p'q'}$, and you ask for the cardinality of a maximal subset $Y\subseteq X$ such that $Y$ does not contain equivalent pairs.
Is this interpretation correct?
If it is correct, notice that this relation defines an equivalence relation on the set $X$.
Consider the natural bijection $\phi_A$ between $A=\{a_1,\ldots,a_n\}$ and $\{1,\ldots,n\}$ given by $\phi_A(a_i)=i$, and similarly define $\phi_B$.
Then, given $p\in S_A$ define $\tilde{p}:\{1,\ldots,n\}\to\{1,\ldots,n\}$ by doing $\tilde{p}(i)=\phi_A(p(a_i))$. This might look technical, but is only the translation of the bijection $p$ when we only care about the indices. the same process can be done in $S_B$.
Now, notice that $\sigma_{pq}$ is completely determined by the bijection $\tilde{q}\circ\tilde{p}^{-1}$ (which tells you how you are assigning the indices), and two pairs $(p,q),(p',q')\in X$ are equivalent if and only if
\begin{align*} \sigma_{pq}=\sigma_{p'q'}\Leftrightarrow \tilde{q}\circ\tilde{p}^{-1}=\tilde{q'}\circ\tilde{p'}^{-1}\Leftrightarrow \tilde{q'}=\tilde{q}\circ \tilde{p}^{-1}\circ \tilde{p'}. \end{align*}
This last equivalence shows that for each pair $(p,q)\in X$, there are exactly $|S_A|$ pairs that are equivalent to it (because we can choose $p'$ freely, but then $q'$ is completely determined)
Therefore, a maximal subset $Y\subseteq X$ which does not contain equivalent pairs is simply a set of representatives of the equivalence relation given above, and since all classes have the same number of elements, we have that
$$|Y|=\dfrac{\text{size of $X$}}{\text{size of an equivalence class}}=\dfrac{|S_A\times S_B|}{|S_A|}=|S_B|=n!$$