Take the 2-minute tour ×
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.

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

share|improve this question
    
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 2

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.

share|improve this 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

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

share|improve this answer

Your Answer

 
discard

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.