isi-entrance 2009 Q8

isi-entrance · India · solved Combinations & Selection Counting Integer Solutions to Equations

Let $f(n)$ be the number of ways to write a positive integer as an ordered sum of three non-negative integers, where each integer is chosen from $\{0, 1, 2, \ldots, 2n-1\}$ (i.e., using $n$ colours with values $0$ to $2n-1$). Find $f(n)$.

$$f(n+1) = f(n) + \binom{4n}{2} + 2\binom{2n}{1} + \binom{2n}{1} + 1$$ $$f(1) = 1$$ $$f(n+1) = f(n) + 8n^2 + 4n + 1$$ $$f(n) - f(1) = \frac{4}{3}(n-1)(n)(2n-1) + 2(n-1)n + (n-1)$$ $$f(n) = \frac{n}{3}(8n^2 - 6n + 1) \quad \forall n \in \mathbb{N}$$
Alternatively by brute force: $$\text{Total} = \frac{n(n-1)(n-2)}{6} + n^3 + \frac{3n^2(n-1)}{2} = \frac{n}{3}(8n^2 - 6n + 1)$$

Let $f(n)$ be the number of ways to write a positive integer as an ordered sum of three non-negative integers, where each integer is chosen from $\{0, 1, 2, \ldots, 2n-1\}$ (i.e., using $n$ colours with values $0$ to $2n-1$). Find $f(n)$.

Paper Questions

Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10