I have a question regarding the permutation of sets and it is:
Problem: let the sample space $X$ be the set of permutations of $\{1,2,3,4,5\}$, the permutation $\{n_1,n_2,n_3,n_4,n_5\}$ represents the object allocation where for $i,j\in \{1,2,3,4,5\}$ we have $n_i=j$ if person $i$ receives the object by person $j$. Furthermore $i\in \{1,2,3,4,5\}$. If we define the events:
$$A_i=\{(n_1,n_2,n_3,n_4,n_5)\in X\space |\space n_i=i\}$$
My confusions: I do not understand how to list these elements under the defined set of element characteristics this set has for instance, in the sample space $X$, can $n_1=1, n_2=2,n_3=3,n_4=4, n_5=5?$
If not then the values $n_1$, $n_2$,… can take are $n_1=2,3,4,5; n_2=1,3,4,5; …$ etc. So one possible element of the sample space is $(2,3,4,5,1)\in X?$.
But in the set $A_i,$ now there is a new condition which is $n_i=i$, that means the set $A_1=\{(1,1,1,1,1)\}?$. I am alittle confused on the definition of $n_i=i$ in the set $A_i,$ and how many elements $A_1, A_2,…,A_5$ contains. Can anyone help me explain or find the elements of the set $A_i$, or just an example for$ A_1$ and $A_2?$ I would appreciate it.
Best Answer
Using the definition of a permutation as a bijective function from a set to itself (rather than related definition of strings of characters each character being used once, etc...) we have that $A_1$ is the set of permutations of $\{1,2,3,4,5\}$ such that $1$ is mapped to $1$.
Equivalently, using the definition of permutations as strings of characters instead, $A_1$ is the set of permutations of $\{1,2,3,4,5\}$ such that $1$ is in the first position.
This includes but is not limited to $12345, 13524, 15243,\dots$ and does not include things like $23451$ or $54321$ since $1$ is not in the first position and further does not include things like $11111$ or $67890$ since these are not permutations of $\{1,2,3,4,5\}$ (the first fails to be a permutation since each character is only allowed to be used exactly once and the second failed because the characters used are not from the correct base set. equivalently, the first wasn't bijective and the second had the wrong codomain).
It is worth talking about then things like $A_1\cap A_2$ which are those permutations who simultaneously have the first and second terms as fixed points... containing things like $12345, 12543, 12453,\dots$, the first position necessarily being a $1$ and the second position necessarily being a $2$.
It is also worth looking at $A_1^c$, the set of permutations such that $1$ is not a fixed point.
Finally, of considerable importance is the set $A_1^c\cap A_2^c\cap A_3^c\cap A_4^c\cap A_5^c$, the set of permutations on $\{1,2,3,4,5\}$ such that none of the elements are fixed points. We call a permutation with no fixed points a derangement.
As for counting these, for $|A_1|, |A_1\cap A_2|\dots$ approach directly with rule of product like usual. For those positions whose values are not forced, pick what element appears in that position and take note of how many options you had given earlier such selections. You have that $|A_1|=4!$ that $|A_1\cap A_2|=3!$ and so on.
These observations coupled with inclusion-exclusion will then even allow you to calculate the number of derangements, something I leave to you to finish on your own or to read about in the linked article. I rather strongly suspect that calculating the number of derangements may even be a later part of the current question you are working on or a question to be asked very soon after completing this one since they are so closely related.