My goal is to find, in any arbitrary dimension, how many linear independent vectors there are in the set made of all of the possible vectors in N whose components sum to a fixed value.

$$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$$

given the defintion of $A$, the number of all possible vectors in the 2-dimensional case is $x(x-1)/2$, if $c=4$ then $A=\lbrace \\ (0,0)(0,1)(0,2)(0,3)(0,4)\\ (1,0)(1,1)(1,2)(1,3)\\ (2,0)(2,1)(2,2)\\ (3,0)(3,1)\\ (4,0)\rbrace$

For my purpose i would like to know which vectors are not multiples of other vectors in terms of tuple values. Where $(2,2)$ is a multiple of $2\cdot(1,1)$ as my interested in the ratio between the values, $(0.5,0.5)$ in this case or ratio of (0,1) for $(0,1),\ldots,(0,x)$. But i'm not interested in knowing that $(2,1) = 2\cdot(1,0)+(0,1)$

is it possible to deduce a general formula?

  • $\begingroup$ I have to say I am lost. I'm not sure what you are asking - is it for the number of "n-"tuples which form the equivalent of a "basis" in a vector space. And do you want the sum equal to a fixed value, or $\le$ a fixed value, as in the table. $\endgroup$ Jul 4, 2013 at 20:19
  • $\begingroup$ Sorry for not being so clear, what i have to do is to determine for example, given a space dimension and the constraint of sum of components less or equal to a constant, all of the vectors which are not multiple of other vectors in terms of tuple's values. $\endgroup$
    – fady
    Jul 4, 2013 at 20:58

1 Answer 1


If I understand correctly, you're looking for a basis of $$\left\langle \left(\begin{array}{c}a_0\\a_1 \\ \vdots \\ a_n\end{array}\right): a_i\in \mathbb{Z}\hspace{5pt}\left| \hspace{5pt}\sum a_i=\sigma\right.\right\rangle$$ where $\sigma$ is some fixed integer.

Take $\sigma\cdot\epsilon_i$ for $i=1,\ldots, n$, where $\epsilon_i$ is the unit vector with a $1$ in the $i^\text{th}$ coordinate and $0$s elsewhere. It's easy to see that all of these are members of your desired set, and that they span $\mathbb{Q}^n$ (or $\mathbb{R}^n$, whichever vector space you're in). So the dimension of this space is $n$.

  • $\begingroup$ I think what you are referring to is the fact that given the basis i can obtain all the other vectors as a linear combination of the basis itself. What i'm looking for is find vectors whose tuple's values are multiple of other vectors. $\endgroup$
    – fady
    Jul 5, 2013 at 15:41
  • $\begingroup$ @fady then that isn't what linearly independent means. $\endgroup$
    – Alexander Gruber
    Jul 5, 2013 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .