In basic combinatorics, one learns how to count the number of ways to partition a natural number n into a certain number of pieces; e.g., let $n \in \mathbb{N}$. For some $m < n$, how many ways can we write $x_1+x_2+ \cdots + x_m=n$, where $x_i \in \mathbb{N}$ for $i \in \{1, \ldots, n\}$? Reinterpreting the problem as seeking the number of ways to put $m$ spaces somewhere within a sequence of $n$ objects, we see that the answer is

$$n \choose m$$

I am trying to count such partitions in a related manner: I fix $m, n \in \mathbb{N}$, but then I also fix $a_i \in \mathbb{N}$, for $i \in \{1, \ldots, n\}$. Now, rather than counting the number of ways to write


I wish instead to count the number of ways to write


where again the $x_i$ are in $\mathbb{N}$. The $a_i$ are allowed to equal each other, but they must be natural numbers. So this is a linear combination on a multiset of vectors (the $a_i$) where every vector must be used.

This feels like it should be a fairly straightforward generalization of the simple counting method described above, but I can't seem to nail it down. Any thoughts on how to solve this or suggestions of where to read up on similar questions would be greatly appreciated.

  • $\begingroup$ Perhaps looking into results regarding Numerical Semigroups might help? In the context of numerical semigroups, each way of expressing $n$ as a linear combination of the $a_i$'s is called a factorization of $n$ so such a problem is equivalent to counting the number of factorizations of $n$ generated by a semigroup whose generators are the $a_i$'s. $\endgroup$ – benguin Sep 11 '16 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.