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

Table of contents
- Solution 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

.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version