How many words of length $n$ over the alphabet ${0,1, 2}$ contain an even number of zeros?












2












$begingroup$



How many words of length $n$ over the alphabet ${0,1, 2}$ contain an even number of zeros?




I can't understand why it isn't $3^{n-1} cdot 2$.



For $n-1$ letters, we have $3$ options. That means $3^{n-1}$.



And then for the last letter ($n$), we have two cases:



first - if there were odd zeros the last letter will be $0$ ($1$ option)



second - if there were even zeros, the last letter will be $1$ or $2$ ($2$ options)



means $3^{n-1} cdot 2$



Why am I wrong?



THX






combinatorics discrete-mathematics







share|cite|improve this question











$endgroup$












  • $begingroup$
    Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:08










  • $begingroup$
    How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:24






  • 1




    $begingroup$
    The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:24










  • $begingroup$
    i know that the answer is 3n−1/2 but cant understand why
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:26












  • $begingroup$
    Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
    $endgroup$
    – André 3000
    Dec 9 '18 at 4:42


















2












$begingroup$



How many words of length $n$ over the alphabet ${0,1, 2}$ contain an even number of zeros?




I can't understand why it isn't $3^{n-1} cdot 2$.



For $n-1$ letters, we have $3$ options. That means $3^{n-1}$.



And then for the last letter ($n$), we have two cases:



first - if there were odd zeros the last letter will be $0$ ($1$ option)



second - if there were even zeros, the last letter will be $1$ or $2$ ($2$ options)



means $3^{n-1} cdot 2$



Why am I wrong?



THX






combinatorics discrete-mathematics







share|cite|improve this question











$endgroup$












  • $begingroup$
    Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:08










  • $begingroup$
    How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:24






  • 1




    $begingroup$
    The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:24










  • $begingroup$
    i know that the answer is 3n−1/2 but cant understand why
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:26












  • $begingroup$
    Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
    $endgroup$
    – André 3000
    Dec 9 '18 at 4:42
















2












2








2


2



$begingroup$



How many words of length $n$ over the alphabet ${0,1, 2}$ contain an even number of zeros?




I can't understand why it isn't $3^{n-1} cdot 2$.



For $n-1$ letters, we have $3$ options. That means $3^{n-1}$.



And then for the last letter ($n$), we have two cases:



first - if there were odd zeros the last letter will be $0$ ($1$ option)



second - if there were even zeros, the last letter will be $1$ or $2$ ($2$ options)



means $3^{n-1} cdot 2$



Why am I wrong?



THX






combinatorics discrete-mathematics







share|cite|improve this question











$endgroup$





How many words of length $n$ over the alphabet ${0,1, 2}$ contain an even number of zeros?




I can't understand why it isn't $3^{n-1} cdot 2$.



For $n-1$ letters, we have $3$ options. That means $3^{n-1}$.



And then for the last letter ($n$), we have two cases:



first - if there were odd zeros the last letter will be $0$ ($1$ option)



second - if there were even zeros, the last letter will be $1$ or $2$ ($2$ options)



means $3^{n-1} cdot 2$



Why am I wrong?



THX






combinatorics discrete-mathematics




combinatorics discrete-mathematics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 9 '18 at 0:20









N. F. Taussig

44.8k103358




44.8k103358










asked Dec 8 '18 at 23:39









OmPOIUOmPOIU

212




212












  • $begingroup$
    Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:08










  • $begingroup$
    How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:24






  • 1




    $begingroup$
    The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:24










  • $begingroup$
    i know that the answer is 3n−1/2 but cant understand why
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:26












  • $begingroup$
    Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
    $endgroup$
    – André 3000
    Dec 9 '18 at 4:42




















  • $begingroup$
    Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:08










  • $begingroup$
    How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:24






  • 1




    $begingroup$
    The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
    $endgroup$
    – N. F. Taussig
    Dec 9 '18 at 0:24










  • $begingroup$
    i know that the answer is 3n−1/2 but cant understand why
    $endgroup$
    – OmPOIU
    Dec 9 '18 at 0:26












  • $begingroup$
    Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
    $endgroup$
    – André 3000
    Dec 9 '18 at 4:42


















$begingroup$
Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
$endgroup$
– N. F. Taussig
Dec 9 '18 at 0:08




$begingroup$
Are you asking about the number of ternary sequences of length $n$ with an even number of zeros in the sequence?
$endgroup$
– N. F. Taussig
Dec 9 '18 at 0:08












$begingroup$
How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
$endgroup$
– OmPOIU
Dec 9 '18 at 0:24




$begingroup$
How many words of length n over the alphabet {0,1,2} contain an even number of zeros?
$endgroup$
– OmPOIU
Dec 9 '18 at 0:24




1




1




$begingroup$
The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 0:24




$begingroup$
The number of sequences with length $1$ that have an even number of zeros is $2$. They are $1$ and $2$. The number of sequences of length $2$ that have an even number of zeros is $5$. They are $00, 11, 12, 21, 22$. Try writing a recurrence relation.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 0:24












$begingroup$
i know that the answer is 3n−1/2 but cant understand why
$endgroup$
– OmPOIU
Dec 9 '18 at 0:26






$begingroup$
i know that the answer is 3n−1/2 but cant understand why
$endgroup$
– OmPOIU
Dec 9 '18 at 0:26














$begingroup$
Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
$endgroup$
– André 3000
Dec 9 '18 at 4:42






$begingroup$
Your approach is correct, but you've miscounted. Let $a_n$ be the number of desired words of length $n$. Your first case then contributes $(3^{n-1} - a_{n-1}) cdot 1$ possibilities ($#text{odd words} = text{total number of words} - #text{even words}$). Your second case contributes $2a_{n-1}$ possibilities, so $a_n = (3^{n-1} - a_{n-1}) + 2a_{n-1}$. Can you solve this recurrence?
$endgroup$
– André 3000
Dec 9 '18 at 4:42












2 Answers
2






active

oldest

votes


















2












$begingroup$

OP's solution is wrong, because it is not always 2 choices for the last digit -- it can be either 1 choice or 2 choices. All that OP's solution proves is that the answer is in the interval $$[1cdot 3^{n-1},2cdot 3^{n-1}]$$






share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    vadim123 explains why what you have doesn't give an exact formula: you don't know how often there is $1$ choice for the final place and how often there are $2$.



    However, these depend on whether there are an odd or even number of 0s in the first $n-1$ places. Write $a_{n-1}$ for the number of sequences of length $n-1$ with an even number of places. There are $3^{n-1}$ possible sequences of length $n-1$. In $a_{n-1}$ of these, you have $2$ choices for the final place to make the total number of 0s even, and in the remaining $3^{n-1}-a_{n-1}$ times you only have $1$ choice. Can you deduce and solve a recurrence relation based on this?






    share|cite|improve this answer









    $endgroup$













      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
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031809%2fhow-many-words-of-length-n-over-the-alphabet-0-1-2-contain-an-even-numb%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









      2












      $begingroup$

      OP's solution is wrong, because it is not always 2 choices for the last digit -- it can be either 1 choice or 2 choices. All that OP's solution proves is that the answer is in the interval $$[1cdot 3^{n-1},2cdot 3^{n-1}]$$






      share|cite|improve this answer









      $endgroup$


















        2












        $begingroup$

        OP's solution is wrong, because it is not always 2 choices for the last digit -- it can be either 1 choice or 2 choices. All that OP's solution proves is that the answer is in the interval $$[1cdot 3^{n-1},2cdot 3^{n-1}]$$






        share|cite|improve this answer









        $endgroup$
















          2












          2








          2





          $begingroup$

          OP's solution is wrong, because it is not always 2 choices for the last digit -- it can be either 1 choice or 2 choices. All that OP's solution proves is that the answer is in the interval $$[1cdot 3^{n-1},2cdot 3^{n-1}]$$






          share|cite|improve this answer









          $endgroup$



          OP's solution is wrong, because it is not always 2 choices for the last digit -- it can be either 1 choice or 2 choices. All that OP's solution proves is that the answer is in the interval $$[1cdot 3^{n-1},2cdot 3^{n-1}]$$







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 9 '18 at 3:02









          vadim123vadim123

          76.4k897191




          76.4k897191























              2












              $begingroup$

              vadim123 explains why what you have doesn't give an exact formula: you don't know how often there is $1$ choice for the final place and how often there are $2$.



              However, these depend on whether there are an odd or even number of 0s in the first $n-1$ places. Write $a_{n-1}$ for the number of sequences of length $n-1$ with an even number of places. There are $3^{n-1}$ possible sequences of length $n-1$. In $a_{n-1}$ of these, you have $2$ choices for the final place to make the total number of 0s even, and in the remaining $3^{n-1}-a_{n-1}$ times you only have $1$ choice. Can you deduce and solve a recurrence relation based on this?






              share|cite|improve this answer









              $endgroup$


















                2












                $begingroup$

                vadim123 explains why what you have doesn't give an exact formula: you don't know how often there is $1$ choice for the final place and how often there are $2$.



                However, these depend on whether there are an odd or even number of 0s in the first $n-1$ places. Write $a_{n-1}$ for the number of sequences of length $n-1$ with an even number of places. There are $3^{n-1}$ possible sequences of length $n-1$. In $a_{n-1}$ of these, you have $2$ choices for the final place to make the total number of 0s even, and in the remaining $3^{n-1}-a_{n-1}$ times you only have $1$ choice. Can you deduce and solve a recurrence relation based on this?






                share|cite|improve this answer









                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  vadim123 explains why what you have doesn't give an exact formula: you don't know how often there is $1$ choice for the final place and how often there are $2$.



                  However, these depend on whether there are an odd or even number of 0s in the first $n-1$ places. Write $a_{n-1}$ for the number of sequences of length $n-1$ with an even number of places. There are $3^{n-1}$ possible sequences of length $n-1$. In $a_{n-1}$ of these, you have $2$ choices for the final place to make the total number of 0s even, and in the remaining $3^{n-1}-a_{n-1}$ times you only have $1$ choice. Can you deduce and solve a recurrence relation based on this?






                  share|cite|improve this answer









                  $endgroup$



                  vadim123 explains why what you have doesn't give an exact formula: you don't know how often there is $1$ choice for the final place and how often there are $2$.



                  However, these depend on whether there are an odd or even number of 0s in the first $n-1$ places. Write $a_{n-1}$ for the number of sequences of length $n-1$ with an even number of places. There are $3^{n-1}$ possible sequences of length $n-1$. In $a_{n-1}$ of these, you have $2$ choices for the final place to make the total number of 0s even, and in the remaining $3^{n-1}-a_{n-1}$ times you only have $1$ choice. Can you deduce and solve a recurrence relation based on this?







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Dec 9 '18 at 9:29









                  Especially LimeEspecially Lime

                  22.4k22858




                  22.4k22858






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031809%2fhow-many-words-of-length-n-over-the-alphabet-0-1-2-contain-an-even-numb%23new-answer', 'question_page');
                      }
                      );

                      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







                      -

                      Popular posts from this blog

                      How to send String Array data to Server using php in android

                      Image
                      0 I have a String array which contains value string array = {6,37,38,837,7,...} and I have also used some string values. I want to send that all string values and string array to my database which is located at server side. When I am click on submit button the data will stored in table. On the PHP side I want to read this array as it is,other thing i will do at background means PHP side. See my below code then you will get it what I am says. Here is my code: public class Hotels extends Activity { // Declare Variables JSONArray jsonarray = null; private static final String TAG_ID = "id"; public static final String TAG_NAME = "name"; public static final String TAG_LOCATION = "location"; public static final String TAG_DESC = "description"; String f_date, l_date;...
                      Read more

                      Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

                      Image
                      up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx...
                      Read more

                      Is anime1.com a legal site for watching anime?

                      Image
                      up vote 4 down vote favorite 1 Other anime streaming sites are blocking my IP because I'm Iranian while anime1.com isn't. I wanted to know if it's legal to watch/stream anime from this site. Thanks. anime-production share | improve this question edited Nov 27 at 22:38 W. Are 1,599 2 23 asked Nov 27 at 20:36 mhnajafi 23 3 add a comment ...
                      Read more