Results 1 to 3 of 3

Math Help - Combinations of two-element set

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    1

    Combinations of two-element set

    Hey. I have to write number of combinations in two-piece set for sequence of lenght 'n'. In this way that one of this two elements will never occur next to another.

    Examples:
    Set = 0 and 1
    Sequence of length = 2
    Element which doesn't have to occur next to another = 1
    Possible combinations:00 01 10
    Result: 3

    Set=0 and 1
    Sequence of length = 3
    Element which doesn't have to occur next to another = 1
    Possible combinations:000 001 010 100 101
    Result: 5

    Set=0 and 1
    Sequence of length = 4
    Element which doesn't have to occur next to another = 1
    Possible combinations:0000 0001 0010 0100 1000 1010 0101 1001
    Result: 8

    Am I able to appoint with formula or anyone knows the way how to make it?
    For some time I thought that formula n+2^(n-2), where n is a length of sequence is correct but everything indicates that for large lenghts of sequences this formula isn't correct.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,378
    Thanks
    745

    Re: Combinations of two-element set

    if the number of allowable sequences of length 5 is 13, it would appear that:

    a_{n+2} = a_{n+1} + a_n

    perhaps you should see if you can prove this formula.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1

    Re: Combinations of two-element set

    Quote Originally Posted by rout00 View Post
    Hey. I have to write number of combinations in two-piece set for sequence of lenght 'n'. In this way that one of this two elements will never occur next to another.
    Examples:
    Set = 0 and 1
    Sequence of length = 2
    Element which doesn't have to occur next to another = 1
    Possible combinations:00 01 10
    Result: 3
    The solution to this requires a classical technique.
    Let A_{n} be the set of admissible strings of length n
    Then let a_{n}=\|A_n\| be the number of elements in A_{n}.

    If we take any string from A_{n-1} and add a 0 to its end. Now we have a string in A_{n}.

    This time take any string from A_{n-2} and add a 01 to its end. Now we have another string in A_{n}.

    Look at reply #2. You will see how that recurrence relation fits in.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Orbits of an element and the Stabilizer of the element
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 24th 2011, 05:41 AM
  2. Distinct element combinations and permutations
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 18th 2010, 01:40 PM
  3. Non-distinct element combinations and permutations
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 18th 2010, 01:39 PM
  4. Replies: 3
    Last Post: March 23rd 2010, 07:05 PM
  5. Element in a Set
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 23rd 2010, 09:07 AM

Search Tags


/mathhelpforum @mathhelpforum