Rewriting a sum over permutations

50 Views Asked by At

Suppose I have the set $I_{n} = \{1,...,n\}$ and $n$ formal objects $x_{1},...,x_{n}$ (you can think of these as elements of some algebra). Let me write: $$S(x_{1}\cdots x_{n}) = \frac{1}{n!}\sum_{\sigma}x_{\sigma(1)}\cdots x_{\sigma(n)}$$ where the sum ranges over all permutations $\sigma$ of the set $I_{n}$.

Now, suppose I fix $j \in I_{n}$, and I want to calculate $S(x_{1}\cdots \hat{x}_{j} \cdots x_{n})$, where the hat means to omit this entry. So, in other words, now I will sum over all permutations $\sigma \in I_{n}\setminus \{j\}$.

I want to rewrite in terms of permutations of the set $\{2,...,n\}$ instead. So I came with the following reasoning. Every permutation $\sigma$ of $I_{n}\setminus \{j\}$ is a bijection from $I_{n}\setminus\{j\}$ onto itself. There are $(n-1)!$ such bijections. Consider one such bijection $\sigma$, and its range $\{\sigma(1),...,\sigma(j-1),\sigma(j+1),...,\sigma(n)\}$. Now, define a map $T_{\sigma}$ by setting $T_{\sigma}(2) = \sigma(1)$, $T_{\sigma}(3) = \sigma(2)$,...,$T_{\sigma}(n) = \sigma(n)$. This is a bijection, so each permutation $\sigma$ gives rise to a different bijection $T_{\sigma}$ of this form. In other words, to each permutation $\sigma$ of $I_{n}\setminus \{j\}$ there corresponds a bijection $T_{\sigma}$ from $\{2,...,n\}$ to $I_{n}\setminus \{j\}$. Hence, I can write: $$S(x_{1}\cdots \hat{x}_{j}\cdots x_{n}) = \frac{1}{n!}\sum_{T_{\sigma}}x_{T_{\sigma}(2)}\cdots x_{T_{\sigma}(n)}$$ where the sum ranges over all such bijections $T_{\sigma}$.

Is this reasoning and my final formula correct? Or am I doing something wrong?

1

There are 1 best solutions below

0
On

As $T_\sigma$ is uniquely defined by $\sigma$ and vice versa, your reasoning seems correct yes.