Suppose I have a string of bits of length R. The sum of the bits must be equal to S, so there are S ones and R-S zeros. The longest string of ones cannot exceed X in length. Also the number of places spanning the first and the last 1 (inclusive) cannot exceed Y in length.
How many permutations exist that satisfy these constraints? I am looking for a general formula as a function of R, S, X, Y.
For example, the case where R = 12, S = 6, X = 2, Y = 9 has 37 solutions, which are listed below.
0 0 0 0 1 1 0 1 1 0 1 1
0 0 0 1 0 1 0 1 1 0 1 1
0 0 0 1 0 1 1 0 1 0 1 1
0 0 0 1 0 1 1 0 1 1 0 1
0 0 0 1 1 0 0 1 1 0 1 1
0 0 0 1 1 0 1 0 1 0 1 1
0 0 0 1 1 0 1 0 1 1 0 1
0 0 0 1 1 0 1 1 0 0 1 1
0 0 0 1 1 0 1 1 0 1 0 1
0 0 0 1 1 0 1 1 0 1 1 0
0 0 1 0 1 0 1 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 1 0
0 0 1 0 1 1 0 1 1 0 1 0
0 0 1 1 0 0 1 1 0 1 1 0
0 0 1 1 0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 1 1 0 1 0
0 0 1 1 0 1 1 0 0 1 1 0
0 0 1 1 0 1 1 0 1 0 1 0
0 0 1 1 0 1 1 0 1 1 0 0
0 1 0 1 0 1 1 0 1 1 0 0
0 1 0 1 1 0 1 0 1 1 0 0
0 1 0 1 1 0 1 1 0 1 0 0
0 1 1 0 0 1 1 0 1 1 0 0
0 1 1 0 1 0 1 0 1 1 0 0
0 1 1 0 1 0 1 1 0 1 0 0
0 1 1 0 1 1 0 0 1 1 0 0
0 1 1 0 1 1 0 1 0 1 0 0
0 1 1 0 1 1 0 1 1 0 0 0
1 0 1 0 1 1 0 1 1 0 0 0
1 0 1 1 0 1 0 1 1 0 0 0
1 0 1 1 0 1 1 0 1 0 0 0
1 1 0 0 1 1 0 1 1 0 0 0
1 1 0 1 0 1 0 1 1 0 0 0
1 1 0 1 0 1 1 0 1 0 0 0
1 1 0 1 1 0 0 1 1 0 0 0
1 1 0 1 1 0 1 0 1 0 0 0
1 1 0 1 1 0 1 1 0 0 0 0
My current line of thought is to consider the sum of each string of ones as parts of a composition of S and develop a formula as some variation on 'stars and bars'…
Assume $X \leq S \leq Y \leq R$ so that the problem is well-defined.
Thank you.
Best Answer
Consider the following question:
$\dagger$ What is the number of 0-1 sequences of length $Y$ with exactly $S$ many '1's but no subsequence of $X+1$ consecutive '1's?
I will only address the case that $X+1$ divides $Y$ and leave the general case to you.
Let us split the sequence of length $Y$ into chunks of length $X+1$ and then put exactly one '0' into each of these chunks. This can be done in $(X+1)^{Y/(X+1)}$ many ways and guarantees that there is no subsequence of $X+1$ many consecutive '1's. We may now insert the '1's. There are ${Y - Y/(X+1) \choose S}$ many possible combinations and thus $$(X+1)^{Y/(X+1)} \cdot {Y - Y/(X+1) \choose S}$$ is the answer to $\dagger$.
Now, there are $R-Y+1$ many ways in which we can insert this subsequence into our entire sequence (we may add $0,1, \ldots,$ or all $R-Y$ remaining '0' at the beginning of the sequence). This yields the final answer: $$ \left(R-Y+1 \right) \cdot (X+1)^{Y/(X+1)} \cdot {Y - Y/(X+1) \choose S} $$