# Counting strings with given numbers of occurrences of 0 and 1, and containing a given substring

I have a group with the size of n, and only 2 different elements (1 and 0) with k times 1 and m times 0. For example:

1 1 1 0 1 1 1 where n would be 7, k 6 and m 1. I can arrange this group in Binomial[7,6] = Binomial[7,1] = 7 different ways.

1 1 1 0 1 1 1

1 1 0 1 1 1 1

1 0 1 1 1 1 1

0 1 1 1 1 1 1

1 1 1 1 1 1 0

1 1 1 1 1 0 1

1 1 1 1 0 1 1

And I want to know how often I can find the sequence 1 1 1. In this example it's easy. It doesn't matter how I arrange this group, I always find 1 1 1 so the answer is 7.

But how about

1 1 1 0 0 1 1, n=7, k=5, m=2

There are Binomial[7,5] = Binomial[7,2] = 21 ways of arranging this group, but how many times can I find the sequence 1 1 1? Sure I can write all 21 ways of arranging it down, and count it, but that's not what I am looking for. I'm thinking for hours about it, but I don't find out how I calculate it generally for n, k and m.

Regards

-
Ok, so it's not the same, but if instead of 3 consecutive 1s you are after only 2 consecutive 1s, the formula for "in how many ways can you arrange m 1s in n positions without having two consecutive 1s" is Binomial[n-m, m]. So you will have at least two consecutive ones in Binomial[n,m] - Binomial[n-m,m]. Figuring out how many have two, but not three consecutive 1's is beyond me right now... – Jaime Dec 7 '12 at 21:28

## 2 Answers

Thanks, I found the solution.

$$S(k,m) = \binom{k+m}{k}-\sum\limits_{j=0}^{\left\lceil\frac{k-1}{2}\right\rceil}\binom{m+1}{k-j}*\binom{k-j}{j}$$

-

take "111" as one element and you are there !

run it all on Binomial[n-2,m] instead of Binomial[n,m]

BTW, this is supposed to be a comment, not an answer.

-
I thought about that one, but then you are counting 1 (111) ... and (111) 1 ... as different, which they are not. Your formula doesn't produce the right result for his first example – Jaime Dec 7 '12 at 21:24
so you are looking for uninterrupted sequences of x or more 1s ? – ashley Dec 7 '12 at 21:34
Im looking for uninterrupted sequences of 3 or more 1s. – Frank_Martin Dec 7 '12 at 21:35
the other way round then: count the sequences with (no consecutive 1s) + (two or no consecutive 1s), subtract from the total. – ashley Dec 7 '12 at 21:40
Figuring out the sequences with two, but not more, consecutive 1s is the difficult thing... – Jaime Dec 7 '12 at 22:02