3
$\begingroup$

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

  • 0
    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...2012-12-07

2 Answers 2

1

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

  • 0
    Why is this the solution? Can you provide some explanation (or at least a link to some explanation)? How does the solution change if we want to ensure the string contains "010" instead of "111"?2016-10-08
0

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.

  • 0
    To figure out the sequences with two, but not more, consecutive 1s: Consider the cases $0$, $01$ and $110$. You get the recursion $S(k,m)=S(k,m-1)+S(k-1,m-1)+S(k-2,m-1)$ if $k\geq 2$ and $m\geq 1$. And $S(0,0)=1$. Where $S(k,m)$ denotes the number of sequences with $k$ times $1$ and $m$ times $0$ and no more then $2$ consecutive 1s. This isn't an easy recursion to solve, but it may help you getting any further.2012-12-08