00975333

j

00975333 Grimaldi, Ralph P. Meadows, Douglas S. Compositions of integers. Congr. Numerantium 76, 119-125 (1990). 1990 Utilitas Mathematica Publishing Inc., Winnipeg EN number of compositions ordered partitions Fibonacci number Fibonacci sequence For any integers $n,k$, where $n\ge 1$ and $k\ge 2$, let $F(n,k)$ denote the number of compositions, or ordered partitions, of $n$, where the only summands that are permitted are $1,2,3, \dots, k$. When $n=4$ and $k=3$, for example, we have $F(4,3) =7$, since there are seven compositions to be counted here: $$(1)\ 1+1+1+1 \quad (2)\ 1+1+2 \quad (3) \ 1+2+1 \quad (4)\ 2+1+1 \quad (5)\ 2+2 \quad(6)\ 1+3 \quad (7)\ 3+1$$ For the case where $k=2$, $F(n,2)$ counts the number of compositions of the positive integer $n$ using only 1's and 2's as summands. One finds that $F(n,2)= F_{n+1}$, the $(n+1)$-st Fibonacci number, where $F_0=0$, $F_1=1$, and $F_n= F_{n-1} +F_{n-2}$ for all $n\ge 2$. Consequently, many of the results we obtain in this paper will generalize known properties of the Fibonacci sequence.