Number of $n-$ tuples forming a decreasing sequence.

Question

Problem Statement: Let $n\geq 2$ be a natural number. We are interested in sequences $(x_1,x_2,...,x_n)$ of natural numbers such that $$x_1+x_2+...+x_n = x_1x_2...x_n\text{ and }x_1\leq x_2\leq...\leq x_n.$$ Let $A(n)$ denote the set of all such sequences. Moreover, we denote by $a(n)$ the cardinality of the set $A(n).$ The goal is to generate $a(n)$ for $n\geq 2.$ However, at the moment I am just trying to understand how many non-decreasing sequences I have to check in order to understand the time complexity of a naive algorithm which checks over all the possible sequences. Now it has been shown that for all $n\geq 2$ if $(x_1,x_2,...,x_n)\in A(n)$ then $$\sum_{i=1}^{n}x_i\leq 2n.$$ So I am assuming that each $x_i$ ranges from $1$ to $2n.$ My question is how many non-decreasing tuples do I have to check in order to find $(x_1,x_2,...,x_n)\in A(n)?$

Answer 1

Hint: the number of solutions to $1\le x_1\le x_2\le\cdots \le x_n\le k$ is the same as the number of solutions to $$ 1\le x_1 < x_2+1 < x_3+2 < \cdots < x_n+(n-1) < k+n.$$