Find the sum of the number of all continuous runs of all possible sequences with $2019$ ones and $2019$ zeros I recently had a test that is quite difficult because it is for selecting people to participate important mathematics competition. It has 6 questions like IMO, and the last question is pretty hard. Although I have done it, it takes me a long time. I hope someone would give me a better solution. The question is that:

For a sequence with some ones and zeros, we count the number of continuous runs of equal digits in it. For example, the sequence $011001010$ has $7$ continuous runs; $0,11,00,1,0,1,0$. Find the sum of the number of all continuous runs of all possible sequences with $2019$ ones and $2019$ zeros

That's the question. I did an answer $$4040 \begin{pmatrix} 4037 \\  2018 \end{pmatrix}$$
I think it is true that I have checked the answer in different ways. However, I hope there are faster or more elegant ways to solve this question because I use a lot of algebraic-combinatorics. I hope you guys will help me. Thank you!
Spoiler(my answer)

 Let $a_n$ be the number of the sequences with $n$ continuous runs. Obviously, $a_n \ne 0$ if and only if $n$ is a positive integer between $2$ and $4038$ inclusive. After some simple calculation, we know that: $$\text{For any positive integer }n\text{ between }2\text{ and }4038\text{ inclusive, }a_n=\begin{cases} 2{\begin{pmatrix} 2018 \\  \frac{n}{2}-1 \end{pmatrix}}^2 & \text{if }n\text{ is even}\\ 2\begin{pmatrix} 2018 \\  \frac{n-1}{2} \end{pmatrix} \begin{pmatrix} 2018 \\  \frac{n-3}{2} \end{pmatrix}& \text{if }n\text{ is odd}\end{cases}$$ However, our answer is to find the sum of all continuous runs of all possible sequence, so the answer is $\sum_{k=2}^{2018} ka_k$. After some horrible calculation, you'll get $4040 \begin{pmatrix} 4037 \\  2018 \end{pmatrix}$.


Number of Arrangements with $\boldsymbol{k}$ Runs
Using Stars and Bars, The number of ways to get a sum of $n$ with $k$ positive numbers is $\binom{n-1}{k-1}$.
The number of arrangements with $k$ runs is twice the number of ways (one starting with $0$ and one starting with $1$) to get a sum of $n$ with $\left\lfloor\frac{k+1}2\right\rfloor$ positive numbers times the number of ways to get a sum of $n$ with $\left\lfloor\frac{k}2\right\rfloor$ positive numbers.
My Interpretation of "The Sum of All Continuous Runs"
The question explicitly states that "the sequence $011001010$ has $7$ continuous runs". Here we sum the number of continuous runs for all sequences consisting of $n$ zeros and $n$ ones.
$$
\begin{align}
&\sum_{k=1}^n2(2k)\binom{n-1}{k-1}\binom{n-1}{k-1}+\sum_{k=1}^n2(2k+1)\binom{n-1}{k}\binom{n-1}{k-1}\tag1\\
&=\sum_{k=1}^n\left[4(k-1)\binom{n-1}{k-1}\binom{n-1}{k-1}+4\binom{n-1}{k-1}\binom{n-1}{k-1}\right]\tag{2a}\\
&+\sum_{k=1}^n\left[4k\binom{n-1}{k}\binom{n-1}{k-1}+2\binom{n-1}{k}\binom{n-1}{k-1}\right]\tag{2b}\\
&=\sum_{k=1}^n4(n-1)\left[\binom{n-2}{k-2}\binom{n-1}{n-k}+4\binom{n-1}{k-1}\binom{n-1}{n-k}\right]\tag{3a}\\
&+\sum_{k=1}^n\left[4(n-1)\binom{n-2}{k-1}\binom{n-1}{n-k}+2\binom{n-1}{k}\binom{n-1}{n-k}\right]\tag{3b}\\
&=4(n-1)\binom{2n-3}{n-2}+4\binom{2n-2}{n-1}+4(n-1)\binom{2n-3}{n-1}+2\binom{2n-2}{n}\tag4\\
&=2(n+1)\binom{2n-1}{n}\tag5
\end{align}
$$
Explanation:
$\phantom{\text{a}}\text{(1)}$: separate the even and odd cases
$\text{(2a)}$: $2(2k)=4(k-1)+4$
$\text{(2b)}$: $2(2k+1)=4k+2$
$\text{(3a)}$: $(k-1)\binom{n-1}{k-1}=(n-1)\binom{n-2}{k-2}$
$\text{(3b)}$: $k\binom{n-1}{k}=(n-1)\binom{n-2}{k-1}$
$\phantom{\text{a}}\text{(4)}$: Vandermonde's Identity
$\phantom{\text{a}}\text{(5)}$: put everything over $n!(n-1)!$ and simplify
Plug in $n=2019$ and we get $4040\binom{4037}{2019}$.
