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?
Best Answer
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