# Counting the number of “distinct” permutations of two sets?

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.

• There several possibilities for $Y$. One of them is $\{\pi\}\times S_B$ where $\pi$ is an arbitrary fixed element of $S_A$. – drhab Apr 26 '16 at 13:30
• @drhab thanks! Ofc that is exact, but to fix an element is not enough. Suppose we build $Y$ by fixing each time an element from $S_A$: at the first iteration, if we fix {$\pi$}, I have a partial $Y^{'}$ that has cardinality equals to $|S_B|$; what about the next iterations? I can't see how I can establish which will be the cardinality a priori when I add a new element (thus I enumerate all of the possible pairs for that element). Plus, which are other possibilities for $Y$? – Finalfire Apr 26 '16 at 13:47
• @Finalfire All possible $Y$ can be obtained as follows: Pick an arbitrary bijection $f\colon A\to B$. This induces a homomorphism $\phi\colon S_A\to S_B$, $\sigma\mapsto f\circ \sigma\circ f^{-1}$. Note that by this $(p,q)$ is equivalent to $(\sigma\circ p, \phi(\sigma)\circ q)$. Now pick an arbitrary map $g\colon S_A\to S_A$. Let $Y=Y_g=\{\,(g(p)\circ p,\phi(p))\mid p\in S_A\,\}$. - Hence there are $n!^{n!}$ possible $Y$ – Hagen von Eitzen Apr 26 '16 at 14:42
• @HagenvonEitzen hey, thanks for the reply! This makes sense, but I can't see if it is right. In particular, let's take my example, where $|A|=|B|=3$, thus the cardinality of the set $X=S_A \times S_B$ containing all the pairs of possible permutations is $3!*3!=36$ and is waaay smaller than your result. Anyway I think you're reporting the way of creating Y? – Finalfire Apr 26 '16 at 14:58

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

• Hey there! Thanks for your reply, so exhaustive! The interpretation is correct but it is not enough! In particular, here we assume that the bijection exists but this is only a subset of the possible correspondences, e.g., I could have $(abc)$ and $(xzy)$ and I'd like having this pair in my $Y$ and excluding all of the other equivalent pairs, where the equivalence is defined by the bijection not restricted on the same indexes. I edited the question, maybe is well defined than this comment! – Finalfire Apr 26 '16 at 14:39

Elements of $S_A$ can be looked at as bijections $p:\{1,\dots,n\}\to A$ where $n$ denotes the cardinality of $A$.

Likewise elements of $S_B$ can be looked at as bijections $p:\{1,\dots,n\}\to B$.

Every pair $\langle p_A,p_B\rangle$ induces a bijection $A\to B$ prescribed by $p_A(i)\to p_B(i)$ for $i=1,\dots,n$.

It seems you want $Y\subset X$ to be a set such that the bijections induced by its elements - all of the form $\langle p_A,p_B\rangle$ - are all distinct.

Then it can have at most $n!$ elements. This because there are $n!$ bijections $A\to B$.

• Hey there! Thanks for your reply, so exhaustive! The interpretation is correct but it is not enough! In particular, here we assume that the bijection exists but this is only a subset of the possible correspondences, e.g., I could have $(abc)$ and $(xzy)$ and I'd like having this pair in my $Y$ and excluding all of the other equivalent pairs, where the equivalence is defined by the bijection not restricted on the same indexes. I edited the question, maybe is well defined than this comment! – Finalfire Apr 26 '16 at 14:39
• Could you give me the cardinality of $Y$ in the trivial cases $n=1,2,3$? The cases are small so you can find it by brute force. A look at these results might give me a better view on what you are after. – drhab Apr 26 '16 at 16:31
• I just edited the question for you! – Finalfire Apr 27 '16 at 7:43
• You found the cardinalities $1=1!$, $2=2!$ and $6=3!$. Doesn't that strike you? Exactly what the answers to your question "predict". Under fixed $a,b,c$ the permutations of $x,y,z$ arise. Corresponding with my first comment to your question. I have the impression that my interpretation is correct and that in the general case the cardinality of a maximal set $Y$ having the properties you mention is simply $n!$. – drhab Apr 27 '16 at 7:56
• In fact I was just wondering the same thing and reading again your answer it seems right! Thank you! @drhab – Finalfire Apr 27 '16 at 8:11