Combinatorics question based on ProjectEuler 606

Question

Motivation

The following text is from Problem 606 from Project Euler :

A gozinta chain for $n$ is a sequence $\{1,a,b,...,n\}$ where each element properly divides the next. For example, there are eight distinct gozinta chains for $12$: $$\{1,12\}, \{1,2,12\}, \{1,2,4,12\}, \{1,2,6,12\}, \{1,3,12\}, \{1,3,6,12\}, \{1,4,12\},\{1,6,12\}.$$ Let $S(n)$ be the sum of all numbers, $k$, not exceeding $n$, which have $252$ distinct gozinta chains. You are given $S(10^6)=8462952$ and $S(10^{12})=623291998881978$. Find $S(10^{36})$, giving the last nine digits of your answer.

Given a number $n\in \mathbb N$ we can write its prime factorization $n=p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}$.

Every gozinta chain $(z_1=1,z_1,\ldots,z_{r-1},z_r=n)$ of length $r$ for $n$ can be built as $$\begin{align} z_r=& p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}\\ z_{r-1}= & p_1^{k_1-t^{(r-1)}_{1}}\cdot\ldots\cdot p_m^{k_m-t^{(r-1)}_{m}}\\ &\vdots\\ z_1 = & p_1^{k_1-\sum_{j=1}^{r-1}t^{(j)}_1}\cdot\ldots\cdot p_m^{k_m-\sum_{j=1}^{r-1}t^{(j)}_m}\\ z_0 =&p_1^{k_1-\sum_{j=0}^{r-1}t^{(j)}_1}\cdot\ldots\cdot p_m^{k_m-\sum_{j=0}^{r-1}t^{(j)}_m}=1 \end{align} $$ through the backward recursion $$z_{s-1}=\frac{z_s}{p_1^{t_1^{(s-1)}}\cdot\ldots\cdot p_m^{t^{(s-1)}_m}}$$ with the tuples $(t_1^{(0)},\ldots,t_m^{(0)}),\ldots,(t_1^{(r-1)},\ldots,t_m^{(r-1)})$ satisfying the two constraints

$$ \begin{align} \sum_{j=0}^{r-1}t_\nu^{(j)}&=k_{\nu} && \forall \nu=1,\ldots, m\tag{1}\\ (t_1^{(j)},\ldots,t_m^{(j)})&\neq(0,\ldots,0) && \forall j=1,\ldots r\tag{2} \end{align}$$

The Problem

I would like to understand more about the function $\alpha((k_1,\ldots,k_m))$ that associates the number of gozinta chains for $n$ to the multiplicities of $n$'s prime factors.

---

Remark 1: We could try to enumerate the tuples satisfying $(1),(2)$. For instance, if one supposes $m=1$, (i.e. $n=p^k$) the problem is equivalent to asking how many ordered partitions of $k$ exist. It is well known that such number is $2^{k-1}$. Then $\alpha(k)=2^{k-1}$ for $k>0$. The problem of enumerating tuples satisfying $(1),(2)$ could be seen as a generalization of integer partitioning to $m$-tuples.

---

Remark 2: The problem could be modelled combinatorially in the following way. Suppose we have $m$ bins with $k_1,\ldots, k_m$ balls. At each of our $r-1$ turns we must extract at least one ball. At the last turn ($r-1$) we must have removed all of the balls from the bins. In how many different ways can we do this without fixing the length of the game?

---

Question

Is there a known answer in the literature to the above mentioned combinatorics problem? I would expect either

1. A reference following the idea of Remark 1, essentially correlating the result to ordered partitions of $m$-tuples. I am unaware of such results and have been able to find results only relative to ordered partitions of integers.
2. A combinatorial approach following Remark 2.

I probably have used nonstandard notation as I am not familiar with the subject.

---

Note: I published this question even though it refers to a Project Euler question following guidance from this meta answer.

Answer 1

For a prime power, as you say, you get $2^{k-1}$.

Another way to view this is the number of walks from $0$ to $k$, where you can only go forwards and stop on integer points. You can choose to stop on point $1, 2, \dots, k-1$, giving $2^{k-1}$ options.

What about $n = p^k q^l$? Well, this is the number of walks from $(0, 0)$ to $(k, l)$ where you can only move in the positive direction and stop on the integer lattice. This is A059576. Or:

$$f(k, l) = \sum_{j=0}^{n+k} C(n,j-k+1)\cdot C(k,j-n+1)\cdot 2^j$$

Where $C$ are the Catalan numbers.

For more distinct primes we are essentially looking at the number of $m$ dimensional walks from $(0, \dots, 0)$ to $(k_1, \dots, k_m)$ with nonnegative integers steps. It's fairly easy to answer that question with dynamic programming, but I'm not aware of any closed forms.

Answer 2

It's often easier to tackle this kind of question with an extra parameter. Let's follow route 2. Let $\alpha(n, k)$ be the number of gozinta chains for $n$ which have $k$ elements other than the initial $1$.

For prime powers, $\alpha(p^a, k) = \binom{a-1}{k-1}$ by a stars and bars argument.

Now, suppose we are given $m$ and $\alpha(m, i)$ for all $i$, and we want to find $\alpha(m q^b, k)$ where $q$ is prime and coprime to $m$. For any given gozinta chain, some of the $k$ turns will take balls from the urns corresponding to $m$ and some will take balls only from the urn corresponding to $q^b$. Suppose that on $1 \le j \le k$ turns we take balls from urns corresponding to $m$. We can interleave those $j$ turns with $k-j$ turns in which we take $1$ ball from the urn corresponding to $q^b$ in $\binom{k}{j}$ ways, and we are left with $b-(k-j)$ balls to distribute freely among the $k$ turns, which can be done in $\binom{b+j-1}{k-1}$ ways by stars and bars. Then $$\alpha(mq^b, k) = \sum_j \alpha(m, j) \binom{k}{j} \binom{b+j-1}{k-1}$$