Number of $(\lambda_1,\cdots,\lambda_n)$ such that $\operatorname{lcm}(\lambda_1,\cdots,\lambda_n)=160$

Question

Recently, I have found this problem:

Find the number of $n$-tuples of integers $(\lambda_1,\cdots\lambda_n)$ with $n\neq1$, $\lambda_i\neq\lambda_k \;\forall i,k\leq n$ and $\lambda_i\neq1$ such that: $$\operatorname{lcm}(\lambda_1,\cdots,\lambda_n)=160$$

In order to solve this problem, I factor the number $160$ into: $160=2^5\cdot5$. Now, I list all possible divisors of $160$ without $1$: $$\mathcal{D}=\{2, 4, 5, 8, 10, 16, 20, 32, 40, 80, 160\}$$ The numbers $\lambda_i$ has to be in this set because, if not, the $\operatorname{lcm}(\lambda_1,\cdots,\lambda_n)$ can't be equal to $160$. There are also some sets for which the $\operatorname{lcm}(\lambda_1,\cdots,\lambda_n)$ is not $160$, for example $(2,20)$, so we have some possibilities.

If in a set there is $160$ then all possible other values for $\lambda_i$ are correct. If in a tuple there are the numbers $(32,5),(32,10),(32,20),(32,40),(32,80)$ then all other $\lambda_i$ are correct.

But how can we count all the $n$-tuples?

I think this problem is related with Bell's numbers because, for example, in order to find the number of tuples with $160$ we have to partitionate $\mathcal{D}-\{160\}$.

Answer 1

To get idea of how to build i will start from $n=2$:

As you said there are 5 possible couples which are $(32,5),(32,10),(32,20),(32,40),(32,80)$

Now let $n=3$

First of all we always need atleast $32$ in first element( i will arrange them after). At second element we need a $5,10,20,40$ or $80$. The third one can be anything in $\mathcal{D}-\{160\}$ but distinct from first two elements, so there are $9$ options. Finally we have $1.5.9.(3!)$ (3 stands for arranging) possible triples.

There are $1.5.9.8.(4!)$ possible quadruples and so on.

To generalize we can write:

$$\sum_{i=2}^{10} 5.P(8,i-2).i!$$

Answer 2

If we arbitrarily pick $n$ divisors of $160$ then the terms we pick will have $\operatorname{lcm}$ equal to $160$ if and only if one of the terms is divisible by $5$ and if one of the terms is divisible by $32$.

So by inclusion exclusion we get the $n$tupples with $\operatorname{lcm}$ equal to $160$.

total number of $n$ tuples - $n$ tuples with no multiples of $5$ - $n$ tuples with no multiples of $32$ + $n$tuples with no multiples of $32$ or $5$.

Now if $F(n)=$ number of ways to pick any number of different items (in order) from $n$ items then we have

$F(11) - F(5) - F(9) + F(4)$.

So we have to figure out $F(n)$. That number of $2$tuples is $n\times n-1=\frac {n!}{(n-2)!}= P(n,2)$ and we can have $2,3,...n$ tuples so $F(n) =\sum_{k=2}^n P(n,k)=n!(1 + \frac 1{2!} + .... + \frac 1{(n-1)!})$

Which seems very calucation intensive. We can incorporate the gamma function ( See this question what is the sum of following permutation series $nP0 + nP1 + nP2 +\cdots+ nPn$? ) but that seems like over kill.

So we have

$10*11 + 9*10*11 + ...... + 2*3*...*11 + 11! - 8*9-7*8*9 -....- 9! - 4*5-3*4*5 - 2*3*4*5 - 5! + 3*4+2*3*4 + 4!$ which...

There's got to be an easier way....

....

Answer 3

Let's split it into two cases.

Case 1: $160$ is in the tuple. The other $n-1$ numbers can be chosen freely from the remaining $10$ non-trivial divisors in $\mathcal{D}-\{160\}$, so you have $\binom{10}{n-1}$ possible choices of the numbers. Since it is an ordered tuple, you then need to multiply this by $n!$ for all possible orderings of the $n$ distinct numbers in the tuple.

Case 2: $160$ is not the tuple. In this case you need to have $32$, and in the remaining $n-1$ numbers must include at least one multiple of $5$. There are $\binom{9}{n-1}$ to choose $n-1$ distinct numbers from $\mathcal{D}-\{32,160\}$. But we need to exclude the $\binom{4}{n-1}$ ways of not including any multiple of $5$ (i.e. choosing $n-1$ elements of $\{2,4,8,16\}$). So this gives $\binom{9}{n-1}-\binom{4}{n-1}$ ways of selecting the numbers, and this again needs to be multiplied by $n!$ for the different orderings.

This gives a total of $$n!({\binom{10}{n-1}+\binom{9}{n-1}-\binom{4}{n-1}})$$

Note that this assumes the convention that $\binom{a}{b}=0$ when $a<b$.

Answer 4

By inclusion-exclusion principle, the answer we want is $$ N_{160}-N_{80}-N_{32}+N_{16} $$ where $N_m$ is the number of $n$-tuples of distinct numbers from $\{2,4,5,8,10,\dots,160\}$ with lcm dividing $m$.

Now $N_{160}$ is just the number of ways to select $n$ numbers from this set of non-1 divisor of 160, so is $\binom{11}{n}\cdot n!$. By similar reasoning, you can find the other $N$s and hence obtain the answer.

Answer 5

Hint:

I would do it in the following elementary way:

As $160=2^5\cdot5^1 $, the $\lambda_i$s can have only $2$ and $5$ as prime factors, so denote $$\lambda_i=2^{r_i}\cdot 5^{s_i}\qquad (0\le r_i\le 5,\;0\le s_i\le1,\;i=1,\dots,n).$$ As $\;\operatorname{lcm}(\lambda_1,\dots,\lambda_n)=2^{\max\limits _i r_i}5^{\max\limits _i s_i}$, we only need to determine the number of distinct pairs $(r_i,s_i)$ that satisfy these relations and such that $\;\max\limits_ir_i=5$, $\;\max\limits_is_i=1$.

The shortest way will consist in counting first the number of pairs which do not satisfy one of the conditions on the $\max$.