1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quick Elementary Combinatorics Question / Verification

  1. Dec 18, 2011 #1
    1. The problem statement, all variables and given/known data

    I am using a book that doesn't have any solutions in it, so I would like to be sure that I am doing the problems right before I move on. The question is below:

    In a programming language, a variable name must start with a letter or the underscore character, and succeeding characters must be letters, digits, or the underscore character. Uppercase and lowercase letters are considered different.
    (a) How many variable names with exactly 5 characters can be formed?
    (b) How many are there with at most 5 characters?
    (c) How many are there with at most 5 characters, if they must read the same forwards and backwards? (note that kayak is acceptable but Kayak is not).

    3. The attempt at a solution
    (a) There are 53 possible characters for the first position, and 63 possibilities for the remaining 4 positions. So there are
    [itex]53 \cdot 63^4 = 834,906,933[/itex]
    possible 5 character variable names.

    (b) For some [itex]k[/itex], there are [itex]53 \cdot 63^{k-1}[/itex] possible variable names of length [itex]k[/itex]. So the number of possible variable names with length at most 5 is
    [itex]\sum_{k=1}^5 53 \cdot 63^{k-1} = 848,373,173[/itex] possible variable names with length at most 5.

    (c) For length 1, there are only 53 such possible variable names. For length 2, the first and last characters must be the same, so there are again only 53 such possible variable names. For length 3, there are 53 * 63 variable names, and the same number of variable names of length 4. For length 5, there are 53 * 63 * 63 possible variable names. Hence, there are
    [itex]53 + 53 + 53 \cdot 63 + 53 \cdot 63 + 53 \cdot 63^2 = 217,141[/itex]
    possible variable names with the desired property.

    Thanks!
     
  2. jcsd
  3. Dec 18, 2011 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your calculations look correct to me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Quick Elementary Combinatorics Question / Verification
  1. Elementary question. (Replies: 3)

  2. Combinatorics question (Replies: 2)

  3. Combinatorics Question (Replies: 7)

Loading...