1. Not finding help here? Sign up for a free 30min 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!

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?