 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/discrete-mathematics-continuous-mathematics-and-probability-resit/2/d/solution

Pad every number with leading zeros to obtain exactly

n

decimal digits. Its digits are a solution of

d_{1} + \dots + 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) = (9 n + 8) = \frac{1}{9 !} \prod_{j = 0}^{8} (n + j) .

For

n \geq 1

n + j \leq n (j + 1)

, so

f (n) \leq n^{9} \prod_{j = 0}^{8} (j + 1) /9! = n^{9}

. Thus $f (n) = O (n^{9})$ , with an explicit Big O notation constant

C = 1

and threshold

n = 1

 New to topics? Read the docs here!