Divisible Sequences

As proved here , the number of solutions of $0 \leq a_{1} \leq a_{2} \leq a_{3} \leq \dots \leq a_{m} \leq a$ over integers is ${m+a \choose a}$

Now, clearly as the sequence starts with 360, first number is 360. We have to select 4 divisors of 360 now.

$360 = 2^3 3^2 5$

Let the exponents of 2 in the required four numbers be $a_{1}, a_{2}, a_{3},$ and $a_{4}$ respectively.

Now, as the numbers are part of divisible sequence,

$0 \leq a_{1} \leq a_{2} \leq a_{3} \leq a_{4} \leq 3$ .

Hence, ${7 \choose 3}$ ways.

Similarly, for choosing exponents of $3$ , there are ${4+2 \choose 2} = {6 \choose 2}$ ways, and for choosing exponents of 5 in the numbers is ${4+1 \choose 1} = {5 \choose 1}$ ways.

Hence, total number of such sequences possible is ${7 \choose 3}{6 \choose 2}{5 \choose 1} = 2625$

We first note that $360=2^3\cdot 3^2\cdot 5$ .

Let's define the sequence of numbers to be $n_0,n_1,n_2,n_3,n_4$ . Let $a_k$ be the exponent of $2$ on the number $\dfrac{n_{k-1}}{n_k}$ , let $b_k$ be the exponent of $3$ on the number $\dfrac{n_{k-1}}{n_k}$ , and let $c_k$ be the exponent of $5$ on the number $\dfrac{n_{k-1}}{n_k}$

Clearly, $a_1+a_2+a_3+a_4\le 3$ , $b_1+b_2+b_3+b_4\le 2$ , and $c_1+c_2+c_3+c_4\le 1$ ; also, all of the $a_1,a_2,\cdots c_3,c_4$ are all non-negative integers. Thus we just need to count the number of possible ways for each of the three above cases, and multiply them together.

Case 1: $a_1+a_2+a_3+a_4\le 3$

Let $a_5$ be a number such that $a_1+a_2+a_3+a_4+a_5=3$ . We now use sticks and stones to determine that the number of ways for this to happen is $\binom{7}{3}=35$ .

Case 2: $b_1+b_2+b_3+b_4\le 2$

Let $b_5$ be a number such that $b_1+b_2+b_3+b_4+b_5=2$ . We now use sticks and stones to determine that the number of ways for this to happen is $\binom{6}{2}=15$ .

Case 3: $c_1+c_2+c_3+c_4\le 1$

Let $c_5$ be a number such that $c_1+c_2+c_3+c_4+c_5=1$ . We now use sticks and stones to determine that the number of ways for this to happen is $\binom{5}{1}=5$ .

Thus our final answer is $35\times 15\times 5=\boxed{2625}$ .

Let $S_n=1+2+...+n$

The answer to this problem is

$(S_2+2S_1)(S_3+2S_2+3S_1)(S_4+2S_3+3S_2+4S_1)=5\times15\times35=2625$

---

Tools needed :

• Divisors of an Integer

In my solution, I will use $10$ instead of $360$ for clearer explanation

Analyse :

Prime Factorization : $10=2\times5$

Divisors of 10: $d(10)=(1+1)(1+1)=4$

Solution :

Number of Divisible Sequence of length 2,

This will just be the number of sequence of $10$ , which is $(2)(2)=4$ .

Number of Divisible Sequence of length 3,

The second term (counted backwards) can change to other divisors of $10$ , so there will be

$(2)(2)+(2)(1)+(1)(2)+(1)(1)=(1+2)(1+2)$ sequences.

Number of Divisible Sequence of length 4,

The third term (counted backwards) can also change to other divisors of $10$ , so there will be

$(1+2)(1+2)+(1+2)(1)+(1)(1+2)+(1)(1)=(1+2+1)(1+2+1)$ sequences.

Number of Divisible Sequence of length 5,

The forth term (counted backward) can also change to other divisors of $10$ , so there will be

$(1+2+1)(1+2+1)+(1+2+1)(1)+(1)(1+2+1)+(1)(1)=(1+2+1+1)(1+2+1+1)=25$ sequences.

---

I hope you can derive the answer yourself from this solution, good luck!

For generality, let $n=5$ be the length of the divisible sequence $a_1,\:\ldots,\: a_n$ and let $a_1:=360=2^3\cdot 3^2\cdot 5^1=:p_1^{n_1}\cdot\ldots\cdot p_m^{n_m}$ . The number of divisible sequences of length $n$ given $a_1$ shall be called $N$ .

---

Each element in the sequence divides the previous element, thus all elements are divisors of $a_1$ and share the same prime factors $\begin{aligned} a_k&=p_1^{b_{1k}}\cdot\ldots\cdot p_m^{b_{mk}},&&&1\leq k&\leq n \end{aligned}$ Once again because each element in the sequence divides the previous element, the exponents $b_{ik}$ must be decreasing, non-negative sequences (though not necessarily strictly decreasing): $\begin{aligned} n_i=b_{i1}&\geq \ldots\geq b_{in}\geq 0,&&&1\leq i&\leq m&&&&(*) \end{aligned}$ Note that any different sequence of exponents $b_{ik}$ leads to a different divisible sequence - we only need to count the number of different sequences for each exponent and multiply them together!

---

Let's consider a sequence of exponents $(*)$ . How can we generate such a sequence? The elements may decrease by different amounts each step, that makes it seem rather arbitrary.

Let's try a stars-and-bars approach : Think of the elements as bins, denote a decrease by $-1$ by a star and greater decreases by multiple stars. We see that our problem has been reduced to placing $n_i$ identical stars into $n$ distinct bins, leading to $\begin{aligned} \binom{n-1+n_i}{n-1}&\text{ different sequences}&\Rightarrow&&N&=\prod_{i=1}^m\binom{n-1+n_i}{n-1} \end{aligned}$

---

The number of divisible sequences of length $n=5$ given $a_1=360=2^3\cdot 3^2\cdot 5^1$ is $N=\binom{4+3}{4}\cdot\binom{4+2}{4}\cdot \binom{4+1}{4}=\boxed{2625}$

So I was wondering how to simply generate the sequences from 360-X1-X2-X3-X4-X5.... but faced combinatoric insanity that I simply couldn't deal with.

I then wondered what would happen if I started at the end and worked my way back to the solution,and how many ways to get to the start from the end. These problems are usually easier to think of that way. What are the possible ending numbers?

Subsets of 360 = (2^3* 3^2 *5), such as 2 * 3 * 5, 4 * 3 * 5, 1 * 1 * 1(all exponents zero). I then need to work my way up to 360 by placing multiples between the end divisor, and intermediate divisors, and the final number. After each factor(s) I add, I reach a higher number that will be a divisor of 360.

Or. How many ways can I place the factors needed to reach 360 from the end divisor, in the gaps between numbers where the step-ups go.

360 _ X1 _ X2 _ X3 _ End Divisor.

This is thus a stars and bars problem for each different end divisor. How many ways can you place the 2's to get up to 360, multiply by the number of ways to place the remaining 3's, and the remaining 5.

Now one can simply plug in the formula for stars and bars with a sum for each divisor, making this a triple sum.

$LaTeX$

Thankfully this sum is easy, each component of the sum can be done separately and multiplied, thus the sum is

(That's where I need a nice formula for adding up closely related combination sums...)

Use sage

sage: s = 0
sage: for a in divisors(360):
....:     for b in divisors(a):
....:         for c in divisors(b):
....:             s += len(divisors(c))
....:             
sage: s
2625

First of all, it is important to note that $360=2^{3} \times3^{2} \times5$

Now, let us make 5 boxes: A, B, C, D and E.

We shall insert all the prime factors into these five boxes to represent the divisible sequences.

The rule here is that the first number in the sequence = $1 \times$ the numbers in box A (if there is no number in a box, then we just assume it is a 1 in the box).

The second number in the sequence = $1 \times$ the numbers in box A $\times$ the numbers in box B

And so on and so forth, so that the fifth and final number in the sequence = $1 \times$ the numbers in box A $\times$ the numbers in box B $\times$ the numbers in box C $\times$ the numbers in box D $\times$ the numbers in box E

In this way, since all the prime factors of 360 are in the boxes, the final number must be 360.

As we can see, the sequences created by this method will be the reverse of the sequences required by the question, but we can just reverse the sequences at the end.

We have 6 elements to put into the 5 boxes: three 2's, two 3's and one 5.

Either the 2's can all be put into separate boxes, or two into one box and one into another, or all three into one box.

Either both 3's are put into one box, or they are put into two separate boxes.

So, there are six scenarios, let us consider each one in turn.

*In the calculations, the first figure refers to the number of possibilities for the 2's, the second for the 3's, and the third for the 5's.

$1$ . All three 2's are placed into separate boxes and both 3's are placed into separate boxes.

${5 \choose 3} \times {5 \choose 2}\ \times {5 \choose 1} = 500$

$2$ . All three 2's are placed into separate boxes and both 3's are placed into the same box.

${5 \choose 3} \times {5 \choose 1}\ \times {5 \choose 1} = 250$

$3$ . Two 2's are placed into the same box and the other 2 into another box, and both 3's are placed in separate boxes.

$\left( \left( \begin{matrix} 5 \\ 2 \end{matrix} \right) \times \quad 2! \right) \times {5 \choose 2}\ \times {5 \choose 1} = 1000$

The reason we multiplied the first figure by 2! is because the combinations are distinct i.e. having two 2's in box A and one 2 in box B is not the same as having one 2 in box A and two 2's in box B.

$4$ . Two 2's are placed into the same box and the other 2 into another box, and both 3's are placed in the same box.

$\left( \left( \begin{matrix} 5 \\ 2 \end{matrix} \right) \times \quad 2! \right) \times {5 \choose 1}\ \times {5 \choose 1} = 500$

$5$ . All three 2's are placed into the same box and both 3's are placed into separate boxes.

${5 \choose 1} \times {5 \choose 2}\ \times {5 \choose 1} = 250$

$6$ . All three 2's are placed into the same box and both 3's are placed in the same box.

${5 \choose 1} \times {5 \choose 1}\ \times {5 \choose 1} = 125$

So the total number of possibilities is $500+250+1000+500+250+125=2625$

Instead of thinking of 3, , , , I though of 3, , , , ,0 then write the differences so 3,2,2,1,0,0 gives 1,0,1,1,0 and this always has to sum to 3 so there are 7c4 ways. It follows that the answer is 7c4 6c4 5c4=2625