Results 1 to 5 of 5

Math Help - please explain me this counting

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    129

    please explain me this counting

    How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s?

    Answer is n+1 (counting the empty string)
    Where on earth the empty string comes?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    19,299
    Thanks
    1907
    Awards
    1
    Quote Originally Posted by zpwnchen View Post
    How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s?
    Answer is n+1 (counting the empty string)
    Where on earth the empty string comes?
    I have no idea. I think that is an absurd idea.

    But that must be defined somewhere in your text material.
    If so, you should use it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Plato View Post
    I have no idea. I think that is an absurd idea.

    But that must be defined somewhere in your text material.
    If so, you should use it.
    I don't think the empty string is an "absurd idea" at all. Almost all programming languages that I know of have it. Also, the set of all strings, including the empty string, forms a monoid with respect to concatenation - and the empty string is the neutral element for that monoid. If we did not allow the empty string, then the set of strings would not form a monoid with respect to concatenation, which would be very sad indeed.

    Once one accepts that the concept of an empty string is quite reasonable, the next question concerns the answer to the exercise in question. Now consider: are all characters contained in the empty string equal to 1? - The answer is yes, of course. Hence the empty string has to be included in the counting of all strings of length \leq n consisting entirely of 1s.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2015
    From
    United States
    Posts
    1

    Re: please explain me this counting

    The question says that the string should not exceed length 'n' , so a null string of length 0 should be acceptable . Right ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Dec 2013
    From
    Colombia
    Posts
    293
    Thanks
    74

    Re: please explain me this counting

    Quote Originally Posted by Failure View Post
    Now consider: are all characters contained in the empty string equal to 1? - The answer is yes, of course.
    Personally, I find the idea of a empty string containing only 1s rather preposterous. If it is going to be considered to contain any character it should be zero. This would accord with it's boolean translation (in most languages) of False.

    Having said that, the interpretation under which we say that strings consisting only of 1s are those that do not contain any 0s would give a natural case for inclusion of the empty string.
    Last edited by Archie; April 15th 2015 at 03:58 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Explain me why ...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 19th 2009, 10:13 AM
  2. Can someone explain this to me?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 12th 2009, 09:36 PM
  3. Please explain
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 1st 2008, 10:11 PM
  4. Please explain
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 24th 2008, 09:50 PM
  5. Help! Need someone to explain
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 17th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum