A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a\_1, a\_2, \ldots, a\_k)$ such that $ \sum\_{i=1}^k a\_i = n $. I am interested in the case when the parts are bounded: $a\_i\in\{0, 1, \ldots, j-1\}$. The number of such compositions satisfies the two-variable recurrence
\begin{equation}
\kappa(n,j,k)=\sum\_{i=0}^{j-1}\kappa(n-i,j,k-1)
\end{equation}
and can be expressed as
\begin{equation}
\kappa(n,j,k) = \sum\_{s\geq0} (-1)^s {k \choose s} {k-sj+n-1 \choose k-1}
\end{equation}
[R. P. Stanley, Enumerative Combinatorics, Vol. I, p. 307].
Does someone know how to find the asymptotics of $\kappa(n,j,k)$ when $k\to\infty$, $n\sim\lambda k$, $\lambda\in(0,j-1)$, and $j$ is fixed? In particular, I would like to determine
\begin{equation}
\lim\_{k\to\infty,\ n = \lambda k} (\kappa(n,j,k))^{\frac{1}{k}} =\ ?
\end{equation}



Diagonal asymptotics of integer compositions
Up to a factor of $j^k$, What you're asking for is the probability $P$ that a k-step random walk with steps chosen uniformly from $S = \{0, 1, ..., j-1\}$ lands on $\lambda n$. This is the probability of return to the origin at time $k$ of the (typically biased) random walk with steps chosen uniformly from $S - \lambda = \{-\lambda, -\lambda+1, \dots, -\lambda + j-1\}$.


If we choose some $t$ and bias this random walk so that $-\lambda+r$ has probability $t^{-\lambda + r}/Z\_t$, we are multiplying the probability of return to the origin by $(j/Z\_t)^{k}$. But we can choose $t$ so that this new random walk is unbiased, in which case its probability of return to the origin is roughly proportional to $k^{-1/2}$.


So, $P \sim k^{-1/2 }j^{-k}Z\_t^k$, and the number you're interested in is roughly 


$$k^{-1/2} Z\_t^k.$$


All that remains is to find the values of $t$ such that this new random walk is unbiased, but this is the value that maximizes the probability of return to the origin, i.e. the value for which $$Z\_t = \sum\_{r=0}^{j-1} t^{-\lambda + r} = t^{-\lambda}\frac{t^j-1}{t-1}$$ is minimal.


So the number you're interested in is roughly


$$k^{-1/2} \rho^k,$$


where


$$\rho = \min\_t t^{-\lambda}\frac{t^j-1}{t-1}.$$


You can get an explicit upper bound on $\rho$ by noting that, by convexity of the summands, $$\frac1j Z\_t = \frac1j \sum\_{r=0}^{j-1} t^{-\lambda + r} \leq \frac{1}{2}(t^{-\lambda} + t^{-\lambda+j-1}).$$
The optimal value of $t$ is $((j-1)/\lambda-1)^{-1/(j-1)}$, which gives


$$\rho \leq \frac{j}{2} \left( 
\left(\alpha^{-1}-1\right)^{\alpha} + \left(\alpha^{-1}-1\right)^{-(1-\alpha)}
\right) = \frac{j}{2} \alpha^{-\alpha}(1-\alpha)^{-(1-\alpha)},$$
where $\alpha = \lambda/(j-1).$


