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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.


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|cite|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
@Jack M $2^7 - 1$, because you cannot have all $a$. – Deven Ware Nov 8 '13 at 21:47

Your Answer


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

Browse other questions tagged or ask your own question.