How to calculate the number of vector not multiple of other in $\mathbb{N}$.

Question

I want to determine the number of vectors that are multiple of other vectors given the following constraints. $$A= \lbrace(x_0,x_1, \ldots, x_n): x_i\in \mathbb{N}\hspace{5pt}\left| \hspace{5pt}\sum x_i\leq c\right. \rbrace$$

With a vector multiple of another i mean $$v,u \in A, ~\exists ~x \in \mathbb{N} ~|~u = x\cdot v $$ Let's say i have $c=1$, in this case I would just have $ \lbrace(0,0),(0,1),(1,0)\rbrace$ in which all vectors are unique. I thought about doing this iteratively and look for $c=2$ which has $ \lbrace(0,0),(0,1),(0,2),(1,0),(1,1),(2,0)\rbrace$, here we have 3+1 unique elements, 3 from the previous step, and also (1,1). (0,2) and (2,0) are respectively multiples of (0,1) and (2,0), for example $(2,0)=2\cdot(1,0)$.

I kept trying for a while and I realized that maybe i can get the number of vectors which are not multiple of other counting how many elements in $A$ have all of the $x_i$ components co-prime.

Is this intuition right? and is there a general formula to count them other then iteratively calculate the result, that can be extended to more dimensions?

Answer 1

Only some beginning thoughts.

Let's formalize a bit. Let $A_{n,c}$ be the set of all $n$-tuples of natural numbers with component sum less than or equal to $c$:

$$A_{n,c}=\{(x_1,\ldots,x_n)\in\mathbb{N}^n\mid\sum x_i\le c\}$$

Let $B_{n,c}\subset A_{n,c}$ be those $n$-tuples whose greatest common divisor is $1$:

$$B_{n,c}=\{(x_1,\ldots,x_n)\in A_{n,c}|\gcd(x_1,\ldots,x_n)=1\}$$

The question asks for $|B_{n,c}|$. Here are some preliminary calculations for $n=2$:

$$|B_{2,0}|=1\\|B_{2,1}|=3\\|B_{2,2}|=4\\|B_{2,3}|=6\\|B_{2,4}|=8\\|B_{2,5}|=12\\\vdots$$

This is actually A225531. There is a link that calculates all values for $c\le 400$, but they don't give a general formula.

For $n=3$, I've found the sequence begins with $1,4,8,17,32,47,74$, but this doesn't show up in OEIS. If we let $a_c$ be the number of partitions of $c$ into $2$ or $3$ parts of distinct and relatively prime size, and $b_c$ be the number of partitions of $c$ into $3$ parts of relatively prime size, $2$ of the same size and $1$ a different size, then we have the following recursion:

$$|B_{3,c}|=|B_{3,c-1}|+6a_c+3b_c$$

Of course, this might not make things any easier because we have to calculate $a_c$ and $b_c$, and then resolve the recursion. However, a method like this would generalize to higher dimensions.