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.