Dyck paths with $k$ peaks

There are $n$ $1$'s and $n$ $0$'s. We have to arrange them in a row such that at no position in this row the number of $0$'s from the beginning exceed the number of $1$'s from the beginning. Also the number of occasions when a $1$ is immediately followed by a $0$ should be exactly $k$. In how many ways can they be arranged?

Solution 1:

Let the number of paths be $f(n,k)$; by actual computation we find the following values for $f(n,k)$ for $1\le k\le n\le 5$:

$$\begin{array}{l|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&1&1\\ 3&1&3&1\\ 4&1&6&6&1\\ 5&1&10&20&10&1 \end{array}$$

Looking this up in OEIS, we find that it appears to be OEIS A$001263$, the triangle of Narayana numbers. This is confirmed by the second comment, which identifies $f(n,k)$ as the number of Dyck $n$-paths with exactly $k$ peaks. As noted at both links,

$$f(n,k)=\frac1n\binom{n}k\binom{n}{k-1}\;.$$

Added: If $b=b_1\ldots b_{2n}$ is such a sequence, let $b^+=1b_1\ldots b_{2n}$; $b^+$ has $n+1$ $1$’s and $n$ $0$’s, and it also has exactly $k$ instances of a $1$ immediately followed by a $0$. Clearly $b_{2n}=0$, so $$b^+=1^{p_1}0^{q_1}1^{p_2}0^{q_2}\ldots 1^{p_k}0^{q_k}$$ for some positive integers $p_i$ and $q_i$ such that $p_1+\ldots+p_k=n+1$ and $q_1+\ldots+q_k=n$. There are $\binom{n}{k-1}$ compositions of $n+1$ with $k$ parts and $\binom{n-1}{k-1}$ compositions of $n$ with $k$ parts, so there are $\binom{n}{k-1}\binom{n-1}{k-1}$ pairs of $k$-part compositions $p_1+\ldots+p_k=n+1$ and $q_1+\ldots+q_k=n$. Each pair gives rise to a sequence $1^{p_1}0^{q_1}1^{p_2}0^{q_2}\ldots 1^{p_k}0^{q_k}$, but this sequence may not be $b^+$ for any admissible $2n$-sequence $b$.

Say that two sequences of $n+1$ $1$’s and $n$ $0$’s matching the (generalized) regular expression $(1^+0^+)^k$ are equivalent if they generate the same circular sequence; this clearly is an equivalence relation, and each equivalence class has $k$ elements. (E.g., $1^{p_3}0^{q_3}1^{p_4}0^{q_4}\ldots 1^{p_k}0^{q_k}1^{p_1}0^{q_1}1^{p_2}0^{q_2}$ is equivalent to $1^{p_1}0^{q_1}1^{p_2}0^{q_2}\ldots 1^{p_k}0^{q_k}$.) Raney’s lemma [PDF, p. 5] (= Cycle Lemma [PDF] with $k=1$) implies that exactly one of the $2n+1$ circular shifts of $1^{p_1}0^{q_1}1^{p_2}0^{q_2}\ldots 1^{p_k}0^{q_k}$ is $b^+$ for some admissible $2n$-sequence $b$. (To see this, just replace each $0$ by $-1$.) It’s clear that this shift must be one of the $k$ matching the pattern $(0^+1^+)^k$, so each equivalence class contains exactly one sequence that is $b^+$ for some admissible $2n$-sequence $b$. Thus, there are $$\frac1k\binom{n}{k-1}\binom{n-1}{k-1}=\frac1n\binom{n}{k-1}\binom{n}k$$ admissible $2n$-sequences.

(This argument is my slight adaptation of Richard P. Stanley’s solution to Exercise $36$(a) of the excerpt on problems relating to Catalan numbers taken from Volume $2$ of his Enumerative Combinatorics; the excerpt and solutions can be downloaded from this page.)

Solution 2:

This argument is an expansion of my argument made for sci.math regarding the question not counting the peaks. I have kept the steps small, at the expense of the length of the derivations.

Recurrence Relation

Instead of $0$ and $1$, let's use $-1$ and $+1$.

Let us call an arrangement of $n$ '$+1$'s and $n$ '$-1$'s, with $p$ occurrences of $+1-1$ (peaks), a walk of type $n,p$. Let us also call a walk that has no negative partial sum a unilateral walk.

Let $w(n,p)$ be the number of unilateral walks of type $n,p$. Let us classify these walks by the type of their smallest initial subwalk. Those whose smallest initial subwalk is of type $k,m$ look like either like this: $$ +1-1\langle\text{a unilateral walk of type }n-1,p-1\rangle $$ or like this: $$ +1\langle\text{a unilateral walk of type }k-1,m\rangle-1\langle\text{a unilateral walk of type }n-k,p-m\rangle $$ By considering all possible types of initial subwalk, we get the following recurrence relation: $$ w(n,p)=\overbrace{\vphantom{\sum_{k=1}^n}w(n-1,p-1)}^{+1-1\langle\text{type }n-1,p-1\rangle} +\overbrace{\sum_{k=1}^n\sum_{m=1}^pw(k-1,m)w(n-k,p-m)}^{+1\langle\text{type }k-1,m\rangle-1\langle\text{type }n-k,p-m\rangle}\tag{1} $$ with the initial conditions that $w(0,0)=1$ and $w(n,0)=0$ if $n\gt0$; that is, the only walk without any peaks is the empty walk, and $w(n,p)=0$ if $p\gt n$; that is, there can't be more peaks than $+1$s.

Closed Form for the Generating Function

Note that $g(0,y)=1$ and for $n\gt0$: $$ \begin{align} g(n,y) &=\sum_{p=1}^\infty w(n,p)y^p\tag{2a}\\ &=\sum_{p=1}^\infty\left(w(n-1,p-1)+\sum_{k=1}^n\sum_{m=1}^pw(k-1,m)w(n-k,p-m)\right)y^p\tag{2b}\\ &=yg(n-1,y)+\sum_{k=1}^n\sum_{m=1}^\infty\sum_{p=m}^\infty w(k-1,m)w(n-k,p-m)y^my^{p-m}\tag{2c}\\ &=yg(n-1,y)+\sum_{k=1}^n\sum_{m=1}^\infty\sum_{p=0}^\infty w(k-1,m)w(n-k,p)y^my^p\tag{2d}\\ &=(y-1)g(n-1,y)+\sum_{k=1}^n\sum_{m=0}^\infty\sum_{p=0}^\infty w(k-1,m)w(n-k,p)y^my^p\tag{2e}\\ &=(y-1)g(n-1,y)+\sum_{k=1}^ng(k-1,y)g(n-k,y)\tag{2f} \end{align} $$ $\text{(2a)}$: create generating function on second variable
$\text{(2b)}$: use $(1)$
$\text{(2c)}$: use $\text{(2a)}$
$\text{(2d)}$: substitute $p\mapsto p+m$
$\text{(2e)}$: subtract $g(n-1,y)$ and add $k=1,m=0$ case, which adds $g(n-1,y)$
$\text{(2f)}$: use $\text{(2a)}$

Thus, $$ \begin{align} f(x,y) &=\sum_{n=0}^\infty g(n,y)x^n\tag{3a}\\ &=1+\sum_{n=1}^\infty g(n,y)x^n\tag{3b}\\[5pt] &=1+x(y-1)f(x,y)+xf(x,y)^2\tag{3c}\\[15pt] 0 &=1+(xy-x-1)f(x,y)+xf(x,y)^2\tag{3d} \end{align} $$ $\text{(3a)}$: create generating function on first variable
$\text{(3b)}$: break out the $n=0$ case
$\text{(3c)}$: use $\text{(2)}$
$\text{(3d)}$: subtract $f(x,y)$ from both sides

Applying the Quadratic Formula to $(3)$ yields $$ \begin{align} f(x,y) &=\sum_{n=0}^\infty\sum_{p=0}^nw(n,p)x^ny^p\tag{4a}\\[6pt] &=\frac{1+x(1-y)-\sqrt{(1+x(1-y))^2-4x}}{2x}\tag{4b}\\[6pt] &=\frac1{1+x(1-y)}\frac{1-\sqrt{1-\frac{4x}{(1+x(1-y))^2}}}{\frac{2x}{(1+x(1-y))^2}}\tag{4c} \end{align} $$

Closed Form for the General Term

The Binomial Theorem says $$ \frac{1-\sqrt{1-4x}}{2x}=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^k\tag{5} $$ and $$ \begin{align} \frac{x^k}{(1+x(1-y))^{2k+1}} &=\sum_{j=0}^\infty(-1)^j\binom{2k+j}{j}x^{j+k}(1-y)^j\tag{6a}\\ &=\sum_{j=0}^\infty\sum_{i=0}^j(-1)^{i+j}\binom{2k+j}{2k}\binom{j}{i}x^{j+k}y^i\tag{6b}\\ &=\sum_{i=0}^\infty\sum_{j=i}^\infty(-1)^{i+j}\binom{2k+j}{2k}\binom{j}{i}x^{j+k}y^i\tag{6c}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty(-1)^{j}\binom{2k+j+i}{2k}\binom{j+i}{i}x^{i+j+k}y^i\tag{6d} \end{align} $$ $\text{(6a)}$: binomial theorem on $(1+x(1-y))^{-2k-1}$
$\text{(6b)}$: binomial theorem on $(1-y)^j$
$\text{(6c)}$: switch order of summation
$\text{(6d)}$: substitute $j\mapsto j+i$

Therefore, $$ \begin{align} f(x,y) &=\sum_{k=0}^\infty\sum_{i=0}^\infty\sum_{j=0}^\infty\frac{(-1)^j}{k+1}\binom{2k}{k}\binom{2k+j+i}{2k}\binom{j+i}{i}x^{i+j+k}y^i\tag{7a}\\ &=\sum_{k=0}^\infty\sum_{i=0}^\infty\sum_{j=k}^\infty\frac{(-1)^{j+k}}{k+1}\binom{2k}{k}\binom{i+j+k}{2k}\binom{i+j-k}{i}x^{i+j}y^i\tag{7b}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^j\frac{(-1)^{j+k}}{k+1}\binom{2k}{k}\binom{i+j+k}{2k}\binom{i+j-k}{i}x^{i+j}y^i\tag{7c}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^j\frac{(-1)^{j+k}}{k+1}\binom{i+j}{i}\binom{i+j+k}{k}\binom{j}{k}x^{i+j}y^i\tag{7d}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^j\frac{(-1)^j}{j+1}\binom{i+j}{i}\binom{-i-j-1}{k}\binom{j+1}{k+1}x^{i+j}y^i\tag{7e}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^j\frac{(-1)^j}{j+1}\binom{i+j}{i}\binom{-i-j-1}{k}\binom{j+1}{j-k}x^{i+j}y^i\tag{7f}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\frac{(-1)^j}{j+1}\binom{i+j}{i}\binom{-i}{j}x^{i+j}y^i\tag{7g}\\ &=\sum_{i=0}^\infty\sum_{j=0}^\infty\frac1{j+1}\binom{i+j}{i}\binom{i+j-1}{j}x^{i+j}y^i\tag{7h}\\ &=\sum_{p=0}^\infty\sum_{n=p}^\infty\frac1{n-p+1}\binom{n}{p}\binom{n-1}{n-p}x^ny^p\tag{7i}\\ &=\sum_{n=0}^\infty\sum_{p=0}^n\frac1{n-p+1}\binom{n}{p}\binom{n-1}{n-p}x^ny^p\tag{7j}\\ &=1+\sum_{n=1}^\infty\sum_{p=1}^n\frac1{n-p+1}\binom{n}{p}\binom{n-1}{p-1}x^ny^p\tag{7k}\\ &=1+\sum_{n=1}^\infty\sum_{p=1}^n\color{#C00000}{\frac1{n}\binom{n}{p}\binom{n}{p-1}}x^ny^p\tag{7l}\\ \end{align} $$ $\text{(7a)}$: use $(4)$, $(5)$, and $(6)$
$\text{(7b)}$: substitute $j\mapsto j-k$
$\text{(7c)}$: switch order of summation
$\text{(7d)}$: both binomial products equal $\binom{i+j+k}{i,j-k,k,k}$
$\text{(7e)}$: $(-1)^k\binom{i+j+k}{k}=\binom{-i-j-1}{k}$ and $\frac1{k+1}\binom{j}{k}=\frac1{j+1}\binom{j+1}{k+1}$
$\text{(7f)}$: $\binom{j+1}{k+1}=\binom{j+1}{j-k}$
$\text{(7g)}$: Vandermonde Identity
$\text{(7h)}$: $(-1)^j\binom{-i}{j}=\binom{i+j-1}{j}$
$\text{(7i)}$: substitute $j\mapsto n-i$ then $i\mapsto p$
$\text{(7j)}$: switch order of summation
$\text{(7k)}$: pull out $n=0$ case, then $\binom{n-1}{n-p}=\binom{n-1}{p-1}$, then remove $p=0$ case
$\text{(7l)}$: $\binom{n-1}{p-1}=\frac{n-p+1}{n}\binom{n}{p-1}$

Thus, by equating coefficients in $(7)$, $$ w(n,p)=\frac1n\binom{n}{p}\binom{n}{p-1}\tag{8} $$

Ignoring Peaks

If we don't care to count peaks, we can sum over $p$ to get the number of unilateral walks of type $n$: $$ \begin{align} \sum_{p=1}^n\frac1n\binom{n}{p}\binom{n}{p-1} &=\sum_{p=1}^n\frac1n\binom{n}{n-p}\binom{n}{p-1}\tag{9a}\\ &=\frac1n\binom{2n}{n-1}\tag{9b}\\ &=\frac1{n+1}\binom{2n}{n}\tag{9c} \end{align} $$ $\text{(9a)}$: $\binom{n}{p}=\binom{n}{n-p}$
$\text{(9b)}$: Vandermonde Identity
$\text{(9c)}$: $\binom{2n}{n-1}=\frac{n}{n+1}\binom{2n}{n}$

where $\frac1{n+1}\binom{2n}{n}$ is the $n^\text{th}$ Catalan number.