Number of $n$-ples of integers summing to a given integer Fix a non-negative integer $m$. For any integer $A \geq 1$, use $P_m(A)$ to denote the number of ways of rewriting $A = A_1 + A_2 + \ldots A_m$, with $A_i$ non-negative integers (eventually $0$).
Is it true that $P_m(A) \leq C^A$ for any $A$, for some constant $C$?
What is it possible to see is that, by summing separately on the outcome of the first integer,
$$
P_m(A) = \sum_{j=0}^{A} P_{m-1}(A-j)
$$
 A: The number of ways of writing $A$ as a sum of $m$ non-negative integers is given by a "stars and bars" argument - it is equal to $\binom{A+m-1}{m-1}$.  Essentially, we think of $n$ stars representing the units we want to add up to get $A$, and we place $m-1$ bars separating the different summands.  There are $A + m-1$ symbols to place, and we have to choose $m-1$ of them to be bars, giving the formula.  For example, if $A = 11$ and $m = 5$,
$****||***|*|***$
would correspond to the sum $11 = 4 + 0 + 3 + 1 + 3$.
Hence $P_m(A) = \binom{A+m-1}{m-1}$.  If $m$ is fixed and $A$ grows, then this is a polynomial in $A$ of degree $m-1$.  In particular, using a standard bound on the binomial coefficients,
$$ P_m(A) = \binom{A + m - 1}{m-1} \le \left( \frac{(A+m-1)e}{m-1} \right)^{m-1}. $$
(This is valid as long as $m \ge 2$.  If $m = 1$ then $P_m(A) = 1$.)
However, there does need to be some dependence on $m$.  Note that we also have
$$ P_m(A) = \binom{A+m-1}{m-1} = \binom{A+m-1}{A} \ge \frac{m^A}{A!}, $$
so you cannot get a general upper bound that does not depend on $m$ at all.
