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}$.

 A: Let us consider the general case with $n$ ones and $n$ zeroes.
We have to count the total number of runs $a_n$ in all the $\binom{2n}{n}$ sequences.
For $i=1,\dots,2n-1$, the space between the $i$th digit and the $(i+1)$th digit marks the end of a run in $2\binom{2n-2}{n-1}$ cases (note that it does not depend on $i$). The space on the right side of the $2n$-th digit marks the end of the last run for all the $\binom{2n}{n}$ sequences. Since each run has a space on its right side, counting the runs is equivalent to count such spaces, that is
$$a_n=2\binom{2n-2}{n-1}\cdot (2n-1)+\binom{2n}{n}=(n+1)\binom{2n}{n}.$$
For $n=2019$ we find that
$$a_{2019}=2020\binom{2\cdot 2019}{2019}=4040\binom{2\cdot 2019-1}{2018}=4040
\binom{4037}{2018}.$$
A: 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}$.
A: We prove that a $2n$-letter-long sequence with $n$ zeros and ones each has $n+1$ continuous runs in average. More precisely, we prove that the following construction is bijective:
$$
\begin{Bmatrix}\text{sequence starts with $1$}\\\text{with $m$ continuous runs} \end{Bmatrix} \xrightarrow{F} \begin{Bmatrix}\text{sequence starts with $1$}\\\text{with $2n + 2 - m$ continuous runs} \end{Bmatrix}.
$$
To abbreviate, let $S_m := \{\text{sequences with $m$ continuous runs}\}$. Let $\chi \in S_m$.
We define a function $g(\chi) = (\chi_1, \chi_0)$, where
$$
\begin{aligned}
\text{$\chi_1$ is a sequence with $n$ letters}, &\text{ the $i$-th letter is C if the $i$-th $1$ follows with a $0$}\\
&\text{ the $i$-th letter is N if the $i$-th $1$ follows with a $1$ or is at the end;}\\
\text{$\chi_0$ is a sequence with $n$ letters}, &\text{ the $i$-th letter is C if the $i$-th $0$ follows with a $1$}\\
&\text{ the $i$-th letter is N if the $i$-th $0$ follows with a $0$ or is at the end.}
\end{aligned}
$$
For instance, if $\chi = 11001001$, then $(\chi_1, \chi_0)= (\text{NCCN, NCNC})$. Also, we denote $\overline{\chi_1}$ to be the sequence where all N is changed to C and all C is changed to N. So in the example above, $\overline{\chi_1} = \text{CNNC}$.
Show that the function constructed as $F(\chi) = g^{-1}(\overline{\chi_0}, \overline{\chi_1})$ work, where $g^{-1}$ is the "inverse", or "reconstruction" function of $g$.
