Results 1 to 5 of 5

Math Help - Four colors, no back-to-backs (recursive)

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    10

    Four colors, no back-to-backs (recursive)

    (I posted already that for-loop question from our exam, sorry if this comes out as flooding)


    So the question was short and clear, but I can't figure out the answer.

    We have four colors (blue and three others) of poker chips in a stack of n chips. In how many ways can the stack be formed so that blue chips are not directly on top of each other?

    What I understood by myself:
    For example with three chips the options are
    1) b o b (o = other, b = blue)
    2) o b o
    3) o o b
    4) b o o
    5) o o o

    Which gives us 3+9+9+9+27=57 ways.

    With two chips the options are
    1) b o
    2) o b
    3) o o

    Which gives us 3+3+9 = 15 ways.

    But I can't figure out any kind of formula for this.

    If someone posted already similar question, a link to that thread would be nice.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    I cannot give you a recursive solution. But can give a counting solution.
    If we have N chips then maximum number of blue chips is  \max  = \left\lceil {\frac{N}{2}} \right\rceil .
    Then the count is  \sum\limits_{k = 0}^{\max } {\binom{N-k+1}{k}3^{N - k} } .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    10
    Quote Originally Posted by Plato View Post
    I cannot give you a recursive solution. But can give a counting solution.
    If we have N chips then maximum number of blue chips is  \max  = \left\lceil {\frac{N}{2}} \right\rceil .
    Then the count is  \sum\limits_{k = 0}^{\max } {\binom{N-k+1}{k}3^{N - k} } .
    The max part is clear - if you have more than half of stack blue chips, there has to be blue chips on top of each other. On count, that 3 is the number of other colors, right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by jflurrie View Post
    The max part is clear - if you have more than half of stack blue chips, there has to be blue chips on top of each other. On count, that 3 is the number of other colors, right?
    Correct about the 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Hi jlflurrie,

    Plato has given you an excellent solution, but if I understand you correctly, you may be interested in a recursive solution, is that right?

    If so let's say an arrangement is "acceptable" if no blue chips are adjacent, and let a_n be the number of acceptable arrangements with n poker chips. We know

    [1] a_1 = 4 and
    [2] a_2 = 15.

    Now suppose we have a stack of n+1 chips, where n \geq 2. The chip on top is either blue or one of the other colors. If it is blue, then the chip under it must be one of the other 3 colors, and the remaining n-1 chips can be any acceptable arrangement; so the number of arrangements with a blue chip on top is 3 a_{n-1}. If the chip on top is one of the other 3 colors, then the remaining n chips can be any acceptable arrangement; so this can be done in 3 a_n ways.

    Hence
    a_{n+1} = 3 a_n + 3 a_{n-1}.

    Together with [1] and [2], this is enough to find a_n for any n.
    Last edited by awkward; May 22nd 2010 at 02:12 PM. Reason: phraseology
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Car colors
    Posted in the Statistics Forum
    Replies: 6
    Last Post: January 27th 2011, 05:35 PM
  2. Colors
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: March 20th 2009, 05:51 AM
  3. Back to back stemplot
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 16th 2009, 10:16 AM
  4. colors
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 3rd 2007, 07:29 AM
  5. Do you know your colors?
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: December 21st 2006, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum