Number of compositions of a positive number n, with factors between 1 and a certain number m I'm trying to find the number of compositions of a positive number $n$, with factors between 1 and a certain number $m$.
That is, all the combinations of limited numbers that add up to $n$
$f(n, m)$
For example:
$f(3, 2) = |(1+1+1), (1+2), (2+1)| = 3$
$f(3, 3) = |(1+1+1), (1+2), (2+1), (3)| = 4$
$f(5, 3) = |(1+1+1+1+1), .... , (3+2), (2+3)| = 13$
Reading online I found this formula for calculating the composition, but it works only in some special cases:
$\sum_{k = \lceil n/m \rceil}^{n} \binom{n-1}{k - 1}$
Can someone tell me the general formula?
 A: I was able to callculate $f(m,n)$ quickly by using recurrence:
$$f(n, m)=1\quad \text{if} \quad  n\in\{0,1\}$$
$$f(n, m)=0\quad \text{if} \quad  n<0$$
$$f(n,m)=\sum_{k=1}^m f(n-k,m)$$
...or in Mathematica:
f[n_, m_] := 1 /; n == 0 || n == 1

f[n_, m_] := 0 /; n < 0

f[n_, m_] := f[n, m] = Sum[f[n - k, m], {k, 1, m}]

This gives accurate results for all your examples and calculates the number of combinations for bigger values of $n,m$ fairly quickly. For example:
$$f(5,3)=13$$
$$f(20,10)=521472$$
$$f(100,20)=633800819629853453628932292608$$
A: There is no general formula. In order to compute $f(n,m)$ quickly, you can write the recurrence relation as a matrix equation. Let $x_n$ be the vector
$$
x_n=\begin{bmatrix}f(n,m)\\f(n-1,m)\\f(n-2,m)\\\vdots\\f(n-m+1,m)\end{bmatrix}
$$
and let $A$ be the $m\times m$ matrix which has ones just below the diagonal, ones on the top row, and zeroes everywhere else. When $m=4,$
$$
A=\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}
$$
You can verify that
$$
x_n=Ax_{n-1}
$$
holds for all $n\ge 1$. Iterating this, you get
$$
x_n=A^nx_0=A^n\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix}
$$
Therefore, to compute $f(n,m)$ quickly, it suffices to compute $A^n$ quickly, which can be done in $O(m^3\log n)$ time using exponentiation by squaring.
