Possible new formula for OEIS A191522

Question

The following formula (proved here):

$$\sum_{k=\lfloor \frac{n+1}{2} \rfloor}^{n}{k{k-1 \choose \lfloor \frac{n+1}{2}\rfloor - 1}} = \Big\lceil \frac{n}{2} \Big\rceil{n+1 \choose \lfloor \frac{n}{2} \rfloor}$$

counts the sum of the maximum elements of each subset of $[n]=\{1,\ldots,n\}$ with size $\lfloor (n+1)/2 \rfloor$. For example for $n=3$ there are three subsets $\{1,2\}, \{1,3\}, \{2,3\}$ and the sum of maximum values is $2+3+3=8$.

It seems to be equal to $a(n+2)$ where $a$ is OEIS A191522, "Number of valleys in all left factors of Dyck paths of length n. A valley is a (1,-1)-step followed by a (1,1)-step". For example $a(4)=3$ because the total number of valleys in $UDUD, UDUU, UUDD, UUDU, UUUD, UUUU$ is $1+1+0+1+0+0=3$, where $U=(1,1)$, $D=(1,-1)$.

OEIS does not report the above formula. Is there a way to relate it directly to the above count of valleys of Dyck paths of length $n+2$? Or is at least possible to prove that it coincides with the other proposed formulas?

Answer 1

Yes, very good observation! The right-hand side of OP's identity
\begin{align*} \color{blue}{b_n:=\Big\lceil \frac{n}{2}\Big\rceil{n+1 \choose \lfloor \frac{n}{2} \rfloor}\qquad\qquad n\geq 0}\tag{1} \end{align*} is a shifted variant of OEIS A191522.

Here we show the ordinary generating function \begin{align*} \color{blue}{B(z)}&\color{blue}{=\sum_{n=0}^{\infty}b_nz^n} \end{align*} is strongly related with the generating function stated in OEIS A191522 \begin{align*} A(z)&= \frac{2((1-z-3z^2+z^3)q-1+z+5z^2-3z^3-4z^4}{zq(1-2z-q)^2}\tag{2.1}\\ &=z^3+3z^4+8z^5+20z^6+45z^7+105z^8+224z^9+\cdots\tag{2.2} \end{align*} with $q$ a shorthand for $q(z)=\sqrt{1-4z^2}$.

We show the following is valid \begin{align*} \color{blue}{z^2B(z)=A(z)}\tag{3} \end{align*}

Representation of $b_n$: We start with a more convenient representation of $b_n$ and consider even and odd terms separately. \begin{align*} b_n=\Big\lceil \frac{n}{2}\Big\rceil{n+1 \choose \lfloor \frac{n}{2} \rfloor}&=\left\lfloor\frac{n+1}{2}\right\rfloor\binom{n+1}{\lfloor \frac{n+1}{2} \rfloor +1}\\ b_{2m}&=m\binom{2m+1}{m+1}\qquad\qquad m\geq 0\tag{4.1}\\ b_{2m-1}&=m\binom{2m}{m+1}\ \qquad\qquad m\geq 1\tag{4.2} \end{align*}

Generating function $B(z)$

The binomial coefficients $b_{2m}$ and $b_{2m-1}$ are strongly related with the Central binomial coefficients \begin{align*} \sum_{m=0}^{\infty}\binom{2m}{m}z^m=\frac{1}{\sqrt{1-4z}}\tag{5.1} \end{align*} and the Catalan numbers \begin{align*} \sum_{m=0}^{\infty}\frac{1}{m+1}\binom{2m}{m}z^m=\frac{1-\sqrt{1-4z}}{2z}.\tag{5.2} \end{align*} Since \begin{align*} \binom{2m+1}{m+1}&=\frac{2m+1}{m+1}\binom{2m}{m}=\left(2-\frac{1}{m+1}\right)\binom{2m}{m}\tag{6.1}\\ \binom{2m}{m+1}&=\frac{m}{m+1}\binom{2m}{m}=\left(1-\frac{1}{m+1}\right)\binom{2m}{m}\tag{6.2} \end{align*}

we obtain using the shorthand $q(z)=\frac{1}{\sqrt{1-4z^2}}$ as it is used in (2.1) \begin{align*} \color{blue}{B(z)}&=\sum_{n=0}^{\infty}b_nz^n\\ &=\sum_{m=0}^{\infty}b_{2m}z^{2m}+\sum_{m=1}^{\infty}b_{2m-1}z^{2m-1}\\ &=\sum_{m=0}^{\infty}m\binom{2m+1}{m+1}z^{2m}+\sum_{m=1}^{\infty}m\binom{m}{2m+1}z^{2m-1}\tag{7.1}\\ &=\frac{1}{2}z\frac{d}{dz}\left(\sum_{m=0}^{\infty}\binom{2m+1}{m+1}z^{2m}\right)+\frac{1}{2}\frac{d}{dz}\left(\sum_{m=1}^{\infty}\binom{2m}{m+1}z^{2m}\right)\tag{7.2}\\ &=\frac{1}{2}z\frac{d}{dz}\left(\frac{2}{\sqrt{1-4z^2}}-\frac{1-\sqrt{1-4z^2}}{2z^2}\right)\\ &\qquad\qquad+\frac{1}{2}\frac{d}{dz}\left(\frac{1}{\sqrt{1-4z^2}}-\frac{1-\sqrt{1-4z^2}}{2z^2}\right)\tag{7.3}\\ &=\frac{1}{2}(2z+1)\frac{d}{dz}\left(\frac{1}{\sqrt{1-4z^2}}\right)\\ &\qquad\qquad-\frac{1}{2}(z+1)\frac{d}{dz}\left(\frac{1-\sqrt{1-4z^2}}{2z^2}\right)\tag{7.4}\\ &\color{blue}{=\frac{2z(2z+1)}{q^3}-\frac{(z+1)\left(1-2z^2-q\right)}{2z^3q}}\tag{7.5}\\ &\color{blue}{=z+3z^2+8z^3+20z^4+45z^5+105z^6+224z^7+\cdots}\tag{7.6} \end{align*} and observe the coefficients in (7.6) coincide nicely with those in OEIS A191522.

Comment:

• In (7.1) we use the representation in even and odd elements from (4.1) and (4.2).

• In (7.2) we get rid of the factor $m$ by using the differentiation operator.

• In (7.3) we use the relations from (6.1) and (6.2) and take the generating functions of the central binomial coefficients (5.1) and the Catalan numbers (5.2).

• In (7.4) we collect like terms.

• In (7.5) we do the differentiation with some support from Wolfram Alpha.

• In (7.6) we expand the series again with some help of WA.

Equality $z^2B(z)=A(z)$:

Here we finally show the equality of the generating functions. We start with some transformations of $A(z)$ from (2.1) and then we also transform $B(z)$ a bit to see equality of $z^2B(z)=A(z)$.

We use the following relations with $q=\sqrt{1-4z^2}$: \begin{align*} (1-2z-q)^2&=1+4z^2+q^2-4z-2q+4qz\\ &=1+4z^2+\left(1-4z^2\right)-4z-2q+4qz\\ &=2(1-q)-4z(1-q)\\ &=2(1-q)(1-2z)\tag{8.1}\\ (1-q)(1+q)&=1-q^2=1-\left(1-4z^2\right)=4z^2\tag{8.2}\\ (1-2z)(1+2z)&=1-4z^2=q^2\tag{8.3} \end{align*}

We obtain from (2.1) \begin{align*} \color{blue}{A(z)}&= \frac{2((1-z-3z^2+z^3)q-1+z+5z^2-3z^3-4z^4}{zq(1-2z-q)^2}\\ &=\frac{(1-z-3z^2+z^3)q-1+z+5z^2-3z^3-4z^4}{q(1-q)z(1-2z)}\tag{$\to\ $(8.1)}\\ &=\frac{(1-z-3z^2+z^3)q(1+q)}{4qz^3(1-2z)}\\ &\qquad\qquad+\frac{\left(-1+z+5z^2-3z^3-4z^4\right)(1+q)}{4qz^3(1-2z)}\tag{$\to\ $(8.2)}\\ &=\frac{-1+z+4z^2-2z^3+\left(1-z-2z^2\right)q}{2qz(1-2z)}\tag{$\mathrm{simplified}$}\\ &=\frac{1}{2zq^3}\left((-1+z+4z^2-2z^3)(1+2z)\right.\\ &\qquad\qquad\quad\left.+\left(1-z-2z^2\right)(1+2z)q\right)\tag{$\to\ $(8.3)}\\ &\,\,\color{blue}{=\frac{1}{2zq^3}\left(-1-z+6z^2+6z^3-4z^4\right.}\\ &\qquad\qquad\quad\,\,\color{blue}{\left.+(1+z-4z^2-4z^3)q\right)}\tag{9.1} \end{align*} On the other hand we derive from (7.5) \begin{align*} \color{blue}{B(z)}&=\frac{2z(2z+1)}{q^3}-\frac{(z+1)\left(1-2z^2-q\right)}{2z^3q}\\ &=\frac{1}{2z^3q^3}\left(4z^4(2z+1)-(1+z)(1-2z^2-q)q^2\right)\\ &=\frac{1}{2z^3q^3}\left(4z^4(2z+1)-(1+z)(1-2z^2-q)(1-4z^2)\right)\\ &\,\,\color{blue}{=\frac{1}{2z^3q^3}\left(-1-z+6z^2+6z^3-4z^4\right.}\\ &\,\,\qquad\qquad\quad\color{blue}{\left.+(1+z-4z^2-4z^3)q\right)}\tag{9.2} \end{align*} Comparing (9.1) and (9.2) we see the claim (3) is valid.

Answer 2

It looks like it might be listed: under formulas it has
a(n) = Sum_{k>=0} k*A191521(n,k), where the formula for A191521(n,k) is given in its entry. Check for equality

Answer 3

Here are some structural considerations regarding this binomial identity. When looking at \begin{align*} \color{blue}{\sum_{k=\lfloor \frac{n+1}{2} \rfloor}^{n}{k{k-1 \choose \lfloor \frac{n+1}{2}\rfloor - 1}} = \Big\lceil \frac{n}{2} \Big\rceil{n+1 \choose \lfloor \frac{n}{2} \rfloor}}\tag{1} \end{align*} we can recall the binomial identity \begin{align*} \binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1} \end{align*} and apply it to the left-hand side of (1) to get \begin{align*} \color{blue}{k{k-1 \choose \lfloor \frac{n+1}{2}\rfloor - 1}} =\left\lfloor\frac{n+1}{2}\right\rfloor\frac{k}{\left\lfloor\frac{n+1}{2}\right\rfloor}\binom{k-1}{\lfloor \frac{n+1}{2}\rfloor - 1} \color{blue}{=\left\lfloor\frac{n+1}{2}\right\rfloor\binom{k}{\lfloor \frac{n+1}{2}\rfloor}} \end{align*} So (1) can be equivalently written as \begin{align*} \left\lfloor\frac{n+1}{2}\right\rfloor\sum_{k=\lfloor \frac{n+1}{2} \rfloor}^{n}\binom{k}{\lfloor \frac{n+1}{2}\rfloor} = \Big\lceil \frac{n}{2} \Big\rceil{n+1 \choose \lfloor \frac{n}{2} \rfloor}\tag{2} \end{align*} As @ThomasAndrews indicated in the comment section, we also have for non-negative integers \begin{align*} \left\lfloor\frac{n+1}{2}\right\rfloor=\left\lceil\frac{n}{2}\right\rceil, \end{align*} so that (2) can be simplified to \begin{align*} \sum_{k=\lfloor \frac{n+1}{2} \rfloor}^{n}\binom{k}{\lfloor \frac{n+1}{2}\rfloor} = \binom{n+1 }{\lfloor \frac{n}{2} \rfloor}\tag{3} \end{align*}

Since we also have the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ we can write (3) as \begin{align*} \color{blue}{\sum_{k=\lfloor \frac{n+1}{2} \rfloor}^{n}{\binom{k}{\lfloor \frac{n+1}{2}\rfloor}} = \binom{n+1 }{\lfloor \frac{n+1}{2} \rfloor+1}}\tag{4} \end{align*} revealing that (4) and therefore also (1) are just special cases of the Hockey-stick identity.

Notes:

• Searching for hockey-stick identity in OEIS gives 6 entries.

• When comparing (1) and (4) we see what Donald Knuth says in section 5.5 of Concrete Mathematics: Binomial coefficients are like chameleons, changing their appearance easily.