# Finding the number of possible sequences(of any length)

Given $x$ & $y$. Count the number of distinct sequences $a_1, a_2, \dots, a_n$ $(\forall a_i \ge 1)$ consisting of positive integers such that $\gcd(a_1, a_2, \dots, a_n) = x$ and $\sum_{i=1}^n a_i =y$.

## 1 Answer

First, it is obvious that if $x\not | \ \ y$, then such sequence does not exist. Therefore we suppose $x | y$.

We first enumerate the number of positive sequences $a_1, \cdots, a_n$ such that $x|a_i$ for all $i$ and $\sum_{i=1}^n a_i = y$. By taking $a_i' = \frac{a_i}{x}$ for each $i$ this means a positive sequence $a_1', \cdots, a_n'$ such that $\sum_{i=1}^n a_i' = \frac yx$. It is a combinatoric fact that there are $p(x, y, n) := \binom{\frac yx - 1}{n-1}$ of them.

Note that among the sequences considered above, there are sequences with higher gcd. We denote by $g(x, y, n)$ the number of positive sequences $a_1, \cdots, a_n$ satisfying $\gcd(a_1, \cdots, a_n) = x$ and $\sum_{i=1}^n a_i = y$, then we know that

$$\sum_{\substack{{u > 0}\\{u | \frac yx}}} g(ux, y, n) = p(x, y, n)$$

By Möbius inversion formula, we see that

$$g(x, y, n) = \sum_{\substack{{u > 0}\\{u | \frac yx}}} \mu(u) p\left(ux, y, n\right) = \sum_{\substack{{u > 0}\\{u | \frac yx}}} \mu(u) \binom{\frac{y}{ux}-1}{n-1},$$

where

$$\mu(u) = \begin{cases} 0, &\mbox{if } u \mbox{ is not square free};\\ (-1)^{\omega(u)}, &\mbox{if } u \mbox{ is a product of } \omega(u) \mbox{ distinct primes}, \end{cases}$$

is the Möbius function.