Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive zeros.

Any input on how to approach this is appreciated.

share|cite|improve this question
I assume all sequences of $M$ ones and $N - M$ zeroes are a priori equally likely? – Erik P. Nov 27 '12 at 21:51
@Jean at least K. yes the sequences are equally likely but for a given sequence with fixed number of 0s and 1s I am looking for the number of possible derangements that have at least K consecutive zeros. – epinephelus Nov 27 '12 at 23:28

Let's compute $C(N,M,k)$ the number of sequences of length $N$, with $M$ zeros, and with all runs of zeros having length up to $k$. Say we have $\ell$ runs of zeroes: $z_1,z_2 \cdots z_\ell$ with $1\le z_i \le k$ , $\sum_{i=1}^\ell z_i=Z=N-M$, and $ \lceil Z/k \rceil \le \ell \le M+1$

Then $$C(N,M,k)=\sum_{\ell=\lceil M-N/k \rceil}^{M+1} c_r(M-N,\ell,k) \, c(M-\ell+1,\ell+1)$$

where $c(A,B)={A+B-1\choose B-1}$ is the number of weak compositions, and $c_r(A,B,k)$ is the number of (strict) compositions restricted to a maximum size $k$. This later problem is solved here.

share|cite|improve this answer

First off, I do not think you mean the standard combinatorial definition of derangement as found here: as this requires that each item has its own "home" let's say. I'm going to solve this assuming that you mean arrangement instead.

We can solve the problem by creating one "super" subsequence of zeroes having length $K$. Then we can think of now having $M$ ones still but $N-M-K+1$ zeroes as a result of the combination. In total we now have $N-K+1$ items to arrange in sequences. Before combining there were $\binom{N}{M}$ different sequences and after combining there are $\binom{N-K+1}{M}$ sequences with at least $K$ consecutive zeroes. Thus the probability you seek is: $$p(K) = \frac{\binom{N-K+1}{M}}{\binom{N}{M}} ; \ K=1,2,...,N-M$$

A quick sanity check at the endpoints of $K$ shows that we get what intuition or a quick sketch would confirm. For $K =1$ we know that the probability should be $1$ which the above formula $\frac{\binom{N}{M}}{\binom{N}{M}}$ gives. Also for $K = N-M$ we can see that there are $M+1$ positions for our "super" subsequence to occupy in the following diagram:

$$(\underbrace{000\cdots0}_{N-M} \underbrace{111\cdots1}_{M})$$

If you think of the rightmost $0$ in the "super" subsequence and the positions it can occupy, you will see that there are $M+1$ possible subseqences when $K = N-M$. And so the probability agrees with our formula: $$\frac{\binom{M+1}{M}}{\binom{N}{M}} = \frac{M+1}{\binom{N}{M}}$$.

share|cite|improve this answer
A quick counter example is when K = 2 M=1 N=4, a sequence of at least 2 consecutive zeros always exists whereas your formula implies P = 3/4. I think the issue is where you say there are binom(N-K+1,M) sequences with K consecutive zeros. Actually there are at least as many, there are many more especially for low M. Your answer can be regarded as a relaxed (I did simulations) lower bound for the actual probability – epinephelus Nov 28 '12 at 10:54
You are right. The numerator falls short in at least some cases probably all. I do hope I can figure this out now. Maybe the brute force counting approach will not work here even? Out of curiosity, what is the source of this problem? – Patrick Nov 28 '12 at 18:34

I think what you are looking for is covered [here][1]:

There are 2 types of approaches given in the answers to that question - either a dynamic programming solution or a Markov Chain model should lead to the answer you are seeking in any particular case. If you are up to attempting to find a general formula you should study these methods.

share|cite|improve this answer

Assuming $1$s and $0$s appear independent of each other, for $M$ ones, the probability that a $1$ appears is simply $p=\frac{M}{N}$ and for $0$ is simply $1-p$. The PDF of run of $K$ consecutive $0$s can then be calculated as follows:

$$ r(K) = \left\{ \begin{array}{rl} p(1-p)^K &\mbox{ $0\leq K\leq N$} \\ (1-p)^K &\mbox{ $K=N$} \end{array} \right. $$

share|cite|improve this answer
No. the number of zeros and non zeros on the sequence is fixed. Actually I am looking the number of possible derangements that have K consecutive zeros. – epinephelus Nov 27 '12 at 23:27
@user50921 you original question doesn't say that though. – jay-sun Nov 27 '12 at 23:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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