Limit of Integer Partition Count
Let $x, y, z$ be positive integers satisfying $x + y + z = N$ and $x \le y \le z$. Define $f(N)$ as the number of such ordered triples.
Find $\displaystyle\lim_{N \to \infty} \frac{f(N)}{N^2}$.
Hints
- Start by counting something easier: how many ordered triples $(x, y, z)$ with $x + y + z = N$ and all parts positive are there? Use stars and bars.
- Every unordered multiset $\{x, y, z\}$ corresponds to either 1, 3, or 6 ordered triples depending on how many parts are equal. The 'all distinct' case dominates for large $N$.
- The number of triples with any two parts equal is $O(N)$, while the total ordered count is $O(N^2)$. So the tie-correction terms vanish in the limit, and you can divide the ordered count by $3! = 6$ to get the leading term of $f(N)$.
Worked Solution
How to Think About It: The question is asking how many ways you can split $N$ into three positive integer parts when you only count each multiset once (i.e., $\{1, 2, 5\}$ counts the same as $\{5, 1, 2\}$). The natural first move is to count the easier thing -- ordered triples -- and then divide out the symmetry. Most triples have all three parts distinct, so dividing by $3! = 6$ should get you close. The correction for ties is lower-order, so the limit is clean.
Quick Estimate: The total number of ordered triples $(x, y, z)$ with $x, y, z \ge 1$ and $x + y + z = N$ is $\binom{N-1}{2} = \frac{(N-1)(N-2)}{2} \approx \frac{N^2}{2}$ for large $N$. Dividing by $3! = 6$ to account for the $x \le y \le z$ ordering gives roughly $\frac{N^2}{12}$. So we expect $\lim_{N \to \infty} f(N)/N^2 = 1/12$. The cases where two or more parts are equal -- like $(k, k, N - 2k)$ or $(k, k, k)$ -- are $O(N)$ in count, so they vanish in the $N^2$ limit.
Approach: Count all ordered triples, partition them by symmetry type, and take the limit.
Formal Solution:
Step 1: Count ordered triples.
The number of ordered triples $(x, y, z)$ of positive integers with $x + y + z = N$ is, by stars and bars:
$$T(N) = \binom{N-1}{2} = \frac{(N-1)(N-2)}{2}$$
Step 2: Classify by symmetry type.
Every ordered triple $(x, y, z)$ belongs to exactly one unordered multiset $\{x, y, z\}$. There are three cases:
- All distinct ($x < y < z$): each multiset generates $3! = 6$ ordered triples.
- Exactly two equal ($x = y < z$, or $x < y = z$, or $x = z$, etc.): each generates $3$ ordered triples.
- All equal ($x = y = z$): each generates $1$ ordered triple (only possible when $3 \mid N$, giving the single triple $(N/3, N/3, N/3)$).
Let $A$ = number of "all distinct" multisets, $B$ = number of "two equal" multisets. Then:
$$T(N) = 6A + 3B + [3 \mid N]$$
and
$$f(N) = A + B + [3 \mid N]$$
Step 3: Count $B$.
Triples with exactly two equal parts have the form $(k, k, N - 2k)$ with $k \ge 1$, $N - 2k \ge 1$, $N - 2k \ne k$. This gives $k$ ranging from $1$ to $\lfloor (N-1)/2 \rfloor$, minus $k = N/3$ if $3 \mid N$. So $B = O(N)$.
Step 4: Solve for $f(N)$.
From the two equations:
$$6A + 3B + [3 \mid N] = T(N) \implies A = \frac{T(N) - 3B - [3 \mid N]}{6}$$
$$f(N) = A + B + [3 \mid N] = \frac{T(N) - 3B - [3 \mid N]}{6} + B + [3 \mid N]$$
$$f(N) = \frac{T(N)}{6} + \frac{3B}{6} + \frac{5[3 \mid N]}{6}$$
$$f(N) = \frac{T(N)}{6} + \frac{B}{2} + O(1)$$
Step 5: Take the limit.
Since $T(N) \sim N^2/2$ and $B = O(N)$:
$$\frac{f(N)}{N^2} = \frac{T(N)/6}{N^2} + \frac{B/2}{N^2} + O(N^{-2})$$
$$\to \frac{1}{6} \cdot \frac{1}{2} + 0 = \frac{1}{12}$$
Answer:
$$\lim_{N \to \infty} \frac{f(N)}{N^2} = \frac{1}{12}$$
Intuition
The $1/12$ factor has a clean geometric interpretation. The solutions to $x + y + z = N$ with $x, y, z > 0$ live on a 2D simplex. As $N$ grows, the lattice points on this simplex become dense and their count approaches the simplex's area, which scales as $N^2$. Imposing $x \le y \le z$ cuts the simplex into exactly $3! = 6$ congruent regions (the Weyl chambers of the symmetric group acting on $\mathbb{R}^3$), so you keep $1/6$ of the total. The total ordered count is $\sim N^2/2$, and $1/6$ of that is $N^2/12$.
This type of argument -- count ordered objects, divide by symmetry, ignore lower-order boundary corrections -- comes up constantly in combinatorics and probability. The key discipline is knowing which corrections are lower-order. Here, ties are $O(N)$ while the main term is $O(N^2)$, so the ratio $f(N)/N^2$ is clean. In harder problems (e.g., partitions into parts with more constraints), the boundary corrections can be comparable in size and you need inclusion-exclusion or generating functions to handle them precisely.