Let $b_n$ be the number of compositions of $n$ into parts that are larger than $2$. Find a recurrence relation satisfied by $b_n$
compositions and recurrence relation
-
0yes that is correct it is compositions – 2012-11-05
3 Answers
One (very inelegant) way to solve the problem is to calculate the first few values of $b_n$ and look up the sequence in the On-Line Encyclopedia of Integer Sequences. I get
$\begin{array}{rcc} n:&3&4&5&6&7&8&9&10&11&12\\ b_n:&1&1&1&2&3&4&6&9&13&19 \end{array}$
OEIS returns eight hits, of which the second, A078012, turns out to be exactly what’s wanted. The entry gives the recurrence $b_n=b_{n-1}+b_{n-3}$ for $n\ge 4$, if we set $b_1=b_2=0$. Now that we have the answer, we can try to justify it.
Let $C_n$ be the set of compositions of $n$ with each part greater than $2$. We can split $C_n$ into $C_n'$, the set of compositions beginning with $3$, and $C_n''=C_n\setminus C_n'$. Clearly $|C_n'|=b_{n-3}$, so all that remains is to find a bijection between $C_n''$ and $C_{n-1}$. There’s a very simple one involving the first part of the composition; I’ll give you a chance to find it on your own.
For any $n\ge 3$, we have the trivial composition into $1$ part. In addition, there are the compositions with final entry $3$, and the ones with final entry $4$, and the ones with final entry $5$, and so on up to the compositions that have final entry $n-3$. It follows that $b_n=b_{n-3}+b_{n-4}+b_{n-5}+\cdots +b_3 +1.\tag{$1$}$ This is a recurrence, but not really what we are looking for. It would be nice to have a fixed length recurrence. Bumping the indices in $(1)$ up by $1$, we get $b_{n+1}=b_{n-2}+b_{n-3}+b_{n-4}+b_{n-5}+ \cdots+b_3 +1.\tag{$2$}$ Subtract $(1)$ from $(2)$ and rearrange a bit. We get $b_{n+1}=b_n +b_{n-2}.$ The initial conditions are $b_1=b_2=0$, and $b_3=1$.
$b_n$ can be divided into 2 parts and then conquered.
$b_n$ = Number of such compositions with first term equals to 3 + Number of such compositions with first term larger than 3
For "Number of such compositions with first term equals to 3": It's actually a bijection of b n-3. Think about it, if you remove that first term which equals to 3, it becomes the same as b n-3.
For "Number of such compositions with first term larger than 3": It's actually a bijection of b n-1. If you subtract 1 from the first term. it becomes the same as b n-1 (It's got a recursive pattern here! You can analyze b n-1 in the same way as this one and divide it to similar two parts!).
So, the answer is b n = b n-3 + b n-1, which agrees with André Nicolas's answer.
Good luck with Math 461 at UW!