# NE-Lattice paths from $(0,0)$ to $(n,n)$ with $k$ peaks

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?
• 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). – darij grinberg Nov 15 '19 at 23:11
• 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$. – 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.