# Closed form expression for count of “runs” in binary sequence sharing same length, number of 1's, and location of final 1

I am struggling with the following combinatorial problem related to research I am doing.

Take a binary sequence $(y_1, y_2, \ldots, y_n)$ of length $n$ with $x$ $1$'s, where the final $1$ is in location $t_x$ (in English: $t_x$ is the time of the $x$th event). Let the number of runs of length $2$ (allowing for overlap - see examples below to make this easier to understand) be denoted by $n_{runs}$. To be more precise, $n_{runs}$ is the number of times we have that $y_{k-1} = y_k = 1, k \in \{1, 2, \ldots, n \}$ (informally, "the number of times we see $11$ in our sequence"). To deal with initialization issues when $k=1$, we assume that $y_1=1$ contributes one run to $n_{runs}$.

A couple examples to make this concrete:

(1) $(y_1, y_2, y_3) = 110$: Here, $x=2, t_x=2, n_{runs}=2, n=3$ (again observing the initialization assumption for $y_1$).

(2) $(y_1, y_2, \ldots, y_8) = 11001010$: Here, $x=4, t_x = 7, n_{runs}=2, n=8$.

(3) $(y_1, y_2, \ldots, y_5 ) = 01110$: Here, $x=3, t_x = 4, n_{runs}=2, n=5$.

(4) $(y_1, y_2, \ldots, y_5 ) = 01100$: Here, $x=2, t_x = 3, n_{runs}=1, n=5$.

I would like to know the following - fixing $n$, how many sequences share the same combination of $(x, t_x, n_{runs}, n)$? Is there a closed form expression for this? Of course, the brute force approach is to simply enumerate all sequences sharing the same $(x,t_x,n)$ statistics, then counting the runs, but it would be nice if there was some way to get this in closed form.

We can see that the number of sequences sharing the same $(x,t_x,n)$ is ${ t_x-1 \choose x-1 }$ for all cases within the support ($x \in \{ 0, \ldots, n \}, t_x \in \{ x, \ldots, n \}$) except for $x=0, t_x=0$, for which where there is only 1 sequence.

Some things that we do know, to help gain intuition for the problem:

(1) Marginally, we know $n_{runs}$ can be no larger than $x$.

(2) When $x=t_x=0$, there is only 1 sequence with the same $(x,t_x,n_{runs},n)$. It is $(0,0,0,n)$.

(3) When $x=1$, then $t_x \in \{1, 2, \ldots, n \}$. $n_{runs} = 1$ when $t_x=1$ and $0$ otherwise (all combinations are unique)

(4) When $x \geq 2$, then if $t_x = x$, then $n_{runs}=x$ and all combinations are unique.

(5) If $x=2$, then if $t_x \geq 3$, $n_{runs}=1$ occurs 2 times, while $n_{runs}=0$ occurs ${t_x - 1 \choose x-1} -2$ times.

(6) It can be shown that there is a recursive identity for larger values of $x$,when you successively condition upon the first element being $1$ or $0$, then the second, and so on and so forth. This should lead to something cleaner than the enumerative brute force approach, but not too pretty.

Many thanks to all.

-
Can you explain better/more what is $n_{runs}$ and "0th element"? –  ttnphns Aug 18 '14 at 20:48
@ttnphns I've attempted to do both - I hope it is clearer now. –  Dan Aug 18 '14 at 21:04

The runs are counted as if there were always an extra $1$ at position $0$, making $x+1$ ones. En bloc that would be counted as $x$ runs. To reduce it to $n_{runs}$ runs, this block has to be split at precisely $k=x - n_{runs}$ places, $k\ge 0$, yielding $k+1$ such blocks.

Consider, then, counting the number of binary sequences $y_0, y_1, \ldots, y_t$ which consist of alternating blocks of ones and zeros, both beginning and ending with blocks of ones and having $k+1$ blocks of ones (and therefore $k$ blocks of zeros). The total number of zeros is $t-x = y$. These sequences are in one-to-one correspondence with ordered pairs $(c, d)$ where $c$ is a composition of $x+1$ giving the counts of the $k+1$ one-blocks (in order) and $d$ is a composition of $y$ giving the counts of the $k$ zero-blocks (in order).

Because a composition of $a$ things into $b$ parts is determined by identifying the $b-1$ spaces between those $a$ things where the breaks occur, the number of such compositions is the number of $(b-1)$-subsets of the $a-1$ spaces, equal to $\binom{a-1}{b-1}$. Consequently, for $n\ge t$, the answer is

$$\binom{x}{k}\binom{y-1}{k-1}$$

with $k=x - n_{runs}$ and $y = t-x$. (Notice that $n$ plays no role: it only determines how many zeros to place after $y_t$.) For $n\lt t$, the answer is zero.

Consider, for example, the configurations $(x, t, n_{runs}, n) = (5, 9, 2, n)$, for which $k=5-2=3$ and $y=9-5=4$. The formula gives $\binom{5}{3}\binom{3}{2}=30$ possibilities, constructed from the $4$-compositions of $6$ ones and the $3$-compositions of $4$ zeros. The former are

$$6 = 1+1+1+3 = 1+1+2+2 = 1+1+3+1 = 1+2+1+2 = 1+2+2+1\\ = 1+3+1+1 = 2+1+1+2 = 2+1+2+1 = 2+2+1+1 = 3+1+1+1$$

while the latter are

$$4 = 1+1+2 = 1+2+1 = 2+1+1.$$

To illustrate the correspondence between binary sequences and ordered pairs of compositions, consider the first composition in each group. The composition $6=1+1+1+3$ designates the blocks $1,1,1, 111$ of ones while the composition $4=1+1+2$ designates the blocks $0,0,00$ of zeros to put between them, yielding the corresponding sequence

$$(1+1+1+3, 1+1+2)\to 1\ 0\ 1\ 0\ 1\ 00\ 111$$

This is to be followed by $n-t$ zeros and the initial one (for $y_0$) should be dropped. Sure enough, the resulting sequence $0101001110\ldots 0$ has $x=5, t=9, n_{runs}=2$ as planned.

Going in the other direction, consider the sequence $00\ 1\ 000\ 1111\ 0\ 1\ 0000$, for which $(x,t,n_{runs},n)=(6, 12, 3, 16).$ Ignoring the final $n-t=4$ zeros, which have to be there, and prefixing the sequence with $y_0=1$ yields $(y_0, y_1, \ldots, y_t) = 1\ 00\ 1\ 000\ 1111\ 0\ 1$. This displays a four-composition $1+1+4+1$ of seven ones and a three-composition $2+3+1$ of six zeros, whence the correspondence is

$$1\ 00\ 1\ 000\ 1111\ 0\ 1 \to (1+1+4+1, 2+3+1).$$

-
Thank you for the clarification, Dan. I have now taken that into account by setting $y_0=1$ and using the same technique. I also took the opportunity to correct an earlier mistake in counting the configurations of zeros. I altered the example to make it a little more substantial. –  whuber Aug 19 '14 at 10:50
This is just a technicality: the formula holds for n >= t, and x != t (the case x=0 is contained in this). When x equals t, the support for n_runs is x and the answer is clearly one despite (y-1 choose k-1) = (-1 choose -1). This distinction may not be as clumsy as it sounds. In all cases for a fixed (x, t) where x != t, the support for n_runs does not contain any cases for which y-1<0 or k-1<0. Could be helpful when building up a dictionary of cases against counts. –  Dan Aug 19 '14 at 20:13
According to many (such as Mathematica, as well as myself), $\binom{-1}{-1}=1$, so the formula should not need any special cases. –  whuber Aug 19 '14 at 20:20
If only R did the same :) –  Dan Aug 19 '14 at 20:34
Good point--I'm going to have to watch out when I use R for such calculations! This sounds like another line item for the next update of the R Inferno. –  whuber Aug 19 '14 at 20:40