# How to define the average of index set of an element in a collection of sets?

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?

• 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? – Mike Earnest Feb 7 at 17:51
• 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\}$. – 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)$$.