Let $n$ and $k$ be natural numbers. I will consider North-East lattice paths (NE-paths) from $(0,0)$ to $(n,n)$ and encode these as strings of length $2n$ with letters $\mathsf{N}$ and $\mathsf{E}$. A peak of such a lattice path $\mathsf{P} = \mathsf{x_1x_2\dots x_{2n}}$ is an index $i$ such that $\mathsf{x_i x_{i+1}}=\mathsf{NE}$. The major index of $P$ is the sum of the peaks of $\mathsf{P}$. As an example, the NE-path $\mathsf{P} = \mathsf{ENNENEEENENN}$ has peaks at indices $3,5$ and $9$ and hence $\text{maj}(\mathsf{P})=3+5+9=17$. I have two questions regarding these paths.

  1. From this OEIS-entry, I understand that the number NE-paths from $(0,0)$ to $(n,n)$ with exactly $k$ peaks is equal to $\binom{n}{k}^2$. Does someone know a proof or a reference for this?
  2. I suspect that the $\text{maj}$-generating polynomial over this set of paths has the following nice closed form expression: $$\sum_\mathsf{P}q^{\text{maj}(\mathsf{P})}=q^{k^2}\begin{bmatrix} n\\ k \end{bmatrix}_q^2.$$ Here, the sum is taken over all NE-lattice paths from $(0,0)$ to $(n,n)$ with exactly $k$ peaks. I feel like this is a nice enough formula that it should be mentioned somewhere in the litterature but I have not managed to find it anywhere. Does someone know a reference for this?
  • 3
    $\begingroup$ 1. This is equivalent to Exercise 3 (a) in UMN Fall 2018 Math 5705 midterm #3, since you can encode NE-paths from $\left(0,0\right)$ to $\left(n,n\right)$ as $2n$-tuples with entries in $\left\{0,1\right\}$ having exactly $n$ $1$-positions (just replacing $N$ and $E$ by $1$ and $0$, respectively). $\endgroup$ – darij grinberg Nov 15 '19 at 23:11
  • 1
    $\begingroup$ For 1, the paths with $k$ peaks are in an one-to-one correspondence with the pairs of subsets $X, Y\subset [n]$ with $|X|=|Y|=k$. To see this, just let $X$ be the set of $x$-coordinates of the peaks in a path, $Y$ be the set of their $y$-coordinates. So, the total number of paths with $k$ peaks is $\binom{n}{k}^2$. $\endgroup$ – Max Alekseyev Nov 15 '19 at 23:30

The formula in 2 is a very special case of a result of Richard Stanley's, though it certainly could be older. (I wouldn't be surprised if it can be found in MacMahon's work.) See, e.g., my paper A historical survey of P-partitions, section 7.2, for references. Just in case the connection isn't clear, your problem is equivalent to counting shuffles of the words $00\cdots 0$ and $11\cdots1$, both of length $n$, with $k$ descents, by major index. Stanley's formula counts shuffles of two arbitrary (but disjoint) permutations with a given number of descents by major index.


Imagine that you lay out the N (0) and E (1) moves as follows ($n=4$ shown): $$0000$$ $$1111$$ As you go along the path, color $\color{red}{red}$ the ones you have used, so that after reading either 001, 010, or 100 you have: $${\color{red}{00}}00$$ $${\color{red}1}111$$ Then you have to choose after which 0s to switch to 1s, and which 1s to switch to 0s, for a total of $\binom{n}{k}^2$ ways.


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.