= Solution
Pad every number with leading zeros to obtain exactly $n$ decimal digits. Its digits are a solution of $d_1+\cdots+d_n=9$ in nonnegative <integers>. Conversely every such solution is a valid digit string, since no individual digit can exceed $9$; its digit sum also excludes the number zero. The <stars and bars> count therefore gives
$$
f(n)=\binom{n+8}{9}=\frac1{9!}\prod_{j=0}^8(n+j).
$$
For $n\geq1$, $n+j\leq n(j+1)$, so $f(n)\leq n^9\prod_{j=0}^8(j+1)/9!=n^9$. Thus \b[$f(n)=O(n^9)$], with an explicit <Big O notation> constant $C=1$ and threshold $n=1$.
Back to article page
