9
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I would simplify that by noting $\lceil n/2\rceil=\lfloor (n+1)/2\rfloor.$ Just removes some of the duplicate expressions. $\endgroup$ Aug 11, 2023 at 22:07

3 Answers 3

3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Yes, but it's the lhs of the op's formula. The rhs seems to be new. $\endgroup$ Aug 12, 2023 at 9:37
  • 1
    $\begingroup$ @colt_browning the LHS is not this sum with $A191521$ as a formula, however one could prove that the two formulas give the same result. $\endgroup$ Aug 12, 2023 at 17:52
  • $\begingroup$ @BillyJoe oh, indeed. Please eventually submit your formulas to the OEIS, they are really nice. $\endgroup$ Aug 13, 2023 at 3:13
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Thanks. That was a lot of work. I am going to propose the formula to OEIS. May I cite you in the reference to this proof at math.stackexchange? If yes, with "epi163sqrt" or your real name? If yes for your real name, what is it? $\endgroup$ Aug 13, 2023 at 14:35
  • $\begingroup$ @BillyJoe: You are welcome. Yes, it was a bit of work and interesting to derive the somewhat complicated looking generating function. It's fine for me If you cite me in this OEIS entry. Please use my real name Markus Scheuer. Thanks! :-) $\endgroup$ Aug 13, 2023 at 14:44
  • $\begingroup$ I don't think it affects the result, but $\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}$ only for $n$ even. $\endgroup$ Aug 13, 2023 at 14:50
  • $\begingroup$ One that works is $\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}$. I don't know if it is preferable to mine. $\endgroup$ Aug 13, 2023 at 14:55
  • $\begingroup$ @BillyJoe: This was a typo. Thanks for pointing at it. It's corrected now and coincides now with my other answer. $\endgroup$ Aug 13, 2023 at 14:56
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the insight, although the aim of this question is to demonstrate the equvalence with the mentioned OEIS sequence. Admittedly, I haven't done the effort yet to work out the formulas or find a combinatorial interpretation. $\endgroup$ Aug 12, 2023 at 13:43
  • $\begingroup$ @BillyJoe: You're welcome. I've added another answer showing your nice observation is correct. $\endgroup$ Aug 12, 2023 at 22:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .