Keywords: Tricks
1. Problem Description
$x, y, z \in \mathbb{N}$. For an integer $n$, $x + y + z = n$. Let $f(n)$ denote the number of solutions, which satisfies $x \le y \le z$. What’s the value of $\lim\limits_{n \xrightarrow{} \infty}\frac{f(n)}{n^2}$?
The core of this problem is the number of solutions given an integer constraint. Due to the symmetricity, $x \le y \le z$ accounts for $\frac{1}{3!}$ of the total number of the solutions. There are two methods to solve the total number of the solutions.
1.1 Combination
Consider this problem as the dividing the n balls into three parts. Let $x^{\prime} = x + 1 \in \{1, \dots\}$, $y^{\prime} = y + 1 \in \{1, \dots\}$, and $z^{\prime} = z + 1 \in \{1, \dots\}$. The origin problem then is equivalent to $x^{\prime} + y^{\prime} + z^{\prime} \le n + 3$. According to stars and bars (插板法), we can easily find the number of combinations are $C^{2}_{n + 2}$. Therefore, the value of the limits should be $\frac{1}{2 \times 3!} = \frac{1}{12}$
1.2 Geometry
$f(n)$ is the number of points on the surface of $x + y + z = 1$ in a unit cubic. Note that it is not equivalent to the area of surface (more specifically, the triangle, you know what I mean). The trickiest part is that the density of points on the surface is not equivalent to the number of point on the $(x, y, 0)$. One method to solve this problem is to use the area of the projection of the surface onto $(x, y, 0)$. We can get the same answer $\frac{1}{2 \times 3!} = \frac{1}{12}$.
1.3 Intuition
The number of point is equivalent to the volume instead of area. Therefore, given a constraints, we should apply the same metric to the numerator and denominator.
2. Generalization
Consider a $K$ dimensional vector space $(x_1, x_2, \dots, x_K)$. What is the number of integer solutions of $\sum_{i = 1}^K a_i x_i = n$?
2.1 Recursive method
Let $f(n, k)$ denote the number of solutions given k variables which sum up to n. The recursive formula can be written as:
$f(n, k) = \sum_{i = 1}^n f(n - a_k \cdot i, k-1)$
2.2 Generator function
Let $f(x)$ denote $\prod_{i=1}^K (1 + x_i^{a_i} + x_i^{2a_i} + x_i^{3a_i} + \dots) = \prod_{i=1}^K \frac{1}{1 - x_i^{a_i}}$. The number of integer solutions is $f^{(n)}(x)|_{x = 0}$
Reference
My roommate Ivan Ye.
Comments