Find the sum of the number of all continuous runs of all possible sequences with $2019$ ones and $2019$ zeros

Question

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

Answer 1

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

Answer 2

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

Answer 3

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