Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi guys I am studying for my exam which is in a few hours and I ran into two past exam problems.

Questions:

1) how many 7 letter sequence you can make with a,b,c such that there is at least one b and at most one c.

2) How many piles of n chips can you make with red, blue, or white such that no 2 red chips are together? Give initial conditions.

Answers:

1) I know I have to first make an exponential generating function. But I am really lost in how to solve this problem

2) I am pretty sure I have this one down

Consider the bottom chip in the pile. If it is blue or white, then the remainder of the pile can be any pile of height $n−1$ with no two red chips touching, so in both cases there are an−1 ways to complete the pile. If the bottom chip is red, the next chip cannot be red, so there are two cases: the next chip can be blue or white. In both cases the remainder of the pile can be any pile of height $n−2$ with no two red chips touching, so in both cases there are $a_{n−2}$ ways to complete the pile. Therefore,

$a_n = 2a_{n−1} + 2a_{n−2}$, for $n \ge 2$. and For the initial conditions, every pile of height 0 or 1 has no two red chips touching, so $a_0 = 1$, $a_1 = 3$

Please give me any hints or faster ways to solve these. Any help is greatly appreciated. Thank you.

share|improve this question
    
for the first one I don't think you need to use a generating function ( though you could ). You can just break into two cases, whether you use a $c$ or not. If no $c$ then you have $7$ positions and you must choose at least one to be a $b$, so you have ${7 \choose 1} + {7 \choose 2} + \cdots + {7 \choose 7}$. If there is one $c$ do the same thing, but first you have $7$ choices of where to put a $c$, and now you are messing with the $6$ remaining positions. –  Deven Ware Nov 8 '13 at 21:30
    
Also, the second answer looks good to me. –  Deven Ware Nov 8 '13 at 21:33
    
@DevenWare Or, more directly, you have $2^7$, because for each of the $7$ positions you have to choose either $a$ or $b$. –  Jack M Nov 8 '13 at 21:40
1  
@Jack M $2^7 - 1$, because you cannot have all $a$. –  Deven Ware Nov 8 '13 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.