Given $n\geq 0, j\geq 1.$ How many solutions to: $\sum_{i=1}^j x_i=n,$ where $x_i\geq 0$ and $x_i$ are all different?

87 Views Asked by At

Given $n\in\mathbb{N}\cup\{0\},\ j\in\mathbb{N}.$ How many solutions are there to: $\sum_{i=1}^j x_i=n,$ where $x_i\in\mathbb{N}\cup\{0\}$ for all $i\in\{1,\ldots,j\}$ and $x_k\neq x_l$ if $k\neq l\ ?$

Without this restriction:

$x_k\neq x_l$ if $k\neq l,$

the stars and bars method gives the answer $\binom{j-1+n}{j-1},$ as explained in this answer.

I was wondering if some clever trick can answer my question with the restriction in place.

$x_1=2, x_2=0$ and $x_1=0, x_2=2$ are two different solutions. Although considering these to be the same would be another interesting question. But let's leave this question for another day...