2

I am interested in the set of all permutations between two sets of the same cardinality. For example, all mappings (6 of them in this case) from (1,2,3) to (5,6,7). Does such a set of permutations have a name or established properties? I am not interested in counting, but relationships between these types of sets, like unions, intersections, and decompositions.

Asaf Karagila
  • 393,674
user3433489
  • 394
  • Yes — the word is "permutation." A permutation is a bijection from a set to itself. The set of permutations on $n$ objects is denoted $S_n$. This group $S_n$ is the symmetric group on $n$ "letters." – pancini Aug 06 '23 at 01:37
  • If $|A|=|B|$ then the permutations of $A$ are in one-to-one correspondence with the bijections $A\to B$. The correspondence is $\sigma\mapsto\phi\circ\sigma$, where $\phi$ is some fixed bijection $A\to B$. In other words, imagine renaming the elements of $B$ so they match the names of the elements of $A$; now you're just studying permutations of $A$. – Karl Aug 06 '23 at 01:59
  • 1
    Thank you for the comments and answers. I apologize for the confused question. I'm not interested in all permutations of a size-n alphabet, but all permutations that satisfy certain constraints, like for {1,2,3,4}, all permutations that map {1,3} to {2,4} and map {2,4} to {1,3}, for a total of 4 individual permutations. Does this subset of $S_n$ have a name, and how do I write it down compactly? I know how to write down a single permutation, but not a set like this. – user3433489 Aug 06 '23 at 02:28

3 Answers3

4

Your notion of permutation is somewhat confused. A permutation is a bijection from a set to itself, which therefore preserves cardinality. You are simply talking about permutations, or equivalently, about bijections between sets of the same cardinality.

These permutations are studied in group theory, and are one of the most fundamental and important parts of group theory. If you have a set of these permutations which is closed, as in composing two of them in the set returns a third still in the set, then that set is a group under composition.

In fact, every finite group is isomorphic (loosely meaning the same) to a permutation group.

So if you’re interested in these, study group theory. Chapter 2 of Topics in Algebra by Herstein is a good place to learn all the basics of group theory, but you could also find a book which is more about permutation groups specifically.

Malady
  • 941
  • 1
  • 10
  • Thank you for explaining. I understand how to write down a single permutation, but confused about writing down collections, say: the set of permutations of {1,2,3,4} where all permutations of {1,3} are mapped to all permutations of {2,4}, and all permutations of {2,4} are mapped to {1,3}, for example. What's the compact way to write that? – user3433489 Aug 06 '23 at 02:11
  • Again, you can talk about permutations of one set, or bijections between two sets. There is no notion of “permutation between sets.” I’m not sure what you’re asking exactly. – Malady Aug 06 '23 at 02:48
2

The first thing to note is that a bijection from $(1,2,3)$ to $(5,6,7)$ is not a permutation.

A permutation is a bijection from a set to itself. For example, take the set $\mathbb{N}_3=\{1,2,3\}$ and consider the bijection $\phi:\mathbb{N}_3\rightarrow\mathbb{N}_3$ defined as $\phi(1)=3,\phi(2)=1,\phi(3)=2$. This would be a permutation. As you said, there are six possible permutations, the set of which is denoted $S_3$. For the set $\mathbb{N}_k=\{1,2,...,k\}$ where $k$ is a natural number, the set of permutations is denoted $S_k$.

If you know abstract algebra, the set $S_k$ is a group under composition called the $\textit{symmetric group on k letters}$.

X Stanton
  • 419
2

All permutations that satisfy certain constraints, like for {1,2,3,4}, all permutations that map {1,3} to {2,4} and map {2,4} to {1,3}, for a total of 4 individual permutations

If I understand your comment correctly, it looks like you are looking for something called Permutations with restricted positions, and perhaps also Rook Polynomials. A quick introduction to these is given in chapter 2 of the second edition of the book Enumerative Combinatorics, by Richard P. Stanley.

You can imagine a permutation as a way of placing non-attacking rooks on an $n \times n$ chessboard. Then you can specify a subset $B$ of that board in which you are allowed to place your rooks. The number $r_k$ is the number of ways of placing $k$ non-attacking rooks on $B$.

In that language, your $n$ would be $4$ and your board $B$ would be

$B = \{(1,2), (3,2), (1,4), (2,4), (2,1), (2,3), (4, 1), (4, 3)\}$.

What you have computed is $r_4 = 4$.

Gunnar Sveinsson
  • 574