Let's difine a set $U=\{u_1, u_2,\dotsc, u_n\}$, with cardinality $|U|=n$, and a collection of sets of permutations or $n$-tuples of length $n$ each: $O=\{o_1, o_2, \dotsc, o_k\}$ with cardinality $|O|=k$. For instance for an element $o_1 \in O =\{u_4, u_1, u_7, \dotsc, u_n \}$.

Then I need to define an index set of positions of each element in $U$, in all $O$ orders but I'm not sure how. Example: for one element in $u_1 \in U$, the position of $u_1$ in $o_1$ is $p_1=2$, the position of $u_1$ in $o_2$ is $p_2=3$, the position of $u_1$ in $o_3$ is $p_3=3$, and so on until the last element $o_k \in O$. This will yield a index set of $u_1$ of size $k$, an example: $R_{u{_1}}=\{p_1, p_2, p_3, \dots, p_k\}=\{2,3,3, \dots, p_k\}$.

Finally I want to formulate with good notation an average $\sum R_{u_1}=(p_1 + p_2 + p_3 + \dots p_k)/k $, of this index set for all $u \in U$.

How do I express this procedure with a correct notation?

  • $\begingroup$ This is confusing, but let me try to understand. You have a set with $n$ elements, $U$. You are considering all $n!$ possible orderings of this set, $O$. For each element $u\in U$, you want to find its average index in the order, $\frac1{n!}\sum_{o\in O}(\text{index of $u$ in $o$})$. Correct? $\endgroup$ – Mike Earnest Feb 7 at 17:51
  • $\begingroup$ No, this is not what I mean. $O$ is not all the permutations $n!$, is only 'some' permutations, I think is clearer if I say, k-tuples of length $n$?. For each element in $U$, I want to get the average of positions in all sets $o_k \in O$. An example is, $U=\{u_1, u_2, u_3 \}$; $O=\{o_1, o_2, \dots, o_n \}$ are n-tuples of length $3$, Let's define only 2, $o_1=\{u_2, u_1, u_3 \}$ and $o_1=\{u_1, u_3, u_2 \}$. Then the index function that I'm looking should map elements of $U$, for instance $u_1$, in $O$, e.g., $R_{u_{1}}=\{2,1\} $, $R_{u_{2}}=\{1,3\} $ and $R_{u_{3}}=\{3,2\} $. $\endgroup$ – Mario GS Feb 7 at 18:16

For each permutation $o_i\in O$ consider a standard permutation $\sigma_i$ of the set $\{1,\dots,n\}$ such that $o_i=\{u_{\sigma_i(1)}, u_{\sigma_i(2)},\dots, u_{\sigma_i(n)}\}$. For instance, if $o_1 \in O =\{u_4, u_1, u_7, \dotsc, u_n \}$ then $\sigma_1=\{4, 1, 7, \dotsc, n\}$. Then a position $p_i$ of an element $u_j\in U$ in $o_i$ satisfies $u_{\sigma_i(p_i)}=u_j$, that is $j=\sigma_i(p_i)$ and $p_i=\sigma^{-1}_i(j)$, so $\sum R_{u_j}=\tfrac 1k\sum \sigma_i^{-1}(j)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.