# Combinatorics question based on ProjectEuler 606

## 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.

• A002033 does not contain a closed form based on factorization. – orlp Jun 13 '17 at 3:32

## 2 Answers

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.

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}$$