3
$\begingroup$

Consider the permutation group $\mathfrak{S}_n$ on $n$ letters $\{1,2,\dots,n\}$. Let $\iota=(1,2,3,\dots,n)\in\mathfrak{S}_n$ be the identity permutation in a $1$-line notation. Given $\pi, \rho\in\mathfrak{S}_n$ define the dot product $\pi\cdot\rho=\pi_1\rho_1+\cdots+\pi_n\rho_n$.

The $q$-factorial is given by $[n]!_q=\prod_{k=1}^n(1+q+\cdots+q^{k-1})$. Denote $D=\frac{d}{dq}$ to be the derivative evaluated at $q=1$. The following is a fact $$\sum_{\pi\in\mathfrak{S}_n}\pi\cdot\iota=\frac{(n+1)!}2\binom{n+1}2=D\,[n+1]!_q.$$

Consider the lexicographic ordering on $\mathfrak{S}_n$ for $i=1$ through $n!$. For example, if $n=3$ then write (in order) $$\mathfrak{S}_3=\{\pi^{(1)},\pi^{(2)},\pi^{(3)},\pi^{(4)},\pi^{(5)},\pi^{(6)}\} =\{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\}.$$ Denote $\eta=(\frac11,\frac12,\frac13,\cdots,\frac1n)$ and let $R(n)$ be the number of runs of length $1$ in all permutations in $\mathfrak{S}_n$ (see OEIS A097900).

QUESTION 1. Is this true? For $n\geq2$, we have $$\sum_{i=1}^{n!}(-1)^i\,(\pi^{(i)}\cdot\eta)=\frac{(n-2)!(n+1)}6.$$

QUESTION 2. Is this true? For $n\geq5$, we have $$\frac1{n-2}\sum_{i=1}^{n!}(-1)^i\,(\pi^{(i)}\cdot\eta)=R(n-3).$$

$\endgroup$
1
  • $\begingroup$ Q2 follows from Q1 and the formula $R(n)=n!\cdot (n+4)/6$ given in the OEIS. $\endgroup$ Commented Jul 15, 2022 at 3:13

1 Answer 1

5
$\begingroup$

Question 1. All entries except for the last $2$ positions remain constant in blocks of even size and, therefore, contribute $0$ to the signed sum. Now consider the last $2$ entries. Each pair of values $(a,b)$, where $1\le a<b\le n$, comes in consecutive pairs $\pi^{(2j-1)}=(\dots,a,b)$ and $\pi^{(2j)}=(\dots,b,a)$, for some $1\le j\le n!/2$. The net contribution from (the last $2$ entries of) this pair is, therefore, $$ -\left(\frac{1}{n-1}\cdot a + \frac{1}{n}\cdot b\right) + \left(\frac{1}{n-1}\cdot b + \frac{1}{n}\cdot a\right)= \frac{1}{n(n-1)}\cdot(b-a). $$ Each such pair of values $(a,b)$, $a<b$, occurs in the last $2$ positions of $(n-2)!$ permutations. Each difference $k=b-a$ occurs for $n-k$ pairs $(a,b)$, $a<b$. Therefore, the signed sum in question is equal to $$ \frac{1}{n(n-1)}(n-2)!\sum_{k=1}^{n-1}{k(n-k)}=\frac{1}{n(n-1)}(n-2)!\binom{n+1}{3}=\frac{(n-2)!(n+1)}{6} $$

Update: In general, by the same argument, given any vector $\eta=(\eta_1,\dots,\eta_n)$, the signed sum in question is equal to $$ \frac{(n+1)!}{6}(\eta_{n-1}-\eta_n). $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .