# 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!

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

• I don't know what your 'simple calculation' would be (though I haven't had coffee yet), but more importantly, I don't think $\sum_{k=2}^{2018}a_k$ is the value you want to compute. I understood the question as asking to add up all the individual runs. So a lot of $1$'s, a lot of $11$'s, a lot of $111$'s, etc, and finally about $2020$ runs of $111\ldots111$ (consisting of $2019$ ones). Aug 27, 2019 at 10:03
• It appears that the result is $$(2n+2)\binom{2n-1}{n-1}=(n+1)\binom{2n}{n}$$in general for $n$ ones/zeroes by calculating the first few terms. Aug 27, 2019 at 10:42
• It's unclear what "the sum of all continuous runs" is. Aug 29, 2019 at 14:31
• Ok then. Then there is two questions in this problem Aug 30, 2019 at 5:41

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

• The question seems to ask for the sum of all runs, not the number of runs. Aug 29, 2019 at 11:29
• I am very confused sorry, but I really don't what are you saying about. Aug 29, 2019 at 11:31
• @IsaacYIUMathStudio I edited my answer. Any question? Aug 29, 2019 at 11:59
• @RobertZ I am sorry that you are saying right, so we need to calculate again. Aug 29, 2019 at 12:18
• @IsaacYIUMathStudio I think your original interpretation was the correct one. Otherwise, there would be no point in "counting the continuous runs" as the question says. I think it should be interpreted as the "sum of the numbers of continuous runs" for all admissible sequences. Aug 29, 2019 at 12:22

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

• Since the question gives the number $7$ for the "number of continuous runs" in the string "$011001010$", that is the interpretation I used.
– robjohn
Aug 29, 2019 at 19:45

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