Finding number of Strings when content prefix is fixed [closed]
$begingroup$
Let $n geq m geq k$ be three non-negative integers. What is the number of binary strings of length n over the alphabet $A= { 0,1}$ whose prefix of size $m$ contains exactly $k$ numbers equal to $0$ ?
discrete-mathematics permutations
edited Jan 9 at 6:45
El Pasta
44615
asked Jan 9 at 6:37
guccigucci
11
$endgroup$
closed as off-topic by Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin Jan 9 at 10:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Let $n geq m geq k$ be three non-negative integers. What is the number of binary strings of length n over the alphabet $A= { 0,1}$ whose prefix of size $m$ contains exactly $k$ numbers equal to $0$ ?
discrete-mathematics permutations
edited Jan 9 at 6:45
El Pasta
44615
asked Jan 9 at 6:37
guccigucci
11
$endgroup$
closed as off-topic by Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin Jan 9 at 10:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.
2
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43
add a comment |
$begingroup$
Let $n geq m geq k$ be three non-negative integers. What is the number of binary strings of length n over the alphabet $A= { 0,1}$ whose prefix of size $m$ contains exactly $k$ numbers equal to $0$ ?
discrete-mathematics permutations
edited Jan 9 at 6:45
El Pasta
44615
asked Jan 9 at 6:37
guccigucci
11
$endgroup$
Let $n geq m geq k$ be three non-negative integers. What is the number of binary strings of length n over the alphabet $A= { 0,1}$ whose prefix of size $m$ contains exactly $k$ numbers equal to $0$ ?
discrete-mathematics permutations
discrete-mathematics permutations
edited Jan 9 at 6:45
El Pasta
44615
asked Jan 9 at 6:37
guccigucci
11
edited Jan 9 at 6:45
El Pasta
44615
asked Jan 9 at 6:37
guccigucci
11
edited Jan 9 at 6:45
El Pasta
44615
edited Jan 9 at 6:45
El Pasta
44615
edited Jan 9 at 6:45
El Pasta
44615
44615
asked Jan 9 at 6:37
guccigucci
11
asked Jan 9 at 6:37
guccigucci
11
asked Jan 9 at 6:37
guccigucci
11
11
closed as off-topic by Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin Jan 9 at 10:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin Jan 9 at 10:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Travis, José Carlos Santos, Eevee Trainer, mrtaurho, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.
2
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43
add a comment |
2
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43
2
2
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In how many different ways can $k$ zeroes be ordered within the prefix of length $m$?
$$
N_1={m choose k}
$$
Also, how many different substrings can there be of length $n-m$ after the prefix of length $m$?
$$
N_2=2^{n-m}
$$
since there are $n-m$ gaps which can be filled by either $0$ or $1$. Therefore,
$$
N=N_1 cdot N_2= {m choose k} cdot 2^{n-m}
$$
is the final answer.
answered Jan 9 at 7:07
JevautJevaut
1,037112
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In how many different ways can $k$ zeroes be ordered within the prefix of length $m$?
$$
N_1={m choose k}
$$
Also, how many different substrings can there be of length $n-m$ after the prefix of length $m$?
$$
N_2=2^{n-m}
$$
since there are $n-m$ gaps which can be filled by either $0$ or $1$. Therefore,
$$
N=N_1 cdot N_2= {m choose k} cdot 2^{n-m}
$$
is the final answer.
answered Jan 9 at 7:07
JevautJevaut
1,037112
$endgroup$
add a comment |
$begingroup$
In how many different ways can $k$ zeroes be ordered within the prefix of length $m$?
$$
N_1={m choose k}
$$
Also, how many different substrings can there be of length $n-m$ after the prefix of length $m$?
$$
N_2=2^{n-m}
$$
since there are $n-m$ gaps which can be filled by either $0$ or $1$. Therefore,
$$
N=N_1 cdot N_2= {m choose k} cdot 2^{n-m}
$$
is the final answer.
answered Jan 9 at 7:07
JevautJevaut
1,037112
$endgroup$
add a comment |
$begingroup$
In how many different ways can $k$ zeroes be ordered within the prefix of length $m$?
$$
N_1={m choose k}
$$
Also, how many different substrings can there be of length $n-m$ after the prefix of length $m$?
$$
N_2=2^{n-m}
$$
since there are $n-m$ gaps which can be filled by either $0$ or $1$. Therefore,
$$
N=N_1 cdot N_2= {m choose k} cdot 2^{n-m}
$$
is the final answer.
answered Jan 9 at 7:07
JevautJevaut
1,037112
$endgroup$
In how many different ways can $k$ zeroes be ordered within the prefix of length $m$?
$$
N_1={m choose k}
$$
Also, how many different substrings can there be of length $n-m$ after the prefix of length $m$?
$$
N_2=2^{n-m}
$$
since there are $n-m$ gaps which can be filled by either $0$ or $1$. Therefore,
$$
N=N_1 cdot N_2= {m choose k} cdot 2^{n-m}
$$
is the final answer.
answered Jan 9 at 7:07
JevautJevaut
1,037112
answered Jan 9 at 7:07
JevautJevaut
1,037112
answered Jan 9 at 7:07
JevautJevaut
1,037112
answered Jan 9 at 7:07
JevautJevaut
1,037112
1,037112
add a comment |
add a comment |
2
$begingroup$
Your question will attract more attention if you show what thoughts you have about solving it and where you're stuck -- people will find it easier to help you.
$endgroup$
– postmortes
Jan 9 at 6:43