Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many words

  1. Jul 2, 2007 #1
    how many words of length k can you create from {1,...,k} such that 1 appears even number of times?
    well, for k=0 we have 1, for k=1 we have zero, and for k=2 we have one.
    i thought to use here a recursion formula.
    but not quite sure how to do so, i mean if k>=3, and a_k stands for the number of legitiamte words, then if no 1 appears in the word then we have (k-1)^k words, let's assume that in a_k-1 1 appears even number times then for the the last number we have (k-1) choices, so i think that the equation should be:
    a_k=(k-1)*a_k-1+(k-1)^k
    am i correct here?
    now if this is correct then how find a suitable private answer for non homogenoues part?
     
  2. jcsd
  3. Jul 2, 2007 #2
    my mistake for a_2 we have two options 22 and 11.
     
  4. Jul 2, 2007 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You have written that the way to make a word of length k with an even number of 1s in it is to append a non-1 to a string of length k-1 with an even number of 1s. This is not true. Plus, you have over counted - why treat the string with no 1s in it separately and therefore counted it twice?
     
  5. Jul 2, 2007 #4
    so how would you go to solve this?
    i saw a solution with power series, but didn't understand it.
     
  6. Jul 2, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You should try to learn how to use power series (generating functions) - they are incredibly powerful.

    If you really want a recurrence relation, then do the naive thing.

    A string of length k is gotten by adding a digit to a string of length k-1. In order for this string of length k to have an even number of 1s, then the shorter string must have an even number of 1s and you append a non-1, or it has an odd number of 1s and you append a 1. So count them. Hint: do you need to count the number of strings with an odd number of 1s in or is there a way to write that in terms of strings with an even number of 1s?
     
  7. Jul 2, 2007 #6
    yes i know how to use power series, my problem is that i don't undersatnd the answer.
    I'm given that for
    [tex]F(x)=\sum_{n>=0} a_n*x^n=(1+x^2/2!+x^4/4!+...)(1+x+x^2/2!+...)^{(k-1)}[/tex] where a_n is the sequence we searching for.
    but i don't understand how did they got to this, can you explain?


    p.s
    iv'e learned already generating functions, but still i don't see how arrive to this equation.
     
    Last edited: Jul 2, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?