Rotation of sequences

249 Views Asked by At

(a) Show that for any sequence $(r_1,r_2,...,r_{n+k})\in \mathbb{N}^{n+k}$ such that $\sum r_i=n$, exactly $k$ of its rotations $(s_1,s_2,...,s_{n+k})=(r_{l+1},...,r_{n+k},r_1,...,r_l)$ satisfy $$s_1+s_2+...+s_i+k>i$$ for all $0\leq i<n+k.$

(b) show that $$\frac{k}{n+k}\sum_{r_1+r_2+....+r_{n+k}=n}e_{r_1}...e_{r_{n+k}}=\sum_{\lambda \subseteq (n+k-2,...,k-1)}\prod_{i=0}^{n+k-1}e_{\alpha_i(\lambda)}$$

where $\lambda$ ranges over all partitions (weakly decreasing sequences of positive integers) whose diagram (put $\lambda_i$ cells in row $i$ left justified) fit inside that of $(n+k-2,...,k-1)$ and $\alpha_i(\lambda)$ is the number of parts of λ that are equal to $i$, with $\alpha_0(\lambda)$ defined so that $\sum_{i}\alpha_i(\lambda) = n$.

My Idea: I tried to use induction on $n$ for part $a$. The case $n=1$ is clear. I realized the fact that $S_{n+k}$ must equal to $0$. Suppose that we want to show the case for $n+1$ and we assume that for $n$ there exist exactly $k$ rotations. I tried to remove $1$ from one of nonzero numbers and remove a zero number from the sequence. But I could not get the result.

For part (b) I also tried induction but it did not work

1

There are 1 best solutions below

2
On BEST ANSWER

Consider the modified sequence defined by $t_i=r_i-1$. All of its elements are integers which are at least $-1$ and whose total sum is $-k$, and you want to prove there are exactly $k$ rotations whose partial sums are all greater than $-k$.

We induct on $n$, the claim being obvious when $n=0$. If $n\ge 1$, then some entry in the list is nonnegative (because there are more than $k$ terms suming to $-k$). Let $a$ be a nonnegative entry of the list, and rotate the list to begin with $a$. Call the rotated list $u_1,u_2,\dots,u_{n+k}$, with $u_1=a$.

Let $s_i=u_1+u_2+\dots+u_i$. Note that

  • $s_1=a\ge 0$.

  • $s_{n+k}=-k$.

  • As $s_i$ moves from $s_1=a$ to $s_{n+k}=-k$, it only drops in steps of at most $-1$.

This means that $s_i$ must attain every value between $a$ and $-k$. In particular, there is a partial sum equal to $0$. Let $l$ be the smallest index for which $s_l=0$, so in the sublist $(u_1,u_2,\dots,u_l)$, all partial sums are positive except for the whole sum which is negative.

I claim that when counting rotations of the original list $(t_1,\dots,t_{n+k})$ whose partial sums are all at least $-k$, none of the entries $(u_1,\dots,u_l)$ can occur at the end. If $u_j$ occurred at the end, we would have this situation: $$ (\underbrace{u_{j+1},u_{j+2},\dots,u_l}_{\text{sum is $\le 0$}}, \;\underbrace{u_{l+1},u_{l+2},\dots,u_{n+k}}_{\text{sum is $-k$}}, \;\underbrace{u_{1},u_{2},\dots,u_{j}}_{\text{sum is $\ge 0$}},) $$ but then the partial sum $u_{j+1},u_{j+2},\dots,u_{n+k}$ would be less than or equal to $-k$.

Now consider what happens when you delete $(u_1,\dots,u_l)$ from the list. What remains is a list of fewer integers which still sum to $-k$. By induction, exactly $k$ rotations of this list have all partial sums greater than $-k$. Furthermore, re-inserting $(u_1,\dots,u_l)$ to the immediate left of $u_{l+1}$ will preserve this property (why?). Therefore, exactly $k$ rotations of the original list have all partial sums greater than $-k$.