6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Inactive - Objecting Extremism Aug 27 at 10:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Foreman Aug 27 at 10:42
  • $\begingroup$ It's unclear what "the sum of all continuous runs" is. $\endgroup$ – Christian Blatter Aug 29 at 14:31
  • $\begingroup$ Ok then. Then there is two questions in this problem $\endgroup$ – Isaac YIU Math Studio Aug 30 at 5:41
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The question seems to ask for the sum of all runs, not the number of runs. $\endgroup$ – Inactive - Objecting Extremism Aug 29 at 11:29
  • $\begingroup$ I am very confused sorry, but I really don't what are you saying about. $\endgroup$ – Isaac YIU Math Studio Aug 29 at 11:31
  • $\begingroup$ @IsaacYIUMathStudio I edited my answer. Any question? $\endgroup$ – Robert Z Aug 29 at 11:59
  • $\begingroup$ @RobertZ I am sorry that you are saying right, so we need to calculate again. $\endgroup$ – Isaac YIU Math Studio Aug 29 at 12:18
  • 1
    $\begingroup$ @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. $\endgroup$ – saulspatz Aug 29 at 12:22
1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.