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!

Combinatorics: Finding recurrence relation

  1. Nov 27, 2013 #1
    Find the number of ways to arrange three types of flags on an n foot flag pole: red flags (1 foot high), white flags (1 foot high), blue flags (3 feet high)

    Find a recurrence relation for this number with one condition that there cannot be three 1 foot flags in a row (regardless of their color).

    R= Red, W=White, B=Blue

    a_1 = 2, R, W
    a_2 = 4, RW, WR, WW, RR
    a_3 = 1, B
    a_4 = 4, B(a_1), W(a_3), R(a_3)
    a_5 = 12, B(a_2), W(a_4), R(a_4)
    a_6 = 21, B(a_3), W(a_5-2(a_3)), R(a_5-2(a_3))
    a_7 = 30, B(a_4), W(a_6-2(a_4)), R(a_6-2(a_4))
    a_8 = 24, B(a_5), W(a_7-2(a_5)), R(a_7-2(a_5))
    a_9 = -number,B(a_6), W(a_8-2(a_6)), R(a_8-2(a_6))
    Since there is a negative number, I do not think this is right...could anyone point out what I did wrong?
     
  2. jcsd
  3. Nov 27, 2013 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    doesn't look like the right way to count the number of flags that are six high and have a red on top. For starters, you are claiming there are ten such flags, and really you can only do (I think)

    R
    R/W
    B
    R/W

    or
    R
    B
    R/W
    R/W

    of which there are only eight such flags. Instead of trying to subtract away flags that you originally constructed that are actually illegal, just think about if you start with a R on top, what are the only possible chains you can have before you reach a B? Once you know that you have placed B everything underneath it is counted using your recurrence relation.
     
  4. Nov 27, 2013 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I approach this sort of problem by creating several related recurrence terms. You can have the total number of height n, the number of height n with at most one 1-foot flag on top, and the number that have a 3-foot flag on top. Then you can construct three recurrence relations that connect them.
     
  5. Nov 27, 2013 #4
    Let a_n be the arrangement of flags at n feet. Just figure it out...is it a_n = a_(n-3)+2*a_(n-4)+4*a_(n-5). The initial value is a_2= 1, a_2 = 4, a_3 = 1, a_4 = 4,a_5 = 12
     
  6. Nov 27, 2013 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I get the same recurrence relation.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Finding recurrence relation
Loading...