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!

Recursive definition construction

  1. Jul 15, 2011 #1
    The problem statement, all variables and given/known data
    Construct a recursive definition for the following:

    The number of ways to stack n red, white, green, and blue poker chips so that there are no two consecutive blue poker chips.

    The attempt at a solution
    The number of possible combinations is [itex]4^n[/itex] minus the number of combinations that involve at least two blue poker next to each other.
    The number of combinations with blue poker chips next to each other for the first 6 steps is:
    3 chips: BBB + BB* (x3 other chips) + *BB (x3 other chips) = 7
    4 chips: BBBB + BBB* (x2 x3) + BB** (x3 x3 x3) = 34
    5 chips: BBBBB + BBBB* (x2 x3) + BBB** (x3 x3 x3) + BB*** (x4 x3 x3 x3) + BB*BB (x3) = 145
    6 chips: BBBBBB + BBBBB* (x2x3) + BBBB** (x3x3x3) + BBB*** (x4x3x3x3) + BB**** (x5x3x3x3x3) + BB**BB (x4x3x3) + BB*BBB (x2x3) = 1+6+27+108+405+36+6 = 589

    [itex]X1 = 4[/itex]
    [itex]X2 = (4)(4) -1 = 15[/itex]
    [itex]X3 = 4^3 - 7 = 57[/itex]
    [itex]X4 = 4^4 - 34 = 222[/itex]
    [itex]X5 = 4^5 - 145 = 879[/itex]
    [itex]X6 = 4^6 - 589 = 3507[/itex]

    I'm fairly sure those are correct, but I can't see any recursive function

    Thank-you in advance!
     
    Last edited: Jul 15, 2011
  2. jcsd
  3. Jul 15, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's not really very 'inductive'. Why don't you try to split the number of ways to stack into ways that end in blue and ways that don't end in blue and write an inductive step for each separately?
     
  4. Jul 15, 2011 #3
    You mean something like:
    X1 = 4
    X2 = 12 + 4 = 16;
    x3 = 48 + 4*4 = 64
    x4 = 192 + 4*4*4 = 256

    X1 = 4
    Xn = X(n-1)*4 + 4^(n-1)

    The problem is that I don't see any correlation with the rate at which exclusions occur due to consecutive blue poker chips. 0, 1, 7, 34, 145 (unless I'm doing something wrong to get to that, but I don't think I am).
     
  5. Jul 15, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, I mean let B(n) be the number of ways to legally stack n chips ending in blue. Let N(n) be the number of ways that don't end in blue. Can you write B(n+1) and N(n+1) in terms of B(n) and N(n)? That would be recursive.
     
  6. Jul 15, 2011 #5
    I get
    B(1) = 1
    B(2) = 3
    B(3) = 12
    B(4) = 36
    B(5) = 171
    B(6) = 648

    I still don't see any way that's recursive =[ This problem has been driving me nuts all day.

    Where X represents any chip but B:
    5 stack:
    XXXXB x 81 possibilities
    BXBXB x 9 possibilities
    BXXXB x 27
    XBXXB x 27
    XXBXB x 27

    6 stack:
    XXXXXB x 243
    XBXBXB x 27
    BXXXXB x 81
    XBXXXB x 81
    XXBXXB x 81
    XXXBXB x 81
    BXBXXB x 27
    BXXBXB x 27
     
  7. Jul 15, 2011 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The problem isn't asking you to count them. Suppose you KNOW B(n) and N(n). Can you write B(n+1) and N(n+1) in terms of those. That's all.
     
  8. Jul 15, 2011 #7
    The only way I know to discover B(n+1) is to have a starting place and identify a pattern to progression. I understand that the question isn't asking me to count them, but how can I calculate the recursion without a base set that indicates a recursive relationship?
     
    Last edited: Jul 15, 2011
  9. Jul 18, 2011 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Start with a chip pile in B(n) so it ends in blue. How many ways can you add another chip? Are the resulting piles in B(n+1) or N(n+1)? Now repeat the exercise for a chip pile in N(n).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recursive definition construction
  1. Recursive definition (Replies: 3)

  2. Recursive Definition (Replies: 2)

Loading...