Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm studying a simple counting problem like this:

Given a positive integer $w$ and a collection of positive integers $P = \{p_0 ... p_n\}$ count the number of solutions to $$(p_0 a) + (p_1 b) + \cdots + (p_n z) \leq w.$$

What general category of mathematics does this type of problem belong to?

Perhaps discrete math or combinatorics?

share|cite|improve this question
Also Diophantine equations. This is related to the Frobenius coin problem. – J. M. Nov 22 '11 at 19:12
up vote 4 down vote accepted

You can solve this problem by using generating functions:

Let $f(m)$ be the number of partitions of $m$ involving the integers in $P=\{p_0,\dots,p_n\}$. This is the coefficient of $x^m$ in the series:

$$F = \prod\limits_{p_i \in P} \frac{1}{1-x^{p_i}} = (1+x^{p_0}+x^{2p_0}+\cdots)(1+x^{p_1}+x^{2p_1}+\cdots)\cdots(1+x^{p_n}+x^{2p_n}+\cdots)$$

Then your count is $C = \sum\limits_{m=0}^w f(m)$

Example: Let $P=\{1,3\}$. Then $F = (1+x+x^2+\cdots)(1+x^3+x^6+\cdots) = 1+x+x^2+2x^3+2x^4+2x^5+3x^6+\cdots$

So $f(0)=1$, $f(1)=1$, $f(2)=1$, $f(3)=2$, $f(4)=2$, $f(5)=2$, $f(6)=3$, etc.

Thus solving $a1+b3 \leq 6$ we have $C=1+1+1+2+2+2+3=12$ solutions.

[For the record, The solutions are: $a=0,\dots,6$ and $b=0$ or $a=0,\dots 3$ and $b=1$, or $a=0$ and $b=2$. So $7+4+1=12$ solutions.]

I'm sure there are other ways to tackle such a problem, but since you are counting solutions, this is definitely a problem of combinatorics.

Edit: By the way, if you don't want to allow 0's as part of your solutions (i.e. all $a,b,$ etc. are positive integers), then you can replace $F$ with...

$$F = \prod\limits_{p_i \in P} \frac{x^{p_i}}{1-x^{p_i}} = (x^{p_0}+x^{2p_0}+\cdots)(x^{p_1}+x^{2p_1}+\cdots)\cdots(x^{p_n}+x^{2p_n}+\cdots)$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.