Number of elements in discrete $n$-dimensional simplex such that $x_1 \leq \ldots \leq x_n$

Question

For positive integers $n,d$, how many elements are there in the set $S = \{(x_1,\ldots,x_n) \in \mathbb{Z}^n\ |\ 0 \leq x_1 \leq \ldots \leq x_n \wedge \sum_i x_i = d \}$?

I'm hoping that the order constraints on the $x_1,\ldots,x_n$ can be accounted for somehow by "adjusting" the figurate number, which gives the number of elements for an unconstrained discrete simplex. But I'm a bit out of my depth combinatorically.

Answer 1

Introduce change of variable

$$\begin{cases} x_1 &= y_1\\ x_2 &= y_1 + y_2\\ x_3 &= y_1 + y_2 + y_3\\ &\;\vdots\\ x_n &= y_1 + y_2 + y_3 + \cdots + y_n \end{cases}$$ We have $$\begin{array}{c} 0 \le x_1 \le x_2 \le x_n\\ \text{ and }\\ x_1 + x_2 + \cdots + x_n = d \end{array} \quad\iff\quad \begin{array}{c} y_1, y_2, \ldots, y_n \ge 0\\ \text{ and }\\ ny_1 + (n-1)y_2 + \cdots + y_n = d \end{array} $$ This means the number of solutions of $(x_k)$ satisfying LHS is the same as the number of solutions of $(y_k)$ satisfying RHS. Let us denote this number as $p(d,n)$.

For each solution of $(y_k)$ for the RHS, there is a corresponding partition of integer $d$ into parts whose part not exceeding $n$. i.e.

$$d = \overbrace{n + n + \cdots + n}^{y_1} + \overbrace{(n-1) + (n-1) + \cdots + (n-1)}^{y_2} + \cdots + \overbrace{1 + 1 + \cdots + 1 }^{y_n}$$

This correspondence is one to one. This means $p(d,n)$ equals to the number of ways of expressing integer $d$ as a sum of integers from the set $\{\; 1, 2, \ldots, n \;\}$. For fixed $n$, the generating function of latter is given by:

$$ \text{OCF}_n(t) \stackrel{def}{=} \sum_{d=0}^\infty p(d,n) t^d = \prod_{k=1}^n (1 + t^k + t^{2k} + t^{3k} + \cdots ) = \prod_{k=1}^n \frac{1}{1 - t^k} $$ I'm not aware of any formula of $p(d,n)$ for general $d$ and $n$. However, for small $n$, you can use these OGFs to derive formula for $p(d,n)$.

For example,

• $n = 1$,

$$\text{OCF}_1(t) = \frac{1}{1-t}\quad\implies\quad p(d,1) = 1.$$

• $n = 2$, $$\begin{align}\text{OCF}_2(t) &= \frac{1}{(1-t)(1-t^2)} = \frac{1}{2(1-t)^2} + \frac{1}{4(1-t)} + \frac{1}{4(1+t)}\\ &= \frac12 \sum_{d=0}^\infty (d+1)t^d + \frac14 \sum_{d=0}^\infty t^d + \frac14 \sum_{d=0}^\infty (-t)^d\\ \implies p(d,2) &= \frac{d+1}{2} + \frac{1+(-1)^d}{4} = \left\lfloor \frac{d}{2} \right\rfloor + 1 \end{align} $$
• $n = 3$, $$\begin{align} \text{OCF}_3(t) &= \frac{1}{(1-t)(1-t^2)(1-t^3)} = \frac{1/6}{(1-t)^3} + \frac{1/4}{(1-t)^2} + \frac{1/4}{1-t^2} + \frac{1/3}{1-t^3} \\ &= \frac16\sum_{d=0}^\infty \binom{d+2}{2} t^d + \frac14\sum_{d=0}^\infty (d+1) t^d + \frac14 \sum_{d=0}^\infty t^{2d} + \frac13 \sum_{d=0}^\infty t^{3d}\\ &= \sum_{d=0}^\infty\left( \frac{(d+3)^2}{12} t^d -\frac13 t^d + \frac14 d^{2d} + \frac13 d^{3d}\right)\\ &= \sum_{d=0}^\infty \left(\frac{(d+3)^2}{12} + \epsilon(d)\right) t^d\\ \implies p(d,3) &= \frac{(d+3)^2}{12} + \epsilon(d) \end{align} $$ where $\epsilon(d)$ takes only the values $-\frac13, -\frac{1}{12}, 0, \frac14$. Since $p(d,3)$ is an integer and $|\epsilon(d)| < \frac12$, we can further simplify and get $$p(d,3) = \left\{ \frac{(d+3)^2}{12} \right\} \quad\text{ where } \{ x \} \text{ is the nearest integer to } x. $$

There are formulas of $p(d,n)$ for other $n$. A good reference should be the book

• Integer Partitions, by George E. Andrews, Kimmo Eriksson.

Some of the formula here is copied from this book.