Finding number of Strings when content prefix is fixed [closed]












-2












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










share|cite|improve this question











$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
















-2












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










share|cite|improve this question











$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














-2












-2








-2





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










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 9 at 6:45









El Pasta

44615




44615










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














  • 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










1 Answer
1






active

oldest

votes


















1












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






share|cite|improve this answer









$endgroup$




















    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












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






    share|cite|improve this answer









    $endgroup$


















      1












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






      share|cite|improve this answer









      $endgroup$
















        1












        1








        1





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






        share|cite|improve this answer









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







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Jan 9 at 7:07









        JevautJevaut

        1,037112




        1,037112















            Popular posts from this blog

            Mario Kart Wii

            What does “Dominus providebit” mean?

            File:Tiny Toon Adventures Wacky Sports JP Title.png