$\lim_{N \rightarrow \infty} \frac{f(N)}{N^2}$?, $f(N):$ number of (x,y,z) satisfying $x+y+z = N, x \leq y \leq z$.

36 Views Asked by At

What is $\lim_{N \rightarrow \infty} \frac{f(N)}{N^2}$, where $f(N)$ is the number of points satisfying $x+y+z = N, x \leq y \leq z$?

$x,y,z$ are positive integers (can't be zero).

Without the $x \leq y \leq z$ constraint, I can use a simple stars and bars approach to obtain $$ f(N) = \binom{N-1}{2} $$

But with the constraint, is the solution simply the above divided by $3!$?

Say $N = 10, a = 3, b = 2, c = 5$. We can assign $x,y,z$ to 1 of these 3 values, but there are $3!$ ways in which we can do this. The above binomial coefficient counts for all the ways that we do this. However, there is only a single arrangement out of the $3!$ permutations that satisfies the constraint $x \leq y \leq z$.

But the issue is, this idea doesn't seem to work if 2 out of the numbers in $a,b,c$ are duplicates.

1

There are 1 best solutions below

2
On

In the limit, the cases where two (or all three) numbers are equal, are negligible. Indeed, there are only approximately $\frac N2$ solutions to $2x+z=N$, which is much less than ${N-1\choose 2}=\frac12N^2+\ldots$. In other words, there are constants $a,b,c,d$ with $$ \frac12N^2+aN+b\ge 6f(N)\ge \frac12N^2-cN-d.$$ When dividing by $N^2$ and taking the limit, these disappear.