Mixing
Combinatorics - Counting the number of binary strings with specified length and sum, with substring...
$begingroup$
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.
combinatorics binary
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
$endgroup$
add a comment |
$begingroup$
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.
combinatorics binary
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
$endgroup$
add a comment |
$begingroup$
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.
combinatorics binary
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
$endgroup$
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.
combinatorics binary
combinatorics binary
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
edited Aug 24 '15 at 23:45
BinConMan
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
asked Aug 24 '15 at 22:40
BinConManBinConMan
162
162
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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}
$$
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
$endgroup$
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
add a comment |
$begingroup$
First, let us ignore the $y$ condition, so the constraints are that the string is length $r$, there are $s$ ones, and there are no more than $x$ ones in a row.
Consider the "gaps" between the zeroes. There are $r-s+1$ such gaps; $r-s-1$ are in between two adjacent zeroes, and there are two more at the right and left ends. Let $a_i$ be the number of ones in the $i^{th}$ gap. Then $a_0+a_1+dots+a_{r-s}=s$, and each $0le a_ile x$. The number of solutions to this equation can be counted using inclusion exclusion as
$$
sum_{i=0}^{leftlfloorfrac{r}{x+1}rightrfloor}binom{r-s+1}{i}(-1)^ibinom{r-i(x+1)}{r-s}
$$
Now, let the above formula be $f(r,s,x)$. If we add the $y$ condition back in, then the answer to your question is
$$
f(y,s,x)+(r-y)times sum_{i=1}^xf(y-i-1,s-i,x)
$$
The $f(y,s,x)$ term accounts for sequences whose ones all occur in the first $y$ places. For everything else, there are $r-y$ choices for where the last one occurs. The index $i$ represents the length of the block of ones containing that last one, which is preceded by a $0$.
You can test this formula here.
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1408505%2fcombinatorics-counting-the-number-of-binary-strings-with-specified-length-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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}
$$
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
$endgroup$
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
add a comment |
$begingroup$
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}
$$
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
$endgroup$
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
add a comment |
$begingroup$
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}
$$
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
$endgroup$
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}
$$
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
edited Aug 24 '15 at 23:57
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
answered Aug 24 '15 at 23:30
Stefan MeskenStefan Mesken
14.4k32046
14.4k32046
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
add a comment |
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
If $X=3, S=3, Y=6, R=7$, shouldn't the answer be $binom{7}{3}-5=30$?
$endgroup$
– user84413
Aug 24 '15 at 23:47
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
@user84413 I didn't check your calculation, but I definitely need to have chunks of length $X+1$.
$endgroup$
– Stefan Mesken
Aug 24 '15 at 23:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
$begingroup$
If $X=2, S=3, Y=6, R=7$, I think the answer should be $binom{7}{3}-5-5=25$. (In any case, the answer should be less than $binom{7}{3}=35$.)
$endgroup$
– user84413
Aug 25 '15 at 19:56
add a comment |
$begingroup$
First, let us ignore the $y$ condition, so the constraints are that the string is length $r$, there are $s$ ones, and there are no more than $x$ ones in a row.
Consider the "gaps" between the zeroes. There are $r-s+1$ such gaps; $r-s-1$ are in between two adjacent zeroes, and there are two more at the right and left ends. Let $a_i$ be the number of ones in the $i^{th}$ gap. Then $a_0+a_1+dots+a_{r-s}=s$, and each $0le a_ile x$. The number of solutions to this equation can be counted using inclusion exclusion as
$$
sum_{i=0}^{leftlfloorfrac{r}{x+1}rightrfloor}binom{r-s+1}{i}(-1)^ibinom{r-i(x+1)}{r-s}
$$
Now, let the above formula be $f(r,s,x)$. If we add the $y$ condition back in, then the answer to your question is
$$
f(y,s,x)+(r-y)times sum_{i=1}^xf(y-i-1,s-i,x)
$$
The $f(y,s,x)$ term accounts for sequences whose ones all occur in the first $y$ places. For everything else, there are $r-y$ choices for where the last one occurs. The index $i$ represents the length of the block of ones containing that last one, which is preceded by a $0$.
You can test this formula here.
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
$endgroup$
add a comment |
$begingroup$
First, let us ignore the $y$ condition, so the constraints are that the string is length $r$, there are $s$ ones, and there are no more than $x$ ones in a row.
Consider the "gaps" between the zeroes. There are $r-s+1$ such gaps; $r-s-1$ are in between two adjacent zeroes, and there are two more at the right and left ends. Let $a_i$ be the number of ones in the $i^{th}$ gap. Then $a_0+a_1+dots+a_{r-s}=s$, and each $0le a_ile x$. The number of solutions to this equation can be counted using inclusion exclusion as
$$
sum_{i=0}^{leftlfloorfrac{r}{x+1}rightrfloor}binom{r-s+1}{i}(-1)^ibinom{r-i(x+1)}{r-s}
$$
Now, let the above formula be $f(r,s,x)$. If we add the $y$ condition back in, then the answer to your question is
$$
f(y,s,x)+(r-y)times sum_{i=1}^xf(y-i-1,s-i,x)
$$
The $f(y,s,x)$ term accounts for sequences whose ones all occur in the first $y$ places. For everything else, there are $r-y$ choices for where the last one occurs. The index $i$ represents the length of the block of ones containing that last one, which is preceded by a $0$.
You can test this formula here.
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
$endgroup$
add a comment |
$begingroup$
First, let us ignore the $y$ condition, so the constraints are that the string is length $r$, there are $s$ ones, and there are no more than $x$ ones in a row.
Consider the "gaps" between the zeroes. There are $r-s+1$ such gaps; $r-s-1$ are in between two adjacent zeroes, and there are two more at the right and left ends. Let $a_i$ be the number of ones in the $i^{th}$ gap. Then $a_0+a_1+dots+a_{r-s}=s$, and each $0le a_ile x$. The number of solutions to this equation can be counted using inclusion exclusion as
$$
sum_{i=0}^{leftlfloorfrac{r}{x+1}rightrfloor}binom{r-s+1}{i}(-1)^ibinom{r-i(x+1)}{r-s}
$$
Now, let the above formula be $f(r,s,x)$. If we add the $y$ condition back in, then the answer to your question is
$$
f(y,s,x)+(r-y)times sum_{i=1}^xf(y-i-1,s-i,x)
$$
The $f(y,s,x)$ term accounts for sequences whose ones all occur in the first $y$ places. For everything else, there are $r-y$ choices for where the last one occurs. The index $i$ represents the length of the block of ones containing that last one, which is preceded by a $0$.
You can test this formula here.
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
$endgroup$
First, let us ignore the $y$ condition, so the constraints are that the string is length $r$, there are $s$ ones, and there are no more than $x$ ones in a row.
Consider the "gaps" between the zeroes. There are $r-s+1$ such gaps; $r-s-1$ are in between two adjacent zeroes, and there are two more at the right and left ends. Let $a_i$ be the number of ones in the $i^{th}$ gap. Then $a_0+a_1+dots+a_{r-s}=s$, and each $0le a_ile x$. The number of solutions to this equation can be counted using inclusion exclusion as
$$
sum_{i=0}^{leftlfloorfrac{r}{x+1}rightrfloor}binom{r-s+1}{i}(-1)^ibinom{r-i(x+1)}{r-s}
$$
Now, let the above formula be $f(r,s,x)$. If we add the $y$ condition back in, then the answer to your question is
$$
f(y,s,x)+(r-y)times sum_{i=1}^xf(y-i-1,s-i,x)
$$
The $f(y,s,x)$ term accounts for sequences whose ones all occur in the first $y$ places. For everything else, there are $r-y$ choices for where the last one occurs. The index $i$ represents the length of the block of ones containing that last one, which is preceded by a $0$.
You can test this formula here.
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
answered Jan 7 at 23:35
Mike EarnestMike Earnest
21.9k12051
21.9k12051
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1408505%2fcombinatorics-counting-the-number-of-binary-strings-with-specified-length-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
