How many distinct lists of 14 integers $L=\{v_1,\ldots ,v_{14}\}$ exist satisfying $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$

Question

I am trying to solve the following problem: I have an ordered list of integers $L = \{v_1,\ldots ,v_{14}\}$ with fourteen elements, satisfying the following two conditions: $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$. So in particular every $0\leq v_i \leq 54$. How many different lists $L$ satisfying the conditions exists? Here is some background on the problem.

I am trying to solve something on the computer that boils down to the following problem: find the minimum number $n=p_1^{v_1}\cdot \ldots \cdot p_{k}^{v_k}$ (its prime factorization) such that $S(n)=\frac12\left(\prod _{i=1}^{k}(2v_i+1)+1\right)>1000000$. Now by the fact that $n$ is minimum we see that $v_i \geq v_{i+1}$. If not we would have something like $n = 2\cdot 3^2$ but $S(2\cdot 3^2) = S(2^2 \cdot 3)$ so if some $v_{i} \leq v_{i+1}$ we have not minimized $n$.

Now if we set all $v_i =1$ we get $n=p_1\cdot \ldots \cdot p_k$ and $S(n)=\frac12(3^k+1)>1000000$ or equivalently $3^k \geq 20000000 $ so that $k \geq \log_{3}(2000000) \approx 13.2$. So that for every number $n$ with a prime factorization of at least $14$ distinct primes we see that $S(n) > 1000000$. So, in order to minimize $n$ we look for a number $n$ that has a prime factorization of at most $14$ primes to some power. Also we see that $n$ has a prime factorization that includes not 14 random primes, but the first 14 primes. This is because we can swap primes in the factorization without changing $S(n)$ but this will change $n$, so we choose the smallest primes to minimize $n$. This is the reason the list has $14$ elements.

Now by the minimization of $n$ we see that our minimal $n$ is either equal to or smaller than $p_1\cdot p_2\cdot \ldots p_{14} = 2\cdot 3\cdot \ldots \cdot 43 \approx 1.3\cdot 10^{16}$. Also, for any $n$ we have $n = p_1^{v_1}\cdot \ldots \cdot p_{14}^{v_{14}}> 2^{\sum v_{i}}$ so that again by the minimization of $n$ we have $2^{\sum v_{i}} \leq 1.3\cdot 10^{16}$ implying that $\sum v_i \leq \log_2( 1.3\cdot 10^{16})\approx 53.5$. Thus $\sum v_i \leq 54$.

Thus we have set up the conditions specified at the beginning. Now this is as far as I got, I tried to look at the list $L$ as number base $55$ but this hasn't helped much. Also, I fear that the amount of possible lists is enormous but I am not sure. I am looking for a way to see how many there are and possible an algorithm to generate them in succession. Thanks in advance for any tips or help!

Answer 1

We consider a smaller case: $x_1 + x_2 + x_3 \le 5$. We look at all the of partitions of $1, 2, 3, 4, 5$ into at most $3$ parts. The possible partitions are:

1 = 1            (1, 0, 0)
2 = 2            (2, 0, 0)
  = 1 + 1        (1, 1, 0)
3 = 3            (3, 0, 0)
  = 2 + 1        (2, 1, 0)
  = 1 + 1 + 1    (1, 1, 1)
4 = 4            (4, 0, 0)
  = 3 + 1        (3, 1, 0)
  = 2 + 2        (2, 2, 0)
  = 2 + 1 + 1    (2, 1, 0)
5 = 5            (5, 0, 0)
  = 4 + 1        (4, 1, 0)
  = 3 + 2        (3, 2, 0)
  = 3 + 1 + 1    (3, 1, 1)
  = 2 + 2 + 1    (2, 2, 1)

Each of these partitions corresponding to an ordered solution for $(x_1, x_2, x_3)$. They also represent all the solutions that exist.

---

Essentially, what we're looking for in the context of the question is the total number of ways to partition $n$ into at most $14$ parts for $0 \le n \le 54$.

Define the number of ways to partition $n$ into $k$ parts as $p_k(n)$. Then, we need

$$\sum_{n = 0}^{54}\sum_{k = 0}^{14}p_k(n)$$

where $p_0(0) = 1$ and $p_k(n) = 0$ if either $k \le 0$ or $n \le 0$. From this link on Wikipedia, we have the following recurrence relation for $p_k(n)$:

$$p_k(n) = p_k(n-k) + p_{k-1}(n-1)$$

Below is a PARI-GP script that computes the required number of list using the aforementioned method:

partition(n, k) =
{
    if(n == 0 && k == 0, 
        1,
        if(n <= 0 || k <= 0,
            0,
            partition(n - k, k) + partition(n - 1, k - 1)
        )
    )
}

total = 0;
for(n = 0, 54, for(k = 0, 14, total += partition(n, k)));
print(total);

The script gives $1627035$ as the required number of lists.