
4. Find the number of finite increasing sequences of natural numbers $a_{1}, a_{2}, \ldots, a_{k}$, of all possible lengths $k$, for which $a_{1}=1, a_{i} \mid a_{i+1}$ for $i=1,2, \ldots, k-1$, and $a_{k}=969969$.


Solution. Clearly all members of the sequence must be divisors of its last member, 969 969. Using the decomposition into prime factors,

$$
969969=3 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \text {. }
$$

we thus see that the following holds:

Each member $a_{i}$ of the sequence $a_{1}, a_{2}, \ldots, a_{k}$ is the product of some (for $i=$ 1 -of none, for $i=k$ - of all) of the six distinct primes in the decomposition (1); furthermore, (for $i<k$ ) the member $a_{i+1}$ has, in addition to all the prime factors of $a_{i}$, also at least one new prime factor (since the sequence is to be increasing!). Conversely, each such finite sequence satisfies the conditions of the problem.

From here it follows how one can describe each such sequence in an "economical manner": it is enough to list the new factors as they are turning up, that is, to give the sequence of ratios

$$
\frac{a_{2}}{a_{1}}, \frac{a_{3}}{a_{2}}, \frac{a_{4}}{a_{3}}, \ldots, \frac{a_{k-1}}{a_{k-2}}, \frac{a_{k}}{a_{k-1}}
$$

into whose prime factorizations the six primes from (1) are distributed (at least one prime in each). The desired number of sequences is thus equal to the number of ways the six given primes can be distributed into one or several numbered nonempty groups (each corresponding to the prime factors of the ratios in (2), hence the order of the primes in a group is irrelevant). The word "numbered" means that the order of groups, on the other hand, does matter. For instance, for the distribution into two groups $\{3,11,19\}$ and $\{7,13,17\}$ we get, depending on the order in which the groups are considered, two possible sequence $(1, u, u v)$ and $(1, v, u v)$, where $u=3 \cdot 11 \cdot 19$ and $v=7 \cdot 13 \cdot 17$.

We have thus arrived at the combinatorial problem of determining the value of $P(6)$, where $P(n)$ denotes the number of ways an $n$-element set $X$ can be partitioned into any number of "numbered" nonempty subsets $X_{1}, X_{2}, X_{3}, \ldots$ To compute $P(6)$ we use the recurrence relation

$$
P(n)=\left(\begin{array}{l}
n \\
1
\end{array}\right) P(n-1)+\left(\begin{array}{l}
n \\
2
\end{array}\right) P(n-2)+\cdots+\left(\begin{array}{c}
n \\
n-1
\end{array}\right) P(1)+1
$$

valid for any $n \geqslant 2$, which we now proceed to prove.

We divide the desired partitions of the $n$-element set $X$ into $n$ groups according to the number $j$ of elements in the first subset $X_{1}(1 \leqslant j \leqslant n)$. This first subset $X_{1}$, having $j$ elements, can be chosen in exactly $\left(\begin{array}{l}n \\ j\end{array}\right)$ ways, and then the remaining set $X^{\prime}=X \backslash X_{1}$ can be partitioned into nonempty numbered subsets $X_{2}, X_{3}, X_{4}, \ldots$ in $P(n-j)$ ways. (This holds even for $j=n$, when we set $P(0)=1$, since there is nothing already left to partition.) The number of desired partitions of $X$ whose first set $X_{1}$ consists of exactly $j$ elements is thus equal to $\left(\begin{array}{l}n \\ j\end{array}\right) P(n-j)$, and the formula (3)
already follows (the last term 1 on the right-hand side of (3) corresponds to the case of $j=n$ ).

From the obvious value $P(1)=1$ we thus compute by (3), in turn, $P(2)=3$, $P(3)=13, P(4)=75, P(5)=541$ and $P(6)=4683$.

Conclusion. There exist exactly 4683 such sequences.
